Second Largest Eigenvalue of graphs without C4

Question

Given a $d$-regular graph, let $\lambda = \max(|\lambda_2|,|\lambda_n|) $ where $\lambda_i$ are the eigenvalues of its adjacency matrix. Can we show that this value is at most $o(d)$ if the graph is $C_4$-free?

A general bound on the spectrum is shown in this paper here. However this bound is not very useful when $d$ is smaller than a constant. Such a bound is also true in random $d$-regular graphs, where we know that the graphs are almost surely $\lambda \in O(\sqrt{d})$. I am wondering if a weaker bound is true when the graph is $C_4$ free.

Answer 1

There are two ways we can get $\lambda = d$, which negatively answers your question but isn't very satisfying:

• Take any $C_4$-free bipartite $d$-regular graph. Then we have $\lambda_n = -d$.
• Take any $C_4$-free $d$-regular graph with several components. Then we have $\lambda_2 = d$ (and in general, the multiplicity of the eigenvalue $d$ is equal to the number of components).

More generally, $\lambda$ will be close to $d$ when the graph has very poor expansion properties. For example, when $d$ is odd, we can take two copies of a $C_4$-free graph $H$ with degree sequence $(d,d,\dots,d,d-1)$ and then connect the two vertices of degree $d-1$ by an edge. For this graph, $\lambda_2$ will be very close to $d$; intuitively, this is because the vector $\mathbf v$ which is equal to $1$ on one copy of $H$ and $-1$ on the other copy of $H$ is a good approximation of the eigenvector for $\lambda_2$, and $A\mathbf v$ is equal to $d\mathbf v$ in all but two coordinates.

---

Actually, the spectral result in the paper by Babai and Guiduli does not help here even when $d$ is large. This is due to a notation conflict.

• In the case of $d$-regular graphs, the adjacency matrix always has a largest eigenvalue of $d$ and so we define $\lambda = \max\{|\lambda_2|, |\lambda_n|\}$. When this is small, the graph has good expansion properties.
• In the case of general graphs, even the largest eigenvalue is unknown. So Babai and Guiduli let $\lambda = \max\{|\lambda_1|, |\lambda_n|\}$. (Actually, $\lambda = \lambda_1$.) This doesn't tell us about the expansion properties; as the introduction mentions, the result is a generalization of an upper bound on the number of edges in the graph, via the inequality $2m/n \le \lambda$.