Tight Lower Bound for Multicolor Discrepancy
Abstract
We prove the following asymptotically tight lower bound for \(k\)-color discrepancy: For any \(k \ge 2\), there exists a hypergraph with \(n\) hyperedges 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. (2025). As an application, we show that our result implies improved lower bounds for group fair division.
Fields of Study & Subjects
Mathematical Approximation and Integration
Limits and Structures in Graph Theory
Cryptography and Data Security
Publication details
- Journal / source
- Society for Industrial and Applied Mathematics eBooks
- Pages
- 266–274
- Publication date
- 1 January 2026
- Language
- EN