English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

We prove that the degree 4 sum-of-squares (SOS) relaxation of the cliquenumber of the Paley graph on a prime number $p$ of vertices has value at least$\Omega(p^{1/3})$. This is in contrast to the widely believed conjecture thatthe actual clique number of the Paley graph is $O(\mathrm{polylog}(p))$. Ourresult may be viewed as a derandomization of that of Deshpande and Montanari(2015), who showed the same lower bound (up to $\mathrm{polylog}(p)$ terms)with high probability for the Erd\H{o}s-R\'{e}nyi random graph on $p$ vertices,whose clique number is with high probability $O(\log(p))$. We also show thatour lower bound is optimal for the Feige-Krauthgamer construction ofpseudomoments, derandomizing an argument of Kelner. Finally, we presentnumerical experiments indicating that the value of the degree 4 SOS relaxationof the Paley graph may scale as $O(p^{1/2 - \epsilon})$ for some $\epsilon >0$, and give a matrix norm calculation indicating that the pseudocalibrationproof strategy for SOS lower bounds for random graphs will not immediatelytransfer to the Paley graph. Taken together, our results suggest that degree 4SOS may break the "$\sqrt{p}$ barrier" for upper bounds on the clique number ofPaley graphs, but prove that it can at best improve the exponent from $1/2$ to$1/3$.

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