[Combprob] Wednesday, Sept. 30, Dan Spielman "Ramanujan Graphs and Finite Free Probability"

[Daniel Spielman]

Some of you might be interested in the talk I am giving tomorrow in the
Math Colloquium: "Ramanujan Graphs and Finite Free Probability"

It is at 4:15 in LOM 215.

Abstract:
We introduce "Finite Free Probability" to prove the existence of bipartite
Ramanujan graphs of every degree and number of vertices. Ramanujan graphs
are defined in terms of the eigenvalues of their adjacency or Laplacian
matrices. In this spectral perspective, they are the best possible expander
graphs. Infinite families of Ramanujan graphs were first constructed by
Margulis and Lubotzky, Phillips and Sarnak. These constructions are
sporadic, only producing graphs of special degrees and numbers of vertices.
In this talk, we outline an elementary proof of the existence of bipartite
Ramanujan graphs of every degree and number of vertices. We do this by
considering the expected characteristic polynomial of a random d-regular
graph. We develop finite analogs of results in free probability to compute
this polynomial and to bound its roots. By proving that this polynomial is
the average of polynomials in an interlacing family, we then prove there
exists a graph in the distribution whose eigenvalues satisfy the Ramanujan
bound.

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