Sharp asymptotics for the Lovász number of random circulant graphs
Abstract
We study the LOVÁSZ number of dense random circulant graphs generated by independent Bernoulli bits indexed by cyclic distances. Although only O(n) independent random inputs determine O(n2) globally dependent edge indicators, we prove sharp expectation asymptotics along all odd orders, including composite orders, with leading constant one. This resolves a conjecture posed for random circulant graphs in 2025. The proof combines an exact Fourier reduction and complementary duality with a positive interior smoothing that reveals a nonlinear random fixed-point equation. To analyze this equation under the strong dependence of the distance-bit model, we construct canonical tree fields, establish growing-degree Gaussian approximations through polynomial comparison and Wick/Hermite expansions, and transfer the resulting approximation back to the original sign model. A deterministic residual estimate together with an explicit exceptional-event integration yields the sharp expectation asymptotics.
Related
- Sharp Lovasz-Theta Bounds on Random Graphs
- The Alon-Tarsi number of 4-regular circulant graphs
- The Lovász number is not alone: a continuum of Rényi points in the entanglement-assisted spectrum of graphs
- Distance and resistance on random series-parallel graphs: logarithmic speeds and near-critical asymptotics
- Perron-Wright asymptotics and critical component processes for regular inhomogeneous random graphs
BibTeX
@misc{chen2026sharp,
title = {{Sharp asymptotics for the Lovász number of random circulant graphs}},
author = {Xin Chen and Hongwei Hu and Yanqing Hu and Wei Wang and Luzhen Yang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.22971},
eprint = {2610.22971},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.22971},
note = {CC0},
}
RIS
TY - UNPB
TI - Sharp asymptotics for the Lovász number of random circulant graphs
AU - Xin Chen
AU - Hongwei Hu
AU - Yanqing Hu
AU - Wei Wang
AU - Luzhen Yang
PY - 2026
DA - 2026/10/16
PB - arXiv
DO - 10.48550/arxiv.2610.22971
UR - https://arxiv.org/abs/2610.22971
AB - We study the LOVÁSZ number of dense random circulant graphs generated by independent Bernoulli bits indexed by cyclic distances. Although only O(n) independent random inputs determine O(n^2) globally dependent edge indicators, we prove sharp expectation asymptotics along all odd orders, including composite orders, with leading constant one. This resolves a conjecture posed for random circulant graphs in 2025. The proof combines an exact Fourier reduction and complementary duality with a positive interior smoothing that reveals a nonlinear random fixed-point equation. To analyze this equation under the strong dependence of the distance-bit model, we construct canonical tree fields, establish growing-degree Gaussian approximations through polynomial comparison and Wick/Hermite expansions, and transfer the resulting approximation back to the original sign model. A deterministic residual estimate together with an explicit exceptional-event integration yields the sharp expectation asymptotics.
ER -