arXiv:2504.18489 · v4

Tight Lower Bound for Multicolor Discrepancy

首次提交 2025-04-26 00:58

版本更新 2026-10-29 19:06

雷达观测 2026-10-30 13:28

摘要

We prove the following asymptotically tight lower bound for $k$-color discrepancy: For any $k \geq 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/\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.

作者备注：13 pages. This is the TheoretiCS journal version

期刊信息：TheoretiCS, Volume 5 (2026), Article 18, 1-13