Tight Lower Bound for Multicolor Discrepancy

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 Ω(√n). This improves on the previously known lower bound of Ω(√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.