The spectral radius of a simple graph

Dynkin diagrams and the Mahler measure problem »

The spectral radius of a simple graph

April 30, 2009 by Qiaochu Yuan

I’ve decided not to port over the posts from AoPS. Among other things, I’d prefer to preserve the comments on older posts as they are.

So here’s something I’ve been thinking about. Given a simple connected graph $G$ , define $\rho(G)$ to be its largest positive eigenvalue; in other words, if $w_n$ counts the number of walks (equivalently, closed walks) of length $n$ on $G$ , then

$\displaystyle \rho(G) = \limsup_{n \to \infty} \sqrt[n]{w_n}.$

(The limit of the ratio between consecutive terms won’t work if, for example, $G$ is bipartite.) There are a couple of ways to see that the largest positive eigenvalue also bounds the absolute value of the negative eigenvalues: one is by the Perron-Frobenius theorem, but really it suffices to observe that $w_n$ is always a non-negative integer. Hence $\rho$ is the spectral radius of the adjacency matrix.

For most graph theorists, it’s more natural to talk about the spectral radius of the Laplacian, and there appears to be a general consensus that the Laplacian is both more interesting and more useful. But I’ve always had a soft spot for the adjacency matrix, so this is what this post is going to be about. Recently I’ve been playing around with small values of the spectral radius.

Property 1: The spectral radius of an undirected graph cannot lie in $(1, \sqrt{2})$ .

Proof. If $G$ has no edges, we are done. Suppose no two edges of $G$ are incident to the same vertex; then the number of closed walks of length $n$ is zero if $n$ is odd and twice the number of edges if $n$ is even; thus the only eigenvalues are $1, -1$ and $\rho(G) = 1$ .

Now suppose there are two edges incident to the same vertex.

Lemma (subgraph bound): Let $G$ be a graph, and let $H$ be a subgraph of $G$ . Then $\rho(G) \ge \rho(H)$ .

Proof. Every (closed) walk on $H$ is a (closed) walk on $G$ .

Back to Property 1. Now, the graph consisting of two edges connecting three vertices is the path graph $P_3$ , and its eigenvalues are $0, \sqrt{2}, -\sqrt{2}$ , which one can see as follows: the number of closed walks of length $n$ from the center vertex to itself is $0$ if $n$ is odd and $2^{ \frac{n}{2} }$ if $n$ is even, since a closed walk is just a choice of which of the two other vertices to visit every other step. It follows that $\rho(G) \ge \sqrt{2}$ .

More generally, it turns out that the subgraph bound implies that spectral radii are discretized, at least up to a point.

Property 2: The only connected simple graphs $G$ with $\rho(G) < \sqrt{3}$ are the path graphs $P_1, P_2, P_3, P_4$ .

Proof. The star graph $S_k$ satisfies $\rho(S_k) = \sqrt{k}$ , which is easily verified by counting the number of closed walks from the center vertex to itself. It follows by the subgraph bound that a graph with $\rho(G) < \sqrt{3}$ has no vertices of degree $3$ . Similarly, the cycle graphs $C_k$ all satisfy $\rho(C_k) = 2$ , since they are $\ 2$ -regular, so by the subgraph bound $G$ is acyclic. These two conditions ensure that $G$ consists of a single path graph $P_n$ . (Note that $S_2 = P_3$ .)

The path graphs satisfy $\rho(P_n) = 2 \cos \frac{\pi}{n+1}$ , which we will not prove here. It turns out that the characteristic polynomials of the corresponding adjacency matrices are the Chebyshev polynomials of the second kind, which is quite interesting in its own right, but that’s another story. Since $2 \cos \frac{\pi}{6} = \sqrt{3}$ , it follows that $n < 5$ .

The above proof actually had to prove something stronger: if a graph with $\rho(G) < 2$ is acyclic, we might ask if this discreteness in the behavior of the spectral radius continues to hold at least up to radius $\ 2$ . We can’t hope for discreteness after $\ 2$ , since the path graphs satisfy $\rho(P_n) < 2$ but $\lim_{n \to \infty} \rho(P_n) = 2$ ; in other words, $\ 2$ is a limit point of the set of spectral radii. But we can prove that there aren’t any smaller ones.

Property 3: For every $\epsilon > 0$ , the set of connected simple graphs with $\rho(G) < 2 - \epsilon$ is finite.

The following lemma will be useful.

Lemma: If $G$ is a connected simple graph with $\rho(G) < 2$ , then $G$ is a binary tree.

Proof. We know that $G$ must be acyclic. The graph on five vertices consisting of a vertex of degree $\ 4$ and four other vertices also has spectral radius $\ 2$ : the number of closed walks of length $n$ from the center vertex to itself is $0$ if $n$ is odd and $4^{ \frac{n}{2} }$ if $n$ is even. Again, it follows by the subgraph bound that the vertices of $G$ have degree at most $3$ . (If we fix a root not of degree $3$ , we obtain the usual “picture” of a binary tree.)

Back to Property 3. Let $G$ be a binary tree and fix a root (which can be any vertex not of degree $3$ ). If $\rho(G) < 2 - \epsilon$ , then there exists $n$ such that $G$ cannot contain $P_n$ as a subgraph. Quantitatively, since

$\displaystyle 2 - 2 \cos \frac{\pi}{n+1} \approx \frac{\pi^2}{2 \cdot (n+1)^2}$

it follows that the largest value of $n$ such that $G$ can contain $P_n$ as a subgraph satisfies

$\displaystyle n \approx \sqrt{ \frac{\pi^2}{2 \epsilon} }$ .

So as a binary tree $G$ has height at most $n$ . But a binary tree of height $n$ has at most $2^{n+1} - 1$ vertices, so there are finitely many such graphs. This also implies that the set of their spectral radii is finite.

So here are some questions:

1. The proof above shows that the maximum number of vertices of a graph $G$ with $\rho(G) < 2 - \epsilon$ is $O(c^{ \sqrt{1/\epsilon} })$ , which is probably a very loose bound. What is a sharp bound? What is a bound on the number of (labeled) connected simple graphs with this property?

2. The sequence of spectral radii less than $\ 2$ begins $0, 1, \sqrt{2}, \phi = 2 \cos \frac{\pi}{5}, \sqrt{3}, ...$ . Does it have interesting properties? (I am thinking of a vague analogy with the Beraha constants.)

3. The characteristic polynomial of a symmetric matrix with integer coefficients is monic with integer coefficients, and in addition all of its roots are real. I have been told that not every such polynomial occurs as the characteristic polynomial of a symmetric matrix; to what extent is this for “graph-theoretic” reasons? Put another way, to what extent are the above results true for any monic polynomial with integer coefficients and real roots? (“Spectral radius” should be interpreted as meaning the largest root in absolute value.)

About these ads

Posted in combinatorics, graph theory | Tagged walks on graphs | 3 Comments

3 Responses

on May 1, 2009 at 4:13 pm | Reply José P. [metafor]

The font/color scheme makes your post not so easy on the eyes; aside from that, c’est magnifique!
on May 7, 2009 at 6:34 pm | Reply kai

qc, help me. i just took an ib test for math hl. there are three parts (in three days). i just finished with day 1. it was horrible. please, fly over back to bellevue and take the rest of the test for me T_T.

btw, i will one day understand what you just posted. i will…
on April 27, 2010 at 9:20 pm | Reply The McKay correspondence I « Annoying Precision

[...] the representation graphs introduced in this blog post to something I blogged about in the very first and second posts in this blog! The result will be a beautiful connection between the finite [...]

Comments RSS

	Le lemme de Yoneda e… on The Yoneda lemma I
	Qiaochu Yuan on Irreducible components
	paterz1 on Irreducible components
	paterz1 on Irreducible components
	Qiaochu Yuan on Irreducible components

Annoying Precision

"If people do not believe that mathematics is simple, it is only because they do not realize how complicated life is." – John von Neumann