Lovasz-Theta value of random graphs tightly determined at square root of n
Sharp Lovasz-Theta Bounds on Random Graphs
Computational ComplexityDiscrete Mathematics
Summary
Random graphs, which connect points in a random way, have a number called the Lovasz-Theta function that helps understand their structure. It was known this number grows roughly like the square root of the number of points, but the exact growth was uncertain. The authors have proven that this function essentially equals the square root of the number of points as the graph becomes very large. This solves a question that has been open for a long time using advanced mathematical techniques.
What this means in practice
- •For algorithm designers: Use the precise Lovasz-Theta value to better analyze and design algorithms for graph problems on random instances.
- •For network engineers: Gain improved theoretical understanding of random network properties impacting communication protocols and network resilience.
A theory result. No direct application yet.
Authors
Aaron Potechin, Jeff Xu
Abstract
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 work, we resolve this question by proving that the \Lovasz-Theta function of $G(n,\tfrac{1}{2})$ is $(1+o_n(1))\sqrt{n}$ with high probability, determining its asymptotic value up to vanishing relative error.