The Lovász number of random circulant graphs
A random dense circulant graph on $\mathbb{Z}_n$ is sampled by drawing $x \in \{0,1\}^{\lceil (n-1)/2 \rceil}$ uniformly at random and joining $i$ and $j$ when $x_k = 1$, where $k \in \{1, \dots, \lceil (n-1)/2 \rceil\}$ is $\pm(i - j) \bmod n$. Let $\vartheta(G)$ be the Lovász number. Bandeira, Błasiok, Dmitriev, Faure, Kireeva and Kunisky proved a precise lower bound and the upper bound $O(\sqrt{n \log\log n})$, and numerics suggest the same behaviour as for $G(n, \frac12)$.
Problem. Prove or disprove that for a random dense circulant graph $G$ on $n$ vertices, $\mathbb{E}\,\vartheta(G) = (1 + o(1))\sqrt n$ as $n \to \infty$.
Source: Dmitriev, Conjecture 18 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
- circulant graphs, Lovász theta function, random graphs, Randomstrasse101
- 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}
}
@misc{bandeira2025circulant,
author = {Bandeira, Afonso S. and B{\l}asiok, Jaros{\l}aw and Dmitriev, Daniil and Faure, Ulysse and Kireeva, Anastasia and Kunisky, Dmitriy},
title = {The {L}ov{\'a}sz number of random circulant graphs},
year = {2025},
eprint = {2502.16227},
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}
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00035, "The Lovász number of random circulant graphs", clopen.solutions.