Sharp Lovasz-Theta Bounds on Random Graphs
En palabras de los autores
It is well known that the \Lovasz-Theta function of a random graph is . 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 . 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 is with high probability, determining its asymptotic value up to vanishing relative error.
Apareció: viernes, 25 de septiembre. arXiv. Preprint, todavía sin revisión por pares.
Comentario de los autores: FOCS'26