Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2604.23634 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914507856543744 |
|---|---|
| author | Csirmaz, Laszlo |
| author_facet | Csirmaz, Laszlo |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_23634 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On the Supremum of Singleton Ratios in Submodular Functions Csirmaz, Laszlo Combinatorics Information Theory 05B35, 52B12, 52B40, 94A17 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. |
| title | On the Supremum of Singleton Ratios in Submodular Functions |
| topic | Combinatorics Information Theory 05B35, 52B12, 52B40, 94A17 |
| url | https://arxiv.org/abs/2604.23634 |