Tight Lower Bound for Multicolor Discrepancy

arXiv:2504.18489 · cs.DM, cs.GT · Submitted 2025-04-25 · Read on arXiv

cs.DM, cs.GT

Submitted: 2025-04-25

Updated: 2026-10-29

Comments: 13 pages. This is the TheoretiCS journal version

Journal ref: TheoretiCS, Volume 5 (October 30, 2026) theoretics:17704

DOI: 10.46298/theoretics.26.18

License: http://creativecommons.org/licenses/by/4.0/

The gist: We prove the following asymptotically tight lower bound for k-color discrepancy: For any k at least 2…

Terminology

Abstract

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

Related papers