EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

On the Supremum of Singleton Ratios in Submodular Functions

Laszlo Csirmaz

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →