Bounds on Graph Spectra
Graph theory, zeta functions

Bounds on Graph Spectra

 ,

The paper on tree-forest ratios is here https://arxiv.org/abs/2205.10999. While writing this, I needed some reasonable upper bound estimates for the k-th eigenvalue. This is written down separately https://arxiv.org/abs/2205.10968. The second paper proves an surprisingly simple but apparently new inequality \lambda_k \leq d_k + d_{k-1} if \lambda_1=0 \leq \lambda_2 \leq \cdots \leq \lambda_n are the eigenvalues of the Kirchhoff Laplacian of a finite simple graph and where d_1 \leq d_2 \leq \cdots \leq l_n are the vertex degrees of the graph. If you should be in graph spectral research and have seen the inequality, let me know. I might actually make an exception in this case and bother trying to submit this to a journal, hoping for the rare luck that the paper would be looked at by an expert. There is no rush with that. This might take years. The easiest verification of course would be somebody plagiarizing the result. This is the most effective peer review !!! I mentioned in the video below that the proof of the bound d_1 \leq d_2 \leq \cdots \leq l_n could be given as an exercise as it just needs the information that it is true and that it has a simple proof. There are different ways to see the result. I myself had a scare for some time suddenly thinking that the catchy corollary \lambda_k \leq d_k (which is the version shown in the video) is just a consequence of the Gershgorin circle theorem. But Gershgorin’s theorem does not say much in the Kirchhoff case, where the Gershgorin circles are nested.

The main result on trees and forests is that in the Barycentric limit, the exponential growth rate of the number of rooted spanning trees as well as the exponential growth rate of the number of rooted spanning forests exists. We see these values as potential values U(0) or U(-1) of a potential function U. This subharmonic function has the universal density of states as Riesz measure. We understand the one-dimensional case very well as then the tree growth-rate (U(0)=0) and the forest growth rate U(-1)=2 log(golden ratio) are known and the Riesz measure is the equilibrium measure on [0,4] and is also known as the arc-sin distribution. In the two dimensional case, it appears that the spectrum has its support on a Cantor set. As we know that finite approximations are explicitly close to the limiting measure, we could in principle use computer assisted methods to prove rigorously that there are gaps. Very prominent is the gap [4,6] in the dimension 2 (graphs with some triangles K3 but no tetrahedral subgraphs K4). Here are the pictures from the paper:

  • The spectrum in the 2-dimensional case. We see the real and imaginary part of the potential (Lyapunov exponent and integrated density of states in the Schroeinger operator jargon). We see clearly a gap [4,6] and the value of the integrated density of states is 1/2 there.
  • The spetrum in the 1-dimensional case, where the support of the spectrum is the interval [0,4] and the arc-sin distribution there. We again show the potential (which is zero exactly on the interval) and the integrated density of states which is a scaled arc sin function.
The potential theoretic picture in dimension 2 and 1. The Tree index is the potential value at z=0. We see it is zero in the one dimensional case (related to the fact that the number of spanning trees grows polynomially there) and positive in the two dimensional case.
Some Screen Shots from the Movie.

Here is some graphics added in an upgraded version of the paper: