Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2605.29176 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916058141556736 |
|---|---|
| author | Juliano, Emanuel |
| author_facet | Juliano, Emanuel |
| contents | Recently, Balla, Janzer, and Sudakov showed a lower bound on the MaxCut in terms of the vector chromatic number, recovering known results on the MaxCut of $H$-free graphs. In this note, we show that their bound is tight, providing a construction that achieves a value arbitrarily close to the optimal constant. This answers a question raised by Elphick. Our construction is a modification of the geometric graph used by Feige and Schechtman to establish the integrality gap for the Goemans--Williamson semidefinite relaxation of the MaxCut. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_29176 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Tightness of a MaxCut Lower Bound via Vector Chromatic Number Juliano, Emanuel Combinatorics Recently, Balla, Janzer, and Sudakov showed a lower bound on the MaxCut in terms of the vector chromatic number, recovering known results on the MaxCut of $H$-free graphs. In this note, we show that their bound is tight, providing a construction that achieves a value arbitrarily close to the optimal constant. This answers a question raised by Elphick. Our construction is a modification of the geometric graph used by Feige and Schechtman to establish the integrality gap for the Goemans--Williamson semidefinite relaxation of the MaxCut. |
| title | Tightness of a MaxCut Lower Bound via Vector Chromatic Number |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2605.29176 |