5
$\begingroup$

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.

$\endgroup$
8
$\begingroup$

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.)

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks! Do you have a reference to any exposition of the second result? (apart from the original paper that I linked to) $\endgroup$ – user6818 Feb 6 '15 at 18:10
0
$\begingroup$

This is a comment on Chua KS observation about branched continued fractions and matching polynomials. That these two are related has been observed in an article by Viennot: https://link.springer.com/chapter/10.1007/BFb0076539.

Notice that if $R$ is any of the two regions $[Im(x)>0]$ or $[|x|>2\sqrt{d-1}]$ in $\mathbb{C}$, then the image of $R^n$ by the functions $f_{j,A}=x_j-\sum_{i\in A}\dfrac{1}{x_i}$, where $|A|\leq d-1$, is again contained in $R$.

Using this fact and the observation about matching polynomials and branched continued fractions one can readily prove that matching polynomials are different from zero in both of the regions $[Im(x)>0]$ and $[|x|>2\sqrt{d-1}]$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.