If you assume the graph is bipartite (as Cam suggested) and $3-$regular, then I believe the middle eigenvalues are always at most $sqrt{2}$ in absolute value, with the Heawood graph being the only connected graph with equality.
We know that for any positive integer $k$ the number of closed walks on your graph of length $k$ is equal to $Tr(A^k)=sum_i lambda_i^k$. In the case $k=2$, this becomes
$$sum_{i=1}^n lambda_i^2 = 2 |E| = 3 n,$$
while for $k=4$ we have
$$sum_{i=1}^n lambda_i^4 geq 15 n,$$
since there are $9n$ closed walks of the form $x rightarrow y rightarrow x rightarrow z rightarrow x$ (here $y$ possibly can equal $z$), and $6n$ walks of the form $x rightarrow y rightarrow z rightarrow y rightarrow x$ where $z neq x$.
Now suppose that $lambda_i^2 in [t, 9]$ for every $i$. It follows from convexity that, subject to the constraint $sum lambda_i^2=3n$, the sum of $lambda_i^4$ is maximized when every $lambda_i^2$ is either $t$ or $9$, that is to say
$$sum_{i=1}^n lambda_i^4 leq (frac{3-t}{9-t} n) (81) + (frac{6}{9-t} n) (t^2)=(27-6t)n.$$
Comparing with our lower bound, we see $t leq 2$. Equality can only hold when there are exactly $n/7$ eigenvalues equal to $3$ in absolute value, and the rest equal to $sqrt{2}$ in absolute value. This is the spectrum of $n/14$ disjoint copies of the Heawood graph, which is uniquely determined by its spectrum.
It feels like there should be a way of saying that large connected graphs have an eigenvalue much smaller than this, but I don't see how to modify this method to show that (I'm not sure how the connectedness of the graph would show up in path counting). If your graph has many $4$ cycles, you can include them in the $k=4$ lower bound to get a better bound on $t$.
No comments:
Post a Comment