{"id":"arxiv/2609.30064","url":"https://arxiv.org/abs/2609.30064","tags":["cs.CC","cs.DM","math.CO"],"score":0,"title":"Sharp Lovasz-Theta Bounds on Random Graphs","domain":"cs.CC","source":"arxiv","authors":["Aaron Potechin","Jeff Xu"],"reviews":0,"subject":"cs.CC","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-24","reactions":{}}