Non-Additive Discrepancy: Coverage Functions in a Beck-Fiala Setting

T. R. Avila, Lars Rohwedder, Leo Wennmann · 2026

Read Non-Additive Discrepancy: Coverage Functions in a Beck-Fiala Setting by T. R. Avila, Lars Rohwedder, Leo Wennmann (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-2602-09948.txt.

Description

Discrepancy theory asks how evenly items can be split among colors, and its classical tools assume the quantity being split adds up neatly. A 2026 paper led by Tatiana Rocha Avila, with two co-authors, studies what happens when it does not. Recent work extended the theory to non-additive functions, motivated by fair division, but many classical methods fail there.

The authors focus on coverage functions in a sparse setting that mirrors the classical Beck-Fiala setup. The same setting covers matroid rank functions and graph edge coverage. Assuming each item touches only a few elements across all functions, they prove a constructive bound. It grows polynomially with that sparsity, the number of colors, and the logarithm of the item count.

Catalog record

CREATORT. R. Avila, Lars Rohwedder, Leo Wennmann
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE58 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-09948

Browse the full library · About the Tower of Babel