A degree 4 sum-of-squares lower bound for the clique number of the Paley graph

Dmitriy Kunisky, Xifan Yu

We prove that the degree 4 sum-of-squares (SOS) relaxation of the clique number of the Paley graph on a prime number $p$ of vertices has value at least $\Omega (p^{1/3})$. This is in con…