Delphi.science

Sharp asymptotics for the Lovász number of random circulant graphs

Source: arxiv.org/abs/2610.22971

Xin Chen, Hongwei Hu, Yanqing Hu, Wei Wang, Luzhen Yang

arXivarxiv/2610.22971Oct 16, 2026math.PRscore 0

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…

JSON

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2610.22971
curl -X POST /api/v1/records/arxiv/2610.22971/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.22971/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'