UC Berkeley Discrete Analysis Seminar, Spring 2025

The interchange process in a graph with labeled vertices picks an edge uniformly at random at every step, and swaps the labels of its endpoints. Aldous conjectured that the spectral gap of this Markov chain is the same as the gap of the simple random walk on that graph. We will go over a proof given by Caputo, Liggett and Richthammer, which proceeds by induction on the vertices by applying the so-called octopus inequality.

I will discuss some calculations regarding the "octopus lemma" of Caputo, Liggett, and Richthammer, and time permitting will discuss some aspects of a representation-theoretic proof due to Cesi.

The existence of d-regular Ramanujan graphs (an optimal spectral expander) for every d has been a longstanding open question. In their recent and groundbreaking paper, Huang, McKenzie, and Yau show that for any d, a random d-regular graph on n vertices is Ramanujan with probability 69% as n tends to infinity. Their 150 page paper is a tour de force of a variety of tools in random matrix theory. This week we will begin a series of talks aimed at understanding the details of their proof. In this introductory talk, we will provide a high level outline of their approach and an introduction to some of the key tools they use.

I will discuss how to prove the edge statistics from the rigidity of the spectrum. It is proved by analyzing the time decay property of a (discrete version of) heat equation derived from the Dyson Brownian motion. I will follow section 3 of Landon–Yau's "Edge statistics of Dyson Brownian motion".

We will continue unpacking Huang, McKenzie, and Yau's proof that a random d-regular graph is Ramanujan with constant probability. Our first talk in this series framed this as a random matrix theory problem and introduced Dyson Brownian motion as a way to reduce this problem to understanding the edge statistic of a time-dependent matrix. Our second talk established that for sufficiently large t, it will suffice to show optimal rigidity of the eigenvalues. This week, we will introduce our main tool to both show optimal rigidity and understand the behavior of the edge statistic for small t: loop equations. We define our loop equation of interest (motivated by the underlying graph model) and will begin to show how studying this can (1) prove optimal rigidity and (2) prove the edge statistic doesn’t change for sufficiently small t.

We will continue unpacking Huang, McKenzie, and Yau's proof that a random d-regular graph is Ramanujan with constant probability. Last week we discussed how to show optimal rigidity from a bound relating Stieltjes transformations. This week, we will introduce our main tool for studying these Stieltjes transformations: loop equations. We will define the self consistent equation of interest, motivated by the underlying graph model. Time permitting, Zack will begin to discuss how we can also use Stieltjes transformations and the loop equation to analyze the edge statistic for small t.

Spring Break

We will continue to discuss the breakthrough of Huang, McKenzie, and Yau that a random d-regular graph is Ramanujan with constant probability. Thus far we have focused on the plan of attack for large t, to show that edge eigenvalues of GOE matrices resemble those of a "mixture" of a GOE and a random adjacency matrix. In this talk, we will discuss the case of small t, where we wish to show that the "mixture" has edge eigenvalues resembling that of the random adjacency matrix. This will proceed following §17 of Erdos–Yau's book, in particular the reduction to a result on the derivatives of expected Stieltjes transforms.

To show universality through Dyson Brownian Motion, we must show that we do not alter spectral statistics after perturbation with a Gaussian matrix. In this talk, we consider the Gaussian Divisible Ensemble, which is the original distribution combined with a Gaussian matrix. In this talk, we show the Stieltjes transform is preserved as we slowly "replace" the original matrix with the Gaussian matrix. We do this by utilizing the loop equation, which is a self-consistent equation for a finite Gaussian matrix. We show through our resampling argument that our Gaussian Divisible Ensemble satisfies a specific family of loop equations up to sufficiently small error.

We will begin the final portion of Huang, McKenzie, and Yau's December breakthrough that most graphs are Ramanujan. Thus far we have reduced the result to bounding errors in the self-consistent equation for the Stieltjes transform. We do this by introducing and analyzing a technique in which the graph is resampled on the boundary of a tree-like neighborhood. For simplicity we will follow Huang, McKenzie, and Yau's paper from May which achieves only optimal rigidity (falling short of edge universality) and over the course of these talks will address the technical aspects required to upgrade the result.

We will continue with the final portion of Huang, McKenzie, and Yau's December breakthrough that most graphs are Ramanujan by following their paper from May which achieves optimal rigidity. In this talk, we will prove that error terms arrived at in the previous talk are small.