On the Supremum of Singleton Ratios in Submodular Functions
For researchers in submodular analysis and optimization, this work provides new bounds on a fundamental quantity characterizing variable dependence in submodular functions, though the gap between bounds remains wide.
The paper studies the maximal singleton ratio in submodular functions, constructing an example where it reaches Ω(n/log n) and proving a doubly exponential upper bound, leaving a large gap open.
Let $N$ be a finite set of cardinality $n$, and $a\in 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. We construct an example demonstrating that $λ$ can be as large as $Ω(n/\log n)$. Furthermore, we establish a doubly exponential upper bound on $λ$. The problem of narrowing the gap between these bounds remains open.