Title: The Second Eigenvalue of Dense Random Regular Graphs
Speaker: Toby Johnson, USC
Date: Monday, September 21, 2015 2:00 pm
Location: Hill center, Room 425, Rutgers University, Busch Campus, Piscataway, NJ
Consider a random d-regular graph on n vertices. Its second eigenvalue is closely related to its expansion properties, and bounding it has been a major topic of research over the last thirty years. It's conjectured by Van Vu that as n and optionally d tend to infinity, the second eigenvalue is bounded by C*sqrt(d) with probability tending to 1, so long as d remains between 3 and n-3. This is currently known to hold only if d = o(n^(1/2)). We show that it holds so long as d remains smaller than n^(2/3). We use the Kahn-Szemeredi approach, which is based on showing concentration for Rayleigh quotients of the graph's adjacency matrix. We develop new techniques based on Stein's method for proving these concentration results. Our machinery gives proofs vastly simpler than previous ones based on martingales. This is joint work with Nicholas Cook and Larry Goldstein.
See: http://math.rutgers.edu/seminars/allseminars.php?sem_name=Discrete%20Math