# Tight Lower Bound for Multicolor Discrepancy

arXiv: https://arxiv.org/abs/2504.18489 · HTML: https://mlsanity.com/paper/2504.18489/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Apr 2025.

## Built on by (most cited first, 1 of 1)

- [Simultaneously Fair Allocation of Indivisible Items Across Multiple Dimensions](https://mlsanity.com/paper/2506.21727/) (2025)

## Abstract (arXiv)

We prove the following asymptotically tight lower bound for k-color discrepancy: For any k ≥ 2, there exists a hypergraph with n hyperedges such that its k-color discrepancy is at least Omega(√n). This improves on the previously known lower bound of Omega(√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.