Non-Additive Discrepancy: Coverage Functions in a Beck-Fiala Setting
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913074733121536 |
|---|---|
| author | Avila, Tatiana Rocha Rohwedder, Lars Wennmann, Leo |
| author_facet | Avila, Tatiana Rocha Rohwedder, Lars Wennmann, Leo |
| contents | Recent concurrent work by Dupré la Tour and Fujii and by Hollender, Manurangsi, Meka, and Suksompong [ITCS'26] introduced a generalization of classical discrepancy theory to non-additive functions, motivated by applications in fair division. As many classical techniques from discrepancy theory seem to fail in this setting, including linear algebraic methods like the Beck-Fiala Theorem [Discrete Appl. Math '81], it remains widely open whether comparable non-additive bounds can be achieved.
Towards a better understanding of non-additive discrepancy, we study coverage functions in a sparse setting comparable to the classical Beck-Fiala Theorem. Our setting generalizes the additive Beck-Fiala setting, rank functions of partition matroids, and edge coverage in graphs. More precisely, assuming each of the $n$ items covers only $t$ elements across all functions, we prove a constructive discrepancy bound that is polynomial in $t$, the number of colors $k$, and $\log n$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_09948 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Non-Additive Discrepancy: Coverage Functions in a Beck-Fiala Setting Avila, Tatiana Rocha Rohwedder, Lars Wennmann, Leo Combinatorics Discrete Mathematics Data Structures and Algorithms Recent concurrent work by Dupré la Tour and Fujii and by Hollender, Manurangsi, Meka, and Suksompong [ITCS'26] introduced a generalization of classical discrepancy theory to non-additive functions, motivated by applications in fair division. As many classical techniques from discrepancy theory seem to fail in this setting, including linear algebraic methods like the Beck-Fiala Theorem [Discrete Appl. Math '81], it remains widely open whether comparable non-additive bounds can be achieved. Towards a better understanding of non-additive discrepancy, we study coverage functions in a sparse setting comparable to the classical Beck-Fiala Theorem. Our setting generalizes the additive Beck-Fiala setting, rank functions of partition matroids, and edge coverage in graphs. More precisely, assuming each of the $n$ items covers only $t$ elements across all functions, we prove a constructive discrepancy bound that is polynomial in $t$, the number of colors $k$, and $\log n$. |
| title | Non-Additive Discrepancy: Coverage Functions in a Beck-Fiala Setting |
| topic | Combinatorics Discrete Mathematics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2602.09948 |