New Ramanujan Graphs!

Posted on May 1, 2013 by Gil Kalai

margulis1

margulis2

Margulis’ paper

Ramanujan graphs were constructed independently by Margulis and by Lubotzky, Philips and Sarnak (who also coined the name). The picture above shows Margulis’ paper where the graphs are defined and their girth is studied. (I will come back to the question about girth at the end of the post.) In a subsequent paper Margulis used the girth property in order to construct efficient error-correcting codes. (Later Sipser and Spielman realized how to use the expansion property for this purpose.)

The purpose of this post is to briefly tell you about new Ramanujan graphs exhibited by Adam Marcus, Daniel Spielman, and Nikhil Srivastava. Here is the paper. This construction is remarkable for several reasons: First, it is the first elementary proof for the existence of Ramanujan graphs which also shows, for the first time, that there are k-regular Ramanujan graphs (with many vertices)  when k is not q+1, and q is a prime power. Second, the construction uses a novel “greedy”-method (with further promised fruits) based on identifying classes of polynomials with interlacing real roots, that does not lead (so far) to an algorithm (neither deterministic nor randomized). Third, the construction relies on Nati Linial’s idea of random graph liftings and verify (a special case of) a beautiful conjecture of Yonatan Bilu and Linial. 

The Ramanujan property

Let us consider the adjacency matrix of a d-regular graph G with n vertices. The trivial eigenvalues of the graph are d and -d; d is always an eigenvalue and -d is an eigenvalue if and only if G is bi-partite. A graph is called a Ramanujan graph if all its nontrivial eigenvalues belong to the interval [-2\sqrt{d-1},+2\sqrt{d-1}]. A theorem of Alon and Boppana asserts that  for every \epsilon>0 there are only finitely many d-regular graphs that all their non-trivial eigenvalues have absolute value less than 2\sqrt{d-1}-\epsilon. Complete graphs and complete bipartite graphs are Ramanujan and the challenge is to find Ramanujan graphs where the degree d is fixed and the number of vertices n is large. The Ramanujan property proofed by Margulis and LPS for their graphs  relies on deep number theory.

Ramanujan graphs are superb expanders. Expander graphs can be defined as d-regular graphs for which all nontrivial eigenvalues belong to the interval [-d(1-t), d(1-t)] where t>0 is fixed. Expander graphs were first defined (using a combinatorial expansion property) by Pinsker who also gave a probabilistic construction. The first explicit construction was achieved by Margulis. The original Ramanujan graphs (both bipartite and not) by Margulis and LPS had degrees which were of the form p+1, where p is a prime. A construction where the degree is q+1 for every prime power q was achieved by Moshe Morgenstern.

2-Lifts and the Bilu-Linial conjecture

Starting from a graph G, a 2-lift of G is obtained by replacing every vertes of G by a pair of vertices, and replacing every edge of G by two disjoint edges among the corresponding new vertices. There are two ways that this can be done. Linial and Bilu showd that the eigenvalues of the new graph are obtained by adding to the eigenvalues of the old graph certain eigenvalues of a \pm matrix which encode the lifting. They conjectured that every d-regular graph has a 2-lifting where all the new eigenvalues are in the interval [-2\sqrt{d-1},+2\sqrt{d-1}]. Markus, Spielman, and Srivastava proved the conjecture for bipartite graphs.

A few words on the proof:

The proof is not difficult and it gives certainly an elementary proof that Ramanujan d-regular graphs exist, and, for the first time, also for every value of d.  The proof relies in a crucial way on the matching polynomial of a graph which was defined by Heilmann and Lieb. The method involves studying interlacing classes of polynomials with real roots. The very basic skeleton of the proof is this: you show that the sum (or average) of all adjacency polynomials for 2-lifts lies in a restricted interval. Then you use the interlacing property to deduce that there is  a single adjacency matrix with the required property. The interval [-2\sqrt{d-1},+2\sqrt{d-1}] is where the eigenvalues of the infinite d-regular tree lies. (This gives a clear motivation for the concept of Ramanujan graphs and various generalizations, including to Ramanujan (high-dimensional) complexes.”) MSS notice a pleasant feature of their proof that the existence of Ramanujan graphs is directly connected to the bounds on the spectral radius of the infinite d-regular tree.

Moore bounds

Let me briefly talk about something else. Let G be a k-regular graph with $n$ vertices and girth g where g is an odd integer. Recall that the girth of a graph is the length of the smallest cycle. We can ask: what is the minimum number of vertices G must have. Put m=(g-1)/2. Let’s look at one vertex v. It has k neighbors, let V_1 be the set of neighbors. Every neighbor in V_1 has k-1 “new” neighbors lets V_2 be the set of all those. We can continue this way and if there are no cycles of length smaller than g all these vertices are different for k=1,2,\dots, m. So we identified $1+k+k(k-1)+\dots+k(k-1)^{m-1}$ different vertices. This gives a lower bound known as “Moore bound”.

Girth (G) \le 2 log_{k-1} n

Erdos and Sachs used the probabilistic method to construct graphs with Girth (G) \ge (1-o(1)) log_{k-1} n.

Margulis’ and LPS’ papers gave a construction of graphs with Girth (G_n) \ge (4/3-o(1)) log_{k-1} n.

What is the truth?

So the correct coefficient is somewhere between 4/3 and 2. What is the truth? Is it possible to construct graphs with Girth (G_n) \ge (2-o(1)) log_{k-1} n?

I am aware of two general arguments (both proposed by Nati Linial) suggesting opposite answers to the question if the right answer is 2 or below 2:

1) [For <2:] The girth problem is analogous to the rate of error correcting codes. Moore bounds is just the volume bound which is usually not asymptotically optimal. Better bound is expected but may require some conceptually new ideas.

2) [For 2:] Regular graphs with large girth are analogous to linear error correcting codes on the infinite regular tree. If you consider the analogue of general codes (drop linearity) then it is easy to reach the 2 upperbound. Usually the behavior of linear and general error correcting codes is similar.

So you can test your own intuition regarding this problem. Unfortunately, a definite answer does not look immanent.

This entry was posted in Combinatorics, Open problems and tagged . Bookmark the permalink.

10 Responses to New Ramanujan Graphs!

  1. Leonid Gurvits says:
    May 1, 2013 at 4:15 pm

    Nice post about very nice paper! The paper is a powerful cheer for the relevance of
    the permanent(actually hafnian) as an analytic tool. This method of stable polynomials
    seems to have some magical power in establishing combinatorial bounds. I came across
    of it when dealing with Van Der Waerden like inequalities around 2003-2004 and very happy to see how far reaching it has become in just a few years.

    Reply
    • Gil Kalai says:
      May 1, 2013 at 9:57 pm

      Thanks, Leonid! Indeed talking with Nati and Doron Puder today, before seeing your comment, Nati remarked that the result and proof method reminds him of your work on Van Der Waerden-like inequalities. Added later: Here is the link for Leonid’s paper

      Reply
      • Leonid Gurvits says:
        May 3, 2013 at 9:52 pm

        Dear Gil, thanks for the link. Two comments on the bipartite case. The averaging formula connecting the matching polynomial and determinants of signed matrices in the bipartite case is a direct corollary of Godsil-Gutman formula expressing the permanent as the
        expectation of the square of the random determinant. In the regular bipartite case a lot is known about the matching polynomial besides its hyperbolicity. For instance, there are
        explicit asymptotically sharp lower bounds on its coefficients: http://arxiv.org/abs/1106.2844
        Those bounds don’t follow from the standard real-roots reasonings like Newton Inequalities, they are essentially of entropic nature and are very related to
        random m-lifts via so called Bethe Approximation.

        So, I wonder whether this new stuff
        can come into the play?

      • Leonid Gurvits says:
        May 4, 2013 at 5:10 am

        One more bipartite observation: Consider d-regular bipartite graph with 2n vertices
        and the corresponding bipartite matching polynomial p(x) of degree n. The roots of
        this polynomial are squares of roots of the original matching polynomial of degree 2n.
        If I am not mistaken, it follows from MSS paper that the largest root of p is very close to
        4(d-1) for large n. One can now apply Newton Inequalities to get upper bounds on
        the coefficients, which will be sharper than, say, those in
        “T. Carroll, D. Galvin and P. Tetali, Matchings and Independent Sets of a Fixed Size in
        Regular Graphs, J. Combin. Theory Ser. A 116 (2009), 1219{1227}”

      • Leonid Gurvits says:
        May 4, 2013 at 10:46 pm

        I was mistaken in my last comment on the roots of bipartite matching polynomial, sorry…
        Just forgot, in the excitement, about the “old” eigenvalues.
        This enlightening post and MSS paper made me think, after some long period, about graph
        spectra and the bounds via infinite trees. The trick reminds the dilation in Hilbert spaces,
        and especially of Sz.-Nagy dilation theorem, which allows very simple infinite dimensional proof of von Neumann theorem on the spectrality of the unit disc, even for finite dimensional operators(aka square matrices). The direct approach is via Herglotz theorem, which is much more involved and, yet, gives much insights.

  2. Pingback: Large Deviations 6 – Random Graphs | Eventually Almost Everywhere

  3. vuhavan says:
    May 2, 2013 at 10:04 pm

    Hi Gil,

    It is a very nice result, I just heard Dan talked about it few weeks ago. On the other hand, it is not a construction
    but an existence proof. Best, Van

    Reply
    • Gil Kalai says:
      May 2, 2013 at 10:16 pm

      Dear Van, of course your are correct. We have here a general operation of 2-lifts, and a proof that by repeating the 2-lift operation we can reach a Ramanujan graphs.

      Reply

  4. Pingback: Local Limits | Eventually Almost Everywhere

  5. Pingback: The Kadison-Singer Conjecture has beed Proved by Adam Marcus, Dan Spielman, and Nikhil Srivastava | Combinatorics and more

Leave a comment