Eigenvalue bounds of the Kirchhoff Laplacian
We prove that each eigenvalue l(k) of the Kirchhoff Laplacian K of a graph or quiver is bounded above by d(k)+d(k-1) for all k in {1,...,n}. Here l(1),...,l(n) is a non-decreasing list of the eigenvalues of K and d(1),..,d(n) is a non-decreasing list of vertex degrees with the additional assumption d(0)=0. We also prove that in general the weak Brouwer-Haemers lower bound d(k) + (n-k) holds for all eigenvalues l(k) of the Kirchhoff matrix of a quiver.
\section{The theorem}

\paragraph{}
Let $G=(V,E)$ be a {\bf finite simple graph} with $n$ vertices.
Denote by $\lambda_1 \leq \lambda_2 \leq \cdots \leq \lambda_n$ the ordered
list of eigenvalues of the {\bf Kirchhoff matrix} $K=B-A$, where $B$ is the
diagonal vertex degree matrix with ordered vertex degrees
$d_1 \leq d_2 \leq \cdots \leq d_n$ and where $A$ is the adjacency matrix of $G$. 

\paragraph{}
We assume $d_0=0$ so that $d_1+d_0=d_1$ and prove

\begin{thm} $\lambda_k \leq d_k+d_{k-1}$, for all $1 \leq k \leq n$.  \label{1} \end{thm}

The case $d=n$ is the {\bf spectral radius} estimate 
$\lambda_n \leq d_n+d_{n-1}$ of Anderson and Morley \cite{AndersonMorley1985}
which we will use in the proof. The case $k=1$ is obvious because $\lambda_1=0$
and $k=2$ is a special case of the Schur-Horn 
inequality \cite{Brouwer} as $\lambda_2 = \lambda_1+\lambda_2 \leq d_1+d_2$. 
Already the case $\lambda_3 \leq d_3+d_2$ appears to be new as it goes beyond the 
Schur-Horn inequality. Note that any estimate on the spectral radius $\lambda_n$
provides upper bounds on $\lambda_k$ and there are many improvements since
the ground breaking Anderson-Morley paper
\cite{GroneMerrisSunder1,GroneMerrisSunder2,Zhang2004,Das2004,
Guo2005,Shi2007,ShiuChan2009, LiShiuChan2010,ZhouXu}.
They would give better upper bounds also for $\lambda_k$
but look less elegant. 

\paragraph{}
Already the corollary $\lambda_k \leq 2d_k$ is stronger than 
what the {\bf Gershgorin circle theorem} 
\cite{Gershgorin,GershgorinAndHisCircles}
gives in this case: the circle theorem provides in every interval $[0,2d_k]$ at 
least one eigenvalue $\lambda_l$ of $K$. It does not need to be the k'th one.
In the Kirchhoff case, where the Gershgorin circles are nested, 
$0$ is always in the spectrum. Theorem~(\ref{1}) gives more information. 
The spectral data $\lambda_1=0,\lambda_2=10,\lambda_3=10$ for example are 
Gershgorin compatible to $d_1=1, d_2=3, d_3=7$ because there is 
an eigenvalue in each closed ball $[0,2], [0,6]$ and $[0,14]$. 
But these data contradict Theorem~(\ref{1}) as
$\lambda_2 = 2 d_2+4$. Theorem~\ref{1} keeps the eigenvalues more 
aligned with the degree sequence, similarly as the Schur-Horn theorem does.

\paragraph{}
An application is that the pseudo determinant ${\rm Det}(K)= \prod_{k=2}^n \lambda_k$ 
which by the Kirchhoff-Cayley {\bf matrix tree theorem} count
the number of rooted spanning trees has an upper bound $2^n \prod_k d_k$
and that ${\rm det}(1+K)$ by the Chebotarev-Shamis matrix forest theorem
count the number of rooted spanning forests has an upper bound $2^n \prod_k (1+d_k)$. 
These determinant inequalities do not follow from the Gershgorin nor from the 
Schur-Horn inequalities. We like to rephrase the determinant
bounds as bound on the spectral potential 
$U(z)=(1/n) \log \det(K-z) \leq 2 + (1/n) \log\det(M-z)$,
where $M={\rm Diag}(d_1,\dots,d_n)$ is the diagonal matrix and $z \leq 0$ is real. 
We made use of Theorem~(\ref{1}) to show that $U(z)$ has a Barycentric limit. It bounds the 
potential $U$ of the interacting system with the potential $(1/n) \log\det(M-z)$ of the non-interacting 
system where $M$ can be thought of as the Kirchhoff matrix of a non-interacting system where we have
$d_k$ self-loops at vertices $k$, even-so the tree and forest interpretations do not make sense any more.

\section{The proof}

\paragraph{}
If we make he statement slightly stronger, also the induction assumption becomes
more powerful. Let $\mathcal{K}$ the class of symmetric matrices which are obtained
as principal submatrices of a Kirchhoff matrices of a finite simple graph 
obtained by deleting the rows and columns to a maximal diagonal entry.
In other words, we close the class of Kirchhoff matrices under the operation of taking 
principal submatrices. The stronger statement is that for all $A \in \mathcal{K}$, 
the eigenvalues $\lambda_k$ and diagonal entries $d_k$, when ordered in an ascending order, 
satisfy $\lambda_k \leq d_k+d_{k-1}$. 

\paragraph{}
The class $\mathcal{K}$ is invariant under
the operation $\phi$ which removes corresponding rows and columns. This allows induction. 
The induction foundation $n=1$ is obvious because the result holds for any 
$1 \times 1$ matrix with non-negative entries. For $2 \times 2$ matrices 
$K=\left[ \begin{array}{cc} d_1 & -t \\ -t & d_2 \end{array} \right]$ we have
with the trace $T=d_1+d_2$ the eigenvalue $\lambda_2= (T+\sqrt{T^2+4t^2-4d_1 d_2})/2$
which is $\leq T=d_1+d_2$ if $t \leq \sqrt{d_1 d_2}$ and especially if $t \leq d_1$. 

\paragraph{}
The induction step uses the {\bf Cauchy interlace theorem} or {\bf Separation theorem}
\cite{HornJohnson2012}:
if $\mu_k$ are the eigenvalues of $\phi(K)$, then $\lambda_k \leq \mu_k \leq \lambda_{k+1}$. 
(The interlace theorem follows from the {\bf Hermite interlace theorem} for real polynomials 
\cite{Hwang2004,Fisk2005}. If $f$ is a monic polynomial of degree $n$ with real roots 
$\lambda_1 \leq \cdots \leq \lambda_n$
and $g$ is a monic polynomial of degree $n-1$ with real roots 
$\mu_1 \leq \cdots \leq \mu_{n-1}$ then
{\bf $g$ interlaces $f$} if 
$\lambda_1 \leq \mu_1 \leq \lambda_2 \leq \cdots \leq \mu_{n-1} \leq \lambda_n$. 
Equivalent for $f$ and $g$ to interlace is that the interpolation $t f+(1-t)g$ 
has real roots for all $t \in [0,1]$.) 

\paragraph{}
The interlace theorem does not catch the largest eigenvalue $\lambda_n$. 
This requires an upper bound
for the {\bf spectral radius}. 
This is where Anderson and Morley \cite{AndersonMorley1985} come in.
They realized that $K=F^* F$ is essentially isospectral to $F F^*$. 
The later is the adjacency matrix of the line graph but with the modification
that all diagonal entries are $2$. Since the row or column sum
of $F F^*$ is bound by $d_k(a) + d_k(b)$ for any edge $(a,b)$, 
the upper bound holds. But we need to extend this estimate to $\mathcal{K}$. 

\begin{lemma}[Upgrade of Anderson and Morley] 
For any matrix in $\mathcal{K}$, the spectral radius 
satisfies $\lambda_n \leq d_n + d_{n-1}$. 
\end{lemma}

\paragraph{}
We can assume that after a coordinate change 
the diagonal entries of $K \in \mathcal{K}$ are ordered. This simply requires to 
order the vertices compatible with the order of the $d_j$. 
\cite{AndersonMorley1985} estimate $\lambda_n \leq d_n+d_{n-1}$ 
for Kirchhoff matrices and even show that 
$\lambda_n \leq {\rm  max}_{(a,b) \in E(G)} d(a)+d(b)$. 
We now verify that this extends to $\mathcal{K}$.

\paragraph{}
We have already seen the induction assumption for $n=1$ and $n=2$.
Let $K$ be a $n \times n$ matrix in $\mathcal{K}$ and assume we know 
the answer already for all $(n-1) \times (n-1)$ matrices in $\mathcal{K}$. 
When taking a principal submatrix of $K$ by deleting
the first row and first column, we do not change $d_n$ nor $d_{n-1}$. 
The reason is that decoupling the
lowest degree vertex does not change the largest two diagonal elements.
The upper bound $d_n+d_{n-1}$ is therefore not affected. 

\paragraph{}
Let $\mu_1 \leq \mu_2 \leq \cdots \leq \mu_{n-1}$ be the eigenvalues of the principal
submatrix where the first row and column are deleted. 
The Cauchy interlacing result gives $\lambda_{n-1} \leq \mu_{n-1} \leq \lambda_n$
The largest eigenvalue $\mu_{n-1}$ of the deformed matrix is smaller or equal than than
the largest eigenvalue $\lambda_n$ and so smaller or equal than 
$d_n + d_{n-1}$. The inequality $\mu_{n-1} \leq d_n + d_{n-1}$ is what we wanted to show.

\paragraph{}
One could also explicitly track how the  maximal eigenvalue decreases 
if all the non-diagonal entries in the first row and column is multiplied by $t$. 
If $v$ is the normalized eigenvector to the largest eigenvalue $\lambda_n$, 
then since the matrices are symmetric, $v$ is perpendicular to 
$[1,1,\dots, 1,1]$ the eigenvector to $\lambda_1=0$.  
This implies $\sum_{k=1}^{n-1} v_k = -v_1$. Let now $E$ be the matrix in 
which the first row and first column except $E_{11}$ contains only 1 and 
everything else is zero. We need to understand how 
$K - t E$ changes the largest eigenvalue $\lambda$. 
The {\bf first Hadamard deformation formula} gives $\lambda(t)' = v^T E v = v_1^2>0$.
The {\bf second Hadamard deformation formula} would even show $\lambda(t)''>0$, 
illustrating {\bf eigenvalue repulsion}. In any case, the largest eigenvalue increases
under the deformation. Since at $t=1$, the end of the deformation, 
we have $\lambda_n \leq d_n+d_{n-1}$ this is also the case for 
$t=0$, where the connections to the weak vertex link have all been capped. 

\begin{comment}
s = RandomGraph[{20, 50}]; 
a = RandomChoice[VertexList[s]];
S = VertexList[NeighborhoodGraph[s, a]];
A = Normal[KirchhoffMatrix[s]];
Q[t_]:=Module[{U = A},Do[U[[a, S[[k]]]] = -t; U[[S[[k]], a]] = -t, {k, Length[S]}]; U]
F[t_]:=Module[{}, B = Q[t]; l = Max[Sort[N[Eigenvalues[B]]]];
  d = Sort[Table[B[[k, k]], {k, Length[B]}]]; 
  d1 = Prepend[Delete[d, Length[d]], 0]; l]
Plot[F[t], {t, 0, 1}]
\end{comment} 

\section{Remarks}

\paragraph{}
Similarly than the Schur-Horn inequality
$\sum_{j=1}^k \lambda_j \leq \sum_{j=1}^k d_j$ 
which is true for any symmetric matrix with diagonal entries $d_j$, 
Theorem~(\ref{1}) controls how close the ordered eigenvalue sequence
is to the ordered vertex degree sequence. But it is different.
For example, if the eigenvalues increase exponentially like $\lambda_k = 6^k$, then 
the inequality $\lambda_k \leq 2 d_k$ implies 
on a logarithmic scale $\log(\lambda_k) \leq \log(2) + \log(d_k)$. Schur-Horn does
not provide that. As for the {\bf Gershgorin circle theorem}, it
would only establish $\log(\lambda) \leq \log(2) + \log(d_n)$, 
where $d_n$ is the largest entry because the theorem assures only that in each 
Gershgorin circle, there is at least one eigenvalue.

\paragraph{}
Anderson and Morley \cite{AndersonMorley1985} have the better bound 
$\max_{(x,y) \in E} d(x) + d(y)$ and Theorem~(\ref{1}) could be improved in that
$d_k+d_{k-1}$ can be replaced by ${\rm max}_{(x,y) \in E} d_k+d_j$. 
Any general better upper bound of the spectral radius leads to better results.
The Anderson-Morley estimate as an early use of a {\bf McKean-Singer super symmetry}
\cite{McKeanSinger} (see \cite{knillmckeansinger} for graphs). 
in a simple case where one has only $0$-forms and $1$-forms. There, it reduces to
the statment that  $K=F^* F$ is essentially isospectral to $F F^*$ which is true for 
all matrices. It uses that the Laplacian $K$ is of the form $F^* F = {\rm div} {\rm grad}$,
where $F={\rm grad}$ is the {\rm incidence matrix} $F f( (a,b) ) = f(b)-f(a)$ for functions
$f$ on vertices (0-forms) leading to functions on oriented edges (1-form). 

\paragraph{}
There is much work on the spectral radius of the Kirchhoff Laplacian. It is bounded above
by the spectral radius of the {\bf signless Kirchhoff Laplacian} $|K|$ in which one takes the
absolute values for each entry.  This matrix is a non-negative matrix in the connected case
has a power $|K|^n$ with all positive entries so that by the Perron-Frobenius theorem, the
maximal eigenvalue is unique. (The Kirchhoff matrix itself of course can have multiple maximal 
eigenvalues like for the case of the complete graph). Also, unlike $K$ which is never 
invertible $|K|$ is invertible if $G$ is not bipartite. 
If we treat a graph as a one-dimensional simplicial complex 
(ignoring 2 and higher dimensional simplices in the graph), and denote $d$ 
the exterior derivative of this skeleton complex, then 
$(d+d^*)^2 = K_0 + K_1$ where $K=K_0=d^* d$ is the Kirchhoff matrix and $K_1=d d^*$ is the 
one-form matrix with the same spectral radius. This leads to \cite{AndersonMorley1985}.
Much work has gone in improving this 
\cite{BrualdiHoffmann,Stanley1987,LiZhang1997,Zhang2004,FengLiZhang,Shi2007,LiShiuChan2010}.
We have used that an identity coming from connection matrices \cite{Hydrogen}.


\paragraph{}
We stumbled on the theorem when looking for bounds on the {\bf tail distribution} 
$\mu([x,\infty))$ of the {\bf limiting density of states} 
$\mu$ of the Barycentric limit $\lim_{n \to \infty} G_n$ of a 
finite simple graph $G=G_0$, where $G_n$ is the Barycentric 
refinement of $G_{n-1}$ in which the complete subgraphs 
of $G_{n-1}$ are the vertices and two are connected if one is contained
in the other  \cite{KnillBarycentric,KnillBarycentric2}. 
We wanted a {\bf potential} $U(z) = \int_0^{\infty} \log(z-w) \; d\mu(w)$ because
$U(-1)$ measures the exponential growth of rooted spanning trees while $U(0)$ measures
the exponential growth of the rooted spanning forests. 


The connection is
that in general, the {\bf pseudo determinant}  \cite{cauchybinet}
${\rm Det}(K)=\prod_{\lambda \neq 0} \lambda$ 
is the number of {\bf rooted spanning trees} in $G$ by 
the {\bf Kirchhoff matrix tree theorem} and 
${\rm det}(1+K)$ is the number of rooted spanning forests in $G$
by the {\bf Chebotarev-Schamis matrix forest theorem} 
\cite{ChebotarevShamis1,ChebotarevShamis2,Knillforest}. All these relations follow directly
from the {\bf generalized Cauchy-Binet theorem} that states
that for any $n \times m$ matrices $F,G$, one has the pseudo determinant version
${\rm Det}(F^T G) = \sum_{|P|=k} \det(F_P) \det(G_P)$ with $k$ depends on $F,G$ and
$\det(1+x F^T G) = \sum_P x^{|P|} \det(F_P) \det(G_P)$.
{\bf Pythagorean identities} like ${\rm Det}(F^T F) = \sum_{|P|=k} \det^2(F_P)$
and $\det(1+F^T F) = \sum_P \det^2(F_P)$ follow for an arbitrary $n \times m$ matrix $F$.
Applied to the {\bf incidence matrix} $F$ of a connected graph, where $k(A)=n-1$ is the rank of $K=F^T F$,
the first identity counts on the right spanning trees and the second identity counts on the right
the number of spanning forests

\paragraph{}
Having noticed that the 
{\bf tree-forest ratio} 
$\tau(G)={\rm Det}(1+K)/{\rm Det}(K)=\prod_{\lambda \neq 0} (1+1/\lambda)$ 
has a Barycentric limit $\lim_{n \to \infty} (1/|G_n|) \log(\tau(G_n))$,
we interpreted this as $U(-1)-U(0)$ requiring the normalized potential 
to exist. By the way, for complete graphs $G=K_n$ the tree-forest 
ratio is $(1+1/n)^{n-1}$ and converges to 
the {\bf Euler number} $e$. For triangle-free
graphs, $\log(\tau(G_n))/|V(G_n)|$ converges to $\log(\phi^2)$, where
$\phi$ is the {\bf golden ratio}. 
For example, for $G=C_n$, where ${\rm Det}(K)=n^2$ and the number of rooted spanning forests is
the alternate {\bf Lucas number} recursively given by 
$L(n+1) = 3 L(n)-L(n-1)+2, L(0)=0,L(1)=1$.  
We proved in general that $\log(\tau(G_n))/|V(G_n))|$ converges under 
{\bf Barycentric refinements} $G_0 \to G_1 \to G_2 \dots$
for arbitrary graphs to a universal constant that only 
depends on the maximal dimension of $G=G_0$. 

\paragraph{}
Theorem~(\ref{1}) needs to be placed in the context of the
spectral graph literature like 
\cite{Biggs,VerdiereGraphSpectra,Godsil,Brouwer,Chung97,DvetkovicDoobSachs,Spielman2009} 
or articles like \cite{Guo2005,Stephen,GroneMerrisSunder}. 
Most research work in this area has focused on small
eigenvalues like $\lambda_2$ or large 
eigenvalues like the spectral radius $\lambda_n$. For $\lambda_2$, 
there is a {\bf Cheeger estimate} $h^2/(2d_n) \leq \lambda_2 \leq h$ 
for the eigenvalue $\lambda_2$ and Cheeger constant 
$h=h(G)$ \cite{Cheeger1970} first defined for Riemannian manifolds, 
meaning in the graph case that one needs remove $h |H|$ edges 
to remove a subgraph $H$ from $G$. 
For the largest eigenvalue $\lambda_n$ the Anderson-Morley bound 
has produced an industry of results. 

\paragraph{}
Let us look at some example. Figure~\ref{(1)} shows more visually
what happens in some examples of graphs with $n=10$ vertices. \\
a) For the cyclic graph $C_4$, the Kirchhoff 
eigenvalues are $\lambda_1=0,\lambda_2=2,\lambda_3=2,\lambda_4=4$
and the edge degrees are $d_1=d_2=d_3=d_4=2$. \\
b) For the star graph with $n-1$ spikes, the eigenvalues are 
$\lambda_1=0,\lambda_2= \cdots \lambda_{n-1}=1,
\lambda_n=n$ while the degree sequence is 
$d_1=\cdots = d_{n-1}=1, d_n=n$. \\
c) For a complete bipartite graph $K_{n,m}$ with $m \leq m$, 
we have $0 \leq m \leq \cdots \leq m \leq n \cdots n$ with 
$m-1$ eigenvalues $m$ and $n-1$ eigenvalues $n$. The degree sequence
has $m \leq m \leq \cdots \leq m \leq n \leq \cdots \leq n$ with 
$m$ entries $m$ and $n$ entries $n$. 

\paragraph{}
From all the $38$ isomorphism classes of connected graphs with $4$ vertices, 
there are only $3$, for which equality holds in Theorem~(\ref{1}) and $7$ for 
which $\lambda_k = 2 d_k$. From the $728$ 
isomorphism classes of connected graphs with $5$ vertices, there are none for 
Theorem~(\ref{1}) and $5$ for $\lambda_k = 2 d_k$.
From the $26704$ isomorphism classes of connected graphs with $6$ vertices, 
there are $70$ for which Theorem~(\ref{1}) has equality and $76$ for which 
$\lambda_k = 2 d_k$. It is always only the largest eigenvalue, where we have seen
equality $\lambda_n=2d_n$ to hold. 

\paragraph{}
The theorem implies  $\sum_{j=1}^k \lambda_j \leq 2\sum_{j=1}^k d_j$ which is
weaker than the Schur-Horn inequality $\sum_{j=1}^k \lambda_j \leq \sum_{j=1}^k d_j$.
The later result is of wide interest.
It can be seen in the context of partial traces 
\cite{TaoSchurHorn} $\sum_{j=1}^k \lambda_j = {\rm inf}_{dim(V)=k} {\rm tr}(A|V)$ and is
special case of the {\bf Atiyah-Guillemin-Sternberg convexity theorem} 
\cite{Atiyah1982,GuilleminSternberg1982}. The Schur inequality has been 
sharpened a bit for Kirchhoff matrices to 
$\sum_{j=1}^k \lambda_j \leq \sum_{j=1}^k d_j-1$ \cite{Brouwer} 
Proposition 3.10.1. 

\paragraph{}
There is a general lower bound $\lambda_k \geq d_k-(n-k)+1$
which had been conjectured of Guo \cite{Guo2007} 
and is now a theorem \cite{BrouwerHaemers2008} (see also \cite{Brouwer} Proposition 3.10.2.). 
This Brouwer-Haemers estimate from 2008 generalizes $\lambda_n \geq d_n+1$  
\cite{GroneMerrisSunder2} $\lambda_{n-1} \geq d_{n-1}$ (\cite{LiPan1999} and 
$\lambda_{n-2} \geq d_{n-2}-1$ \cite{Guo2007}. 
It follows also from $K=-A+B$ with $B={\rm Diag}(d_1,\cdots d_n)$ positive semi definite
that $\lambda_k(K) \geq \lambda_k(-A)$ \cite{HornJohson2012} (Corollary 4.3.12). 

\paragraph{}
Unlike the Schur-Horn inequality, Theorem~(\ref{1}) does not extend to general 
symmetric matrices. Already for $A=\left[ \begin{array}{cc} 1 & 3 \\ 3 & 1 \end{array} \right]$
which has eigenvalues $\lambda_1=-2, \lambda_2=4$ and with $d_1=1,d_2=1$, the inequality
$\lambda_2 \leq 2 d_2$ fails. It also does not extend to symmetric matrices
with non-negative eigenvalues, but also this does not work as
$A=\left[ \begin{array}{ccc} 1 & 1 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \end{array} \right]$ shows, 
as this matrix has eigenvalues $0,0,3$ and diagonal entries $1,1,1$. The case of $n \times n$
matrices with constant entries $1$ is an example with eigenvalues $0$ and $n$ showing that no
estimate $\lambda_n \leq C d_n$ is in general possible for symmetric matrices even when 
asking the diagonal entry to dominate the other entries. 

\section{Open ends}

\paragraph{}
Theorem~(1) also would follow from the statement
\begin{equation} \sum_{j=1}^k d_j 
- \sum_{j=1}^k \lambda_j \leq d_{k}  
\end{equation}
which would be of independent interest as it 
estimates the {\bf Schur-Horn error}.  Indeed, the Schur-Horn gives together
with such a hypothetical error bound $0 \leq \sum_{j=1}^k d_j - \sum_{j=1}^k \lambda_j  
+ d_{k+1}-\lambda_{k+1} \leq d_k+ d_{k+1} - \lambda_{k+1}$,
which is $\lambda_k \leq d_k+d_{k+1}$. Can we prove the above
Schur-Horn error estimate (1)? We do not know yet but our experiments 
indicate: \\

{\bf Conjecture A:} [Schur-Horn error]  Estimate (1) holds for all finite simple graphs

\paragraph{}
We have mentioned the Brouwer-Haemers bound $\lambda_k \geq d_k-(n-k)+1$
which is very good for large $k$ but far from optimal for smaller $k$. (Note that
part of the graph theory literature labels the eigenvalues in decreasing order.
We use an ordering more familiar in the manifold case, where one has no largest 
eigenvalue and which also appears in the earlier literature like 
\cite{HornJohnson2012}.) The guess $d_{k-1}/2 \leq \lambda_k$ 
assuming $d_{-1}=0$ is a {\bf rule of thumb}, as it fails only in rare cases. 
The next thing to try is $d_{k-2}/2 \leq \lambda_k$ and this is still wrong 
in general but there are even less counter examples.
We can try $d_{k-2}/3$ for which we have not found a counter example yet but
it might just need to look for larger networks to find a counter example. 
We still believe that there is an affine lower bound. This is based only on
limited experiments like for $A=1/3$ where it already looks good.  

{\bf Conjecture B:} [Affine Brouwer-Haemers bound] 
There exist constants $0<A<1$ and $B$
such that for all graphs and $1 \leq k \leq n$ we have
$A d_k - B \leq \lambda_k$. 

\paragraph{}
We see for many Erd\"os-R\'enyi graphs that an upper bound 
$\lambda_k \leq C d_k$ holds for most graphs
for any $C>1$, if the graphs are large. A possible conjecture is that \\

{\bf Conjecture C:} [Linear bound for Erdoes-Renyi] 
For all $C>1$ and all $p \in [0,1]$, the probability of the
set of graphs in the Erd\"os-R\'enyi probability space 
$E(n,p)$ with $\lambda_k \leq C d_k$ for all $1 \leq k \leq n$ 
goes to $1$ for $n \to \infty$. 

\section{Illustration}

\paragraph{}
Here are a few examples of spectra with known upper and 
lower bounds:

\begin{figure}[!htpb]
\scalebox{0.6}{\includegraphics{figures/stargraph.pdf}}
\scalebox{0.6}{\includegraphics{figures/cyclegraph.pdf}}
\scalebox{0.6}{\includegraphics{figures/lineargraph.pdf}}
\scalebox{0.6}{\includegraphics{figures/wheelgraph.pdf}}
\scalebox{0.6}{\includegraphics{figures/completegraph.pdf}}
\scalebox{0.6}{\includegraphics{figures/bipartite.pdf}}
\scalebox{0.6}{\includegraphics{figures/petersen.pdf}}
\scalebox{0.6}{\includegraphics{figures/gridgraph.pdf}}
\scalebox{0.6}{\includegraphics{figures/randomgraph.pdf}}
\label{Spectra}
\caption{
This figure shows examples of spectra and compares them
with known upper and lower bounds. 
We see first the {\bf Star, Cycle and Path graph}, then 
the {\bf Wheel, Complete, Bipartite graph},
and finally the {\bf Petersen, Grid and Random graph},  
all with $10$ vertices. The eigenvalues are outlined thick (in red).
Above we see the upper bound (in blue) as proven in the present 
paper. Then there are the Brouwer-Haemers and Horn-Johnson lower 
bounds which, as the examples show, do not always compete 
but complement each other.
}
\end{figure}

\bibliographystyle{plain}

2022-05-27T02:04:52.000
2205
2205.10968
en
https://arxiv.org/abs/2205.10968
We prove that each eigenvalue l(k) of the Kirchhoff Laplacian K of a graph or quiver is bounded above by d(k)+d(k-1) for all k in {1,...,n}. Here l(1),...,l(n) is a non-decreasing list of the eigenvalues of K and d(1),..,d(n) is a non-decreasing list of vertex degrees with the additional assumption d(0)=0. We also prove that in general the weak Brouwer-Haemers lower bound d(k) + (n-k) holds for all eigenvalues l(k) of the Kirchhoff matrix of a quiver.
Combinatorics (math.CO); Discrete Mathematics (cs.DM)
Eigenvalue bounds of the Kirchhoff Laplacian
Qwen/Qwen-72B
1. YES
2. YES