Sharp Lovasz-Theta Bounds on Random Graphs
It is well known that the \Lovasz-Theta function of a random graph $G(n,\tfrac{1}{2})$ is $Θ(\sqrt{n})$. More precisely, it is tightly concentrated in the interval \( [\sqrt{n},\, 2\sqrt{n}], \) where the upper bound follows from an explicit dual witness for the associated semidefinite program. Numerical evidence and heuristic arguments suggest that the true value is $(1+o(1))\sqrt{n}$. However, closing this gap has remained a longstanding challenge, resisting existing techniques even in light of recent progress on sharp algorithmic thresholds and non-asymptotic free probability. In this…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.30064
curl -X POST /api/v1/records/arxiv/2609.30064/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.30064/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'