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

Xin Chen, Hongwei Hu, Yanqing Hu +2

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 dete…