Spectral pseudorandomness and the clique number of the Paley graph

Abstract:

The Paley graph is a classical number-theoretic construction of a graph that is believed to behave “pseudorandomly” in many regards. Accurately bounding the clique number of the Paley graph is a long-standing open problem in number theory, with applications to several other questions about the statistics of finite fields. I will present recent results studying the application of convex optimization and spectral graph theory to this problem, which involve understanding the extent to which the Paley graph is “spectrally pseudorandom” in various senses.

First, I will show a lower bound on the degree 4 sum-of-squares relaxation of the clique number of the Paley graph, derandomizing an analogous result for Erdos-Renyi random graphs due to Deshpande and Montanari (2015). On the other hand, I will offer some evidence that this relaxation may in fact yield bounds improving on the state of the art, thanks to the spectrum of the Paley graph being sufficiently different from that of an Erdos-Renyi graph.

Second, I will show that certain deterministic induced subgraphs of the Paley graph have the same limiting spectrum as induced subgraphs on random sets of vertices of the same size. I will discuss how this phenomenon arises as a consequence of asymptotic freeness (in the sense of free probability) of certain matrices associated with the Paley graph. Finally, I will present conjectures describing a stronger analogy between random and pseudorandom deterministic induced subgraphs that would lead to clique number bounds improving on the state of the art.

Based partly on joint work with Xifan Yu.

Bio:

Dmitriy (Tim) Kunisky is a postdoctoral associate at Yale University’s Department of Computer Science, hosted by Daniel Spielman. Before joining Yale, he received his PhD in Mathematics from the Courant Institute at New York University, advised by Afonso Bandeira and Gerard Ben Arous. He is broadly interested in both heuristic and rigorous methods for assessing the computational hardness of random optimization problems, especially problems that can be approached using convex optimization. More recently, he has also studied universality and derandomization techniques for showing that the phenomena governing random problems also occur in semi-random and deterministic settings.