Matching polynomials and Ramanujan graphs

Question

Is it purely coincidental that the same number $2\sqrt{d-1}$ appears in these two following apparently disparate concepts?

• A $d-$regular graph is said to be called Ramanujan if its adjacency eigenvalues except the highest and the lowest are inside the interval, $[-2\sqrt{d-1}, 2\sqrt{d-1}]$. (one considers only one copy of the highest and the lowest if either has multiplicities)

• The largest root of the matching polynomial of a graph with largest degree is $d$ over its vertices, is $2\sqrt{d-1}$

---

• A side question : anyone knows of a pedagogic rewriting/exposition of the second result apart from its original proof in this paper, http://projecteuclid.org/euclid.cmp/1103857921 ?

• A related fact that has been shown recently is that if one assigns elements of $\mathbb{Z}_k$ to the set of oriented edges of a graph ( such that the group element assigned to he edge $(u,v)$ is inverse of the group element assigned to $(v,u)$ ) then over all such signings $s$, one has, $\mathbb{E}_s [ det ( xI - A_{s,i} ) ] = \mu (x)$ where $A_{s,i}$ is the $i-$fold Hadamard product of the signed adjacency matrix $A_s$ and $\mu$ is the matching polynomial of the graph.

Answer 1

One approach that goes some way to explaining this is through the path-tree of a graph. This is defined as follows. Choose a vertex $u$ in the graph $G$, The vertices of the path-tree $T(G,u)$ are the paths in $X$ that start at $u$; two paths are adjacent if one is a maximal proper subpath of the other. If we use $\phi$ to denote the characteristic polynomial and $\mu$ for the matching polynomial and abbreviate $T(G,u)$ to $T$, then we have \[ \frac{\mu(G\setminus u,x)}{\mu(G,x)} = \frac{\mu(T\setminus u,x)}{\mu(T,x)}. \] Here I am using $u$ to denote the one-vertex path in $T(G,u)$ (as well as the vertex in $G$). This identity is useful because the matching and characteristic polynomials of a tree are equal, and so we can study the right side using linear algebra. One consequence is that the largest zero of the matching polynomial of $G$ is equal to the largest zero of the characteristic polynomial of $T$. This yields the bound stated on the largest eigenvalue of the matching polynomial, because the largest eigenvalue of a tree with maximum valency $d$ is $2\sqrt{d-1}$.

The source for this is my paper "Matchings and walks in graphs", J. Graph Theory 5 (1981) 285--297. There is also an exposition in Chapter 6 of my book "Algebraic Combinatorics". (Sorry about the self promotion, but I am not aware of other treatments.)

Answer 2

The moments of the adjacency matrix eigenvalues count closed walks in the graph, while the moments of the matching polynomial roots count tree-like closed walks. When the graph has few short cycles, as in a Ramanujan graph, these sets of walks are both rather similar to closed walks on an infinite $d$-regular tree. This is far from the whole story; see Chris Godsil's book for much more.