Tata Institute of Fundamental Research
Ramanujan Graphs of All Degrees
Seminar
Speaker:
Nikhil Srivastava (Microsoft Research, India
#9, Lavelle Road
Bangalore
Karnataka 560025
)
Organiser:
Prahladh Harsha
Date:
Monday, 6 May 2013, 16:30 to 17:30
Venue:
AG-80
(Scan to add to calendar)
Abstract:
We prove that there exist infinite families of bipartite Ramanujan graphs of every degree bigger than 2. We do this by proving a variant of a conjecture of Bilu and Linial about the existence of good 2-lifts of every graph.
We also construct infinite families of `irregular Ramanujan' graphs, whose eigenvalues are bounded by the spectral radius of their universal cover. Such families were conjectured to exist by Linial and others. In particular, we construct infinite families of (c,d)-biregular bipartite graphs with all non-trivial eigenvalues bounded by $\sqrt{c-1}+\sqrt{d-1}$, for all $c, d \geq 3$.
Our proof exploits a new technique for demonstrating the existence of useful combinatorial objects that we call the "Method of Interlacing Polynomials" (joint work with A. Marcus and D. Spielman).
| Speaker: | Nikhil Srivastava (Microsoft Research, India #9, Lavelle Road Bangalore Karnataka 560025 ) |
| Organiser: | Prahladh Harsha |
| Date: | Monday, 6 May 2013, 16:30 to 17:30 |
| Venue: | AG-80 |
(Scan to add to calendar)
Abstract:
We prove that there exist infinite families of bipartite Ramanujan graphs of every degree bigger than 2. We do this by proving a variant of a conjecture of Bilu and Linial about the existence of good 2-lifts of every graph.
We also construct infinite families of `irregular Ramanujan' graphs, whose eigenvalues are bounded by the spectral radius of their universal cover. Such families were conjectured to exist by Linial and others. In particular, we construct infinite families of (c,d)-biregular bipartite graphs with all non-trivial eigenvalues bounded by $\sqrt{c-1}+\sqrt{d-1}$, for all $c, d \geq 3$.
Our proof exploits a new technique for demonstrating the existence of useful combinatorial objects that we call the "Method of Interlacing Polynomials" (joint work with A. Marcus and D. Spielman).
We also construct infinite families of `irregular Ramanujan' graphs, whose eigenvalues are bounded by the spectral radius of their universal cover. Such families were conjectured to exist by Linial and others. In particular, we construct infinite families of (c,d)-biregular bipartite graphs with all non-trivial eigenvalues bounded by $\sqrt{c-1}+\sqrt{d-1}$, for all $c, d \geq 3$.
Our proof exploits a new technique for demonstrating the existence of useful combinatorial objects that we call the "Method of Interlacing Polynomials" (joint work with A. Marcus and D. Spielman).