Tight Lower Bound for Multicolor Discrepancy

Pasin Manurangsi, Raghu Meka

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 discrep…