Seminar

Given a graph, it is known that a large gap between the largest and second largest eigenvalues (spectral gap) of its adjacency matrix translates into good expansion properties. Ramanujan graphs are those with the largest possible spectral gap and are referred to as the optimal spectral expanders. We investigate two models of random graphs: the Erdos-Rényi graph and random d-regular graphs. For the former, we show that it is almost Ramanujan above the threshold of connectivity while for random d-regular graphs, we show the optimal dependence on d (up to a multiplicative constant) of the spectral gap. The talk is based on joint works with Konstantin Tikhomirov and Rafal Latala, Ramon Van Handel.