Tight Lower Bound for Multicolor Discrepancy
cs.DM, cs.GT
Submitted: 2025-04-25
Updated: 2026-10-29
Comments: 13 pages. This is the TheoretiCS journal version
Journal ref: TheoretiCS, Volume 5 (October 30, 2026) theoretics:17704
DOI: 10.46298/theoretics.26.18
License: http://creativecommons.org/licenses/by/4.0/
The gist: We prove the following asymptotically tight lower bound for k-color discrepancy: For any k at least 2…
Terminology
Abstract
We prove the following asymptotically tight lower bound for k-color discrepancy: For any k at least 2, there exists a hypergraph with n hyperedges such that its k-color discrepancy is at least Ω(sqrt n). This improves on the previously known lower bound of Ω(sqrt n/ k) due to Caragiannis et al. (arXiv:2502.10516). As an application, we show that our result implies improved lower bounds for group fair division.
Related papers
- Low-Temperature Sampling via Equilibrium Disagreements
- An Improved Bound for Testing k-Colorability
- Temporal Cliques Admit Linear Spanners
- Multiway Partition is FPT for Connectivity Functions
- Profile and neighbourhood complexity of graphs excluding a minor and tree-structured graphs
- Constrained intersection representations and forbidden patterns