The Lovász number of random circulant graphs

Afonso S. Bandeira, Jarosław Błasiok, Daniil Dmitriev +3

This paper addresses the behavior of the Lovász number for dense random circulant graphs. The Lovász number is a well-known semidefinite programming upper bound on the independen…