Tight Lower Bound for Multicolor Discrepancy
TheoretiCS · 02.11.2026 · Volume 5
DOI: 10.46298/theoretics.26.18 ↗Kurz gefasst
Fachartikel in der Zeitschrift TheoretiCS, online erschienen am 02.11.2026. Verfasst von Pasin Manurangsi und 1 weiteren Autor:innen.
Abstract (Originalsprache)
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.
Zitieren
APA
Manurangsi, P., & Meka, R. (2026). Tight Lower Bound for Multicolor Discrepancy. TheoretiCS, Volume 5. https://doi.org/10.46298/theoretics.26.18
Vancouver
Manurangsi P, Meka R. Tight Lower Bound for Multicolor Discrepancy. TheoretiCS. 2026;Volume 5. doi:10.46298/theoretics.26.18
BibTeX
@article{Manurangsi2026,
author = {Manurangsi, Pasin and Meka, Raghu},
title = {Tight Lower Bound for Multicolor Discrepancy},
journal = {TheoretiCS},
year = {2026},
volume = {Volume 5},
doi = {10.46298/theoretics.26.18}
}
EUVIMED