[Combprob] Combinatorics and Probability Seminar this semester

[Daniel Spielman]

The Combinatorics and Probability Seminar is back!

Our first talk will be by Toby Johnson (USC, former Yale undergrad)
It will take place this Thursday at 4:00 in LOM 215.

Title: The second eigenvalue of dense random regular graphs

Abstract:
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-Szemerédi 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.

The other talks are listed here:

https://urldefense.proofpoint.com/v2/url?u=https-3A__sites.google.com_a_yale.edu_combprob_home&d=AwIFaQ&c=-dg2m7zWuuDZ0MUcV7Sdqw&r=LF0MQT9lkPQlp3gHlW9D2fTc0d4apDhCuC758tavUvQ&m=iNKi-bmtF05l60-oWvtzjmikQAoRMbyx3y3-433Ngms&s=pquUR0-rbFBUsH1ycUESsxJ1yhKULo8Uwu7GDZrNhxg&e= 

  --Dan
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.yale.edu/pipermail/combprob/attachments/20150922/faa5c5d5/attachment.html