On the Supremum of Singleton Ratios in Submodular Functions

Let N be a finite set of cardinality n, and let a∈N. A submodular function f on N with f(a)=1 is defined to be a-reduced if, for any decomposition f=g+h into submodular functions, where h does not depend on a, it follows that h is identically zero. The maximal possible value of f on the remaining singletons defines a quantity λ that characterizes the degree to which one variable can constrain the value of another; geometrically, it also limits the possible elongation of the associated submodular base polytope. The parameter has concrete relevance: it caps the share-size lower bounds provable for secret-sharing schemes via the basic Shannon inequalities, and it controls the geometry of the base polytopes on which greedy submodular-optimization algorithms operate. We construct an example demonstrating that λ can be as large as Ω(n/logn). Furthermore, we establish a doubly exponential upper bound on λ. The problem of narrowing the gap between these bounds remains open.