Tim Kunisky
John Hopkins University
Title
Spectral pseudorandomness, free probability, 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 a new approach to this problem, which also opens up intriguing connections with random matrix theory and free probability. In particular, I will show that certain deterministic induced subgraphs of the Paley graph have the same limiting spectrum as induced subgraphs on random subsets 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. I will then 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. On the way, I will describe new techniques for understanding the eigenvalue statistics of more general random or pseudorandom submatrices of certain structured matrices like ones associated to incoherent tight frames, and will mention how these helped to resolve a recent conjecture of Haikin, Zamir, and Gavish in frame theory.
