← All problems

2025 conjecture on the Lovász number of random circulant graphs

Let nn tend to infinity through odd integers. Define the random circulant graph GnG_n on Z/nZ\mathbb{Z}/n\mathbb{Z} by taking independent random variables X1,…,X(n−1)/2∼Bernoulli⁡(1/2)X_1,\ldots,X_{(n-1)/2}\sim\operatorname{Bernoulli}(1/2) and joining distinct vertices i,ji,j whenever Xdn(i,j)=1X_{d_n(i,j)}=1, where dn(i,j)=min⁡{∣i−j∣,n−∣i−j∣}d_n(i,j)=\min\{|i-j|,n-|i-j|\}. The conjecture is that Eϑ(Gn)=(1+o(1))n\mathbb{E}\vartheta(G_n)=(1+o(1))\sqrt{n} as n→∞n\to\infty through odd integers, where ϑ(Gn)\vartheta(G_n) denotes the Lovász number of GnG_n.

References

Source: arXiv

Progress summary

Refreshed
Open · solution reported

An unrefereed October 2026 preprint claims to prove the conjectured sharp asymptotic, but the claim has not been independently verified.

The conjecture asserts that the expected Lovász number of a dense random circulant graph satisfies Eϑ(G)=(1+o(1))n\mathbb{E}\vartheta(G)=(1+o(1))\sqrt{n}.

Known results

The 2025 work of Afonso S. Bandeira, Jarosław Błasiok, Daniil Dmitriev, Ulysse Faure, Anastasia Kireeva, and Dmitriy Kunisky proved n≤Eϑ(G)≤Cnlog⁡log⁡n\sqrt{n}\leq\mathbb{E}\vartheta(G)\leq C\sqrt{n\log\log n}, leaving the sharp asymptotic open.

October 2026 claimed resolution

Xin Chen, Hongwei Hu, Yanqing Hu, Wei Wang, and Luzhen Yang claim the conjectured sharp asymptotics, addressing the dependence among edge indicators in the distance-bit model. The retrieved evidence is an unrefereed preprint, so this is a claimed resolution rather than a verified one.

Current status (as of October 2026): An October 2026 preprint claims to establish Eϑ(G)=(1+o(1))n\mathbb{E}\vartheta(G)=(1+o(1))\sqrt{n}, but the result remains unverified.

Sources

Solutions 0

No solutions have been posted yet.