Skip to content
Preprint

Sharp Lovasz-Theta Bounds on Random Graphs

Sep 2026 · 0 citations
Computer Science Mathematics

Abstract

It is well known that the \Lovasz-Theta function of a random graph $G(n,\tfrac{1}{2})$ is $\Theta(\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.

View source

Similar papers

Sep 2026

A Resolution of Friedgut's Conjecture on Influential Coalitions

We prove that, for every constant $\varepsilon>0$ and every function $f:\Sigma^n\to\{0, 1\}$, there is a coalition of $O(n/\sqrt{\log n})$ coordinates and a target output $b\in\{0, 1\}$ such that, after the remaining coordinates are sampled uniformly and independently, the coalition can choose its values to make the ou...

Eshan Chattopadhyay, Mohit Gurumukhani · 1 citation · ⚡1
Preprint Oct 2026

The Choice Number of Random Graphs

In 1999, Alon, Krivelevich and Sudakov conjectured that the choice number and chromatic number of the random graph $G(n,p)$ are asymptotically equal whenever $np\to\infty$. We prove their conjecture, showing that, with high probability, $$ \operatorname{ch}(G(n,p))=(1+o(1))\chi(G(n,p)) $$ whenever $np\to\infty$. This i...

Lan Wang, Jia-Sheng Zeng · 0 citations
Preprint Sep 2026

Sharper Zarankiewicz and Diagonal Bipartite Ramsey Bounds

We prove that there is an absolute positive constant $c$ such that every bipartite graph with $N$ vertices in each part and at least $N^2/2$ edges contains a complete bipartite graph $K_{t,t}$ whenever $N\ge c\, 2^{t}$. This improves the classical K\H{o}v\'ari-S\'os-Tur\'an bound requiring $N$ of order $t\,2^t $. As a...

D. Mubayi · 0 citations
Preprint Sep 2026

Tighter bounds on Koml\'os discrepancy: existence and algorithmic results

Guo, Fang, and Lu recently proved the Koml\'os conjecture: for vectors $v_1,\ldots,v_n\in\mathbb R^d$ of Euclidean norm at most one, there are signs $\varepsilon_j\in\{-1,1\}$ with $\|\sum_j\varepsilon_jv_j\|_\infty\le3\sqrt{2\pi}$. We give a short proof of the bound $3\pi$ that keeps the geometric lifting framework of...

Emrullah Akbas, Suvrit Sra · 2 citations
Preprint Oct 2026

On the Hardy--Littlewood--Chowla conjecture

An old conjecture dating back at least to Hildebrand's work in 1989, asserts that the M\"obius function exhibits cancellation on shifted primes; that is, $$\sum_{p\le x}\mu(p+2)=o(\pi(x)),\quad \text{or equivalently}\quad \sum_{n\le x}\Lambda(n)\mu(n+2)=o(x).$$ This is also a well-known model case for the parity proble...

Guang-Shi Lu, Zhi-Wei Wang, Jie Wu · 3 citations · ⚡2
Preprint Oct 2026

Sharp Asymptotics for the Solvability Probability of Random Stable Roommates

For even $n$, let $P_n$ be the probability that independent uniform strict preference lists on $n$ participants admit a stable perfect matching. We prove \[ P_n\sim\frac{e\,2^{1/4}\Gamma(3/4)}{\sqrt\pi}\,n^{-1/4}. \] This establishes Mertens's conjectured exponent of decay, with a leading constant different from his or...

Caden Young, Ian Studebaker · 0 citations

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.