The Lovász number of G(n, 1/2)
Let $\vartheta(G)$ be the Lovász number of a graph $G$. Several results on $\vartheta$ of the Erdős–Rényi graph $G(n,p)$ are known (Juhász; Coja-Oghlan; Arora and Bhaskara), but not its precise asymptotics for $p = \frac12$.
Problem. Prove or disprove that for $G \sim G(n, \frac12)$, $\mathbb{E}\,\vartheta(G) = (1 + o(1))\sqrt n$ as $n \to \infty$.
Source: Dmitriev, Conjecture 17 of Randomstrasse101, in “The Lovasz number for random graphs” (2025); Entry 9 of arXiv:2603.29571.
The statement is adapted from randomstrasse101.math.ethz.ch, whose text is available under CC BY 4.0.
Classification
- Primary
- CO — Combinatorics
- Secondary
- OC, PR
- Keywords
- Lovász theta function, random graphs, Randomstrasse101, semidefinite programming
- Literature checked
- Oct. 2, 2026 by clemens-admin
References
@misc{randomstrasse2025,
author = {Bandeira, Afonso S. and Dmitriev, Daniil and Lucca, Kevin and Nizi{\'c}-Nikolac, Petar and R{\"o}dder, Almut},
title = {{Randomstrasse101}: Open Problems of 2025},
year = {2026},
eprint = {2603.29571},
archivePrefix = {arXiv}
}
@article{lovasz1979shannon,
author = {Lov{\'a}sz, L{\'a}szl{\'o}},
title = {On the {S}hannon capacity of a graph},
journal = {IEEE Transactions on Information Theory},
volume = {25},
number = {1},
pages = {1--7},
year = {1979}
}
@article{juhasz1982theta,
author = {Juh{\'a}sz, Ferenc},
title = {The asymptotic behaviour of {L}ov{\'a}sz' $\vartheta$ function for random graphs},
journal = {Combinatorica},
volume = {2},
number = {2},
pages = {153--155},
year = {1982}
}
@article{cojaoghlan2005lovasz,
author = {Coja-Oghlan, Amin},
title = {The {L}ov{\'a}sz number of random graphs},
journal = {Combinatorics, Probability and Computing},
volume = {14},
number = {4},
pages = {439--465},
year = {2005}
}
@misc{arora2011theta,
author = {Arora, Sanjeev and Bhaskara, Aditya},
title = {A note on the {L}ov{\'a}sz theta number of random graphs},
note = {Unpublished note}
}
Resolution claims
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 …
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-02 | Open → Solution claimed | The registry's curators | Sharp Lovasz-Theta Bounds on Random Graphs v1 recorded from arXiv:2609.30064v1. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00057, "The Lovász number of G(n, 1/2)", clopen.solutions.