Tightness of a MaxCut Lower Bound via Vector Chromatic Number
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.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2605.29176
curl -X POST /api/v1/records/arxiv/2605.29176/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2605.29176/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'