PreprintarXiv licencearXiv
Sharp Lovasz-Theta Bounds on Random Graphs
Abstract
It is well known that the \Lovasz-Theta function of a random graph G(n,1/2) is Θ(√n). More precisely, it is tightly concentrated in the interval [√n, 2√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))√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 work, we resolve this question by proving that the \Lovasz-Theta function of G(n,1/2) is (1+on(1))√n with high probability, determining its asymptotic value up to vanishing relative error.
Related
- Sharp asymptotics for the Lovász number of random circulant graphs
- On some k-fold generalizations of Lovász theta and their sandwich theorems
- Sharp Bounds for Kulli-Basava Indices of Graphs
- Very sharp distance and range transitions for random walk bridges on Ramanujan graphs
- Sharp Bounds on the Eigenvalues of Kikuchi Graphs and Applications to Quantum Max Cut
BibTeX
@misc{potechin2026sharp,
title = {{Sharp Lovasz-Theta Bounds on Random Graphs}},
author = {Aaron Potechin and Jeff Xu},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.30064},
eprint = {2609.30064},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.30064},
}
RIS
TY - UNPB
TI - Sharp Lovasz-Theta Bounds on Random Graphs
AU - Aaron Potechin
AU - Jeff Xu
PY - 2026
DA - 2026/09/24
PB - arXiv
DO - 10.48550/arxiv.2609.30064
UR - https://arxiv.org/abs/2609.30064
AB - It is well known that the \Lovasz-Theta function of a random graph G(n,1/2) is Θ(√n). More precisely, it is tightly concentrated in the interval [√n, 2√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))√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 work, we resolve this question by proving that the \Lovasz-Theta function of G(n,1/2) is (1+o_n(1))√n with high probability, determining its asymptotic value up to vanishing relative error.
ER -