Mathematical Sciences Research Institute

Home » GFA Postdoc Seminar: Spectral gap of random graphs


GFA Postdoc Seminar: Spectral gap of random graphs November 06, 2017 (11:30 AM PST - 12:15 PM PST)
Parent Program:
Location: MSRI: Simons Auditorium
Speaker(s) Pierre Youssef (Université de Paris VII (Denis Diderot))
Description No Description
No Video Uploaded

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.

No Notes/Supplements Uploaded No Video Files Uploaded