On the Supremum of Singleton Ratios in Submodular Functions
Mathematics · 21.06.2026 · 14 (12) · 2223
DOI: 10.3390/math14122223 ↗Kurz gefasst
Fachartikel in der Zeitschrift Mathematics, online erschienen am 21.06.2026. Verfasst von Laszlo Csirmaz. Die Arbeit nennt 21 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: ERC Advanced Grant ERMiD.
Abstract (Originalsprache)
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.
Förderung
- ERC Advanced Grant ERMiD
Zitieren
APA
Csirmaz, L. (2026). On the Supremum of Singleton Ratios in Submodular Functions. Mathematics, 14(12), 2223. https://doi.org/10.3390/math14122223
Vancouver
Csirmaz L. On the Supremum of Singleton Ratios in Submodular Functions. Mathematics. 2026;14(12):2223. doi:10.3390/math14122223
BibTeX
@article{Csirmaz2026,
author = {Csirmaz, Laszlo},
title = {On the Supremum of Singleton Ratios in Submodular Functions},
journal = {Mathematics},
year = {2026},
volume = {14},
number = {12},
pages = {2223},
doi = {10.3390/math14122223}
}
EUVIMED