Sharp Lovasz-Theta Bounds on Random Graphs

Aaron Potechin; Jeff Xu

In the authors' words

It is well known that the \Lovasz-Theta function of a random graph $G (n, \frac{1}{2})$ is $Θ (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)) 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, \frac{1}{2})$ is $(1 + o_{n} (1)) n$ with high probability, determining its asymptotic value up to vanishing relative error.

Main resultThe abstract does not state a limitation.

Sharp Lovasz-Theta Bounds on Random Graphs

In the authors' words

More on Algorithms & complexity that day

A New Gap Sequence for Shellsort: RL-Driven Algorithm Discovery Beyond N4/3

A General Composition Theorem for Approximate Degree

Practical and Space-Efficient LZ77 and LZ Pre-Compression via String Synchronizing Sets

A Human-Like Pedestrian Model for Automated Driving Simulations

Dense Matrices Are Alike; Sparse Matrices Are Sparse in Their Own Way: A Structure-Adaptive Tile Cholesky Factorization

A New Gap Sequence for Shellsort: RL-Driven Algorithm Discovery Beyond $N^{4/3}$