EUVIMEDEUVIMED entdecken
Crossref

Tight Lower Bound for Multicolor Discrepancy

Pasin Manurangsi, Raghu Meka

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →