2504.18489

#1 Tight Lower Bound for Multicolor Discrepancy [PDF] [Copy] [Kimi] [REL]

Authors: Pasin Manurangsi, Raghu Meka

We prove the following asymptotically tight lower bound for $k$-color discrepancy: For any $k \geq 2$, there exists a hypergraph with $n$ vertices such that its $k$-color discrepancy is at least $\Omega(\sqrt{n})$. This improves on the previously known lower bound of $\Omega(\sqrt{n/\log 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.

Subjects: Discrete Mathematics , Computer Science and Game Theory

Publish: 2025-04-25 16:58:59 UTC

---