On the Supremum of Singleton Ratios in Submodular Functions

L. Csirmaz · 2026

Read On the Supremum of Singleton Ratios in Submodular Functions by L. Csirmaz (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-23634.txt.

Description

Csirmaz studies how much one variable can constrain another in a submodular function, through the largest value the function can take on other singletons once one is fixed at one. He constructs an example showing this quantity can grow nearly linearly, up to a logarithmic factor, in the size of the ground set. He also proves a doubly exponential upper bound, leaving a wide gap between the bounds open.

Catalog record

CREATORL. Csirmaz
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE25953
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2604.23634

Browse the full library · About the Tower of Babel