Tight Lower Bound for Multicolor Discrepancy
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914088933654528 |
|---|---|
| author | Manurangsi, Pasin Meka, Raghu |
| author_facet | Manurangsi, Pasin Meka, Raghu |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_18489 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Tight Lower Bound for Multicolor Discrepancy Manurangsi, Pasin Meka, Raghu Discrete Mathematics Computer Science and Game Theory 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. |
| title | Tight Lower Bound for Multicolor Discrepancy |
| topic | Discrete Mathematics Computer Science and Game Theory |
| url | https://arxiv.org/abs/2504.18489 |