UC Berkeley Discrete Analysis Seminar, Fall 2024

We will begin to discuss the recent paper of Chen, Garza Vargas, Tropp, and van Handel, focusing on the overall approach of the paper for showing strong convergence, discussing some of the technical inputs, and introducing the application to recovering Friedman's theorem for random regular graphs.

We will continue discussing arXiv:2405.16026. Our goals for this talk will be to (1) prove that the expected trace of a polynomial of permutation matrices is a rational function of the inverse of the dimension and (2) bounding the error for a Taylor expansion of this rational function. For (1), we will use a combinatorial interpretation of our target quantity. For (2), we will use an extension of the Markov brothers' inequality to rational functions.

We previously showed the existence of a "Taylor-like" expansion of the expected trace of a polynomial of permutation matrices using linear functionals defined on polynomials. This week, Izzy will discuss the extension of this result to linear functionals defined on smooth functions (Theorem 7.1). David will then start on the analysis required to show Friedman’s theorem using the discussed framework.

We will use the machinery developed in the previous talks to give a very short proof of Friedman’s theorem. This essentially boils down to getting control on the moments of the compactly supported distribution constructed in the previous talk. To do so, we will do a brief excursion into the combinatorics of the free group.

En route towards understanding the breakthrough result of Hide and Magee (2023), we will first prove the well-known result that the spectral gap of a hyperbolic surface can at most be 1/4 (as its genus tends to infinity). This result serves as the spectral-geometric analog of the Alon–Boppana bound from graph theory, which states that the the second largest eigenvalue of a d-regular n-vertex graph must at least be 2sqrt(d-1)-o(1).

I will present Buser's paper in which he establishes a relationship between the partition number of a cubic graph and the first (nonzero) eigenvalue of a compact Riemann surface.

We will discuss the paper of Brooks and Makover: "In this paper, we address the following question: What does a typical compact Riemann surface of large genus look like geometrically? We do so by constructing compact Riemann surfaces from oriented 3-regular graphs. The set for such Riemann surfaces is dense in the space of all compact Riemann surfaces, namely Belyi surfaces. And in this construction we can control the geometry of the compact Riemann surface by the geometry of the graph. We show that almost all such surfaces have large first eigenvalue and large Cheeger constant."

We will discuss more details of the paper of Brooks and Makover, continued from 10/24: "In this paper, we address the following question: What does a typical compact Riemann surface of large genus look like geometrically? We do so by constructing compact Riemann surfaces from oriented 3-regular graphs. The set for such Riemann surfaces is dense in the space of all compact Riemann surfaces, namely Belyi surfaces. And in this construction we can control the geometry of the compact Riemann surface by the geometry of the graph. We show that almost all such surfaces have large first eigenvalue and large Cheeger constant."

We will begin our discussion of the result of Hide and Magee, in which it is shown that with overwhelming probability, taking a random cover of a hyperbolic surface introduces no new Laplacian eigenvalues. This is then used to show that a sequence of hyperbolic surfaces exists which has near-optimal Laplacian spectral gap.

We will continue our discussion of the result of Hide and Magee, in which it is shown that with overwhelming probability, taking a random cover of a hyperbolic surface introduces no new Laplacian eigenvalues. This talk will focus on the step of the proof in which the resolvent is constructed.

Happy Thanksgiving!

I will summarize a paper by Antoine Song, using random matrix theory to construct a sequence of minimal surfaces in high-dimensional spheres, which become “more and more hyperbolic” in a certain sense. The minimal surface property implies that the eigenvalue 1/4 has very high multiplicity. The proof highlights a geometric intuition behind strong convergence. I will provide all necessary geometric background.