Linear algebra and applications to graphs Part II

Written up by Mikhail Belkin and Moon Duchin Instructor: Laszlo Babai

June 19, 2001

3.3 More basic properties of the eigenvalues of graphs

Recall the notation that, for a graph G, the adjacency matrix is denoted A_{G} and has eigenvalues κ_{1} ≥ … ≥ κ_{n}, while the Laplacian is denoted Δ_{G} and has eigenvalues λ_{1} ≤ … ≤ λ_{n}.

Exercise 3.28 Prove: κ_{1} + … + κ_{n} = 0.

Exercise 3.29 Prove: λ_{1} + … + λ_{n} = 2m where m = |E| is the number of edges.

Exercise 3.30 Prove: κ_{1}^{2} + … + κ_{n}^{2} = 2m.

Exercise 3.31 Prove: κ_{1}^{3} + … + κ_{n}^{3} = 6t where t is the number of triangles in G.

Exercise 3.32 Prove: (∀s ≥ 0)(κ_{1}^{s} + … + κ_{n}^{s} is an integer.) The same holds for the λ_{i}.

Exercise 3.33 Prove: the following numbers cannot occur as eigenvalues of a graph: \sqrt{−1}, π, 3/5, \sqrt{3/2}, 2^{1/3}. They cannot occur as eigenvalues of the Laplacian either.

Exercise^{+} 3.34 Prove: if the characteristic polynomial of a graph G is irreducible (over ℚ) then G has no nontrivial automorphisms. (An automorphism is a self-isomorphism, i. e., a permutation of the vertices which preserves adjacency.)

OPEN PROBLEM. The characteristic polynomial of almost every graph is irreducible (over ℚ). (“Almost every graph” means that if we create a random graph on a given set of n vertices by flipping \binom{n}{2} coins to decide adjacency then the probability of the event in question is 1 − o(1).)

3.4 Eigenvalues and chromatic number

The chromatic number of a graph is the smallest number of “colors” needed for an assignment of colors to the vertices of G such that no pair of adjacent vertices receives the same color. This is one of the most important graph invariants. Here we consider the connections of chromatic number and the spectral theory of graphs.

Recall the notation that [k] = {1, 2, …, k}.

Definition 3.35 A legal k-coloring of a graph G is a map c : V → [k] such that {i, j} ∈ E ⇒ c(i) ≠ c(j). The chromatic number of G, denoted χ(G), is the smallest value of k for which a legal k-coloring exists.

Exercise 3.36 Compute the chromatic number k of the Petersen graph and present a legal k-coloring.

Exercise 3.37 Show that χ(G) ≤ deg_{max} +1.

The famous four-color theorem asserts that the chromatic number of a planar graph is at most four. But the weaker result that planar graphs are all six-colorable can be derived in a very elementary way, which we describe here.

Exercise 3.38 We will show, in several parts, that χ(G) ≤ 6 for planar graphs.

1. Show: If G is planar, then |E| ≤ 3n − 6, where n = |V |. (Hint: recall Euler’s formula: if a connected graph is embedded in the plane, then |V | − |E| + |F | = 2, where F is the set of faces, or regions; the outside counts as one of the regions.)

2. Show: If G is planar, then deg_{min} ≤ 5.

3. Conclude that χ(G) ≤ 6.

(Hint: use induction, setting aside a vertex of smallest degree at each stage.)

Eigenvalue bounds on the chromatic number are given below.

Theorem 3.39 (H. Wilf) χ(G) ≤ 1 + κ_{1}.

This is an improvement over the result that χ ≤ 1+deg_{max} (Exercise 3.37) because κ_{1} ≤ deg_{max} (Exercise 3.11).

Theorem 3.40 (Hoffman) χ(G) ≥ 1 + \frac{κ_{1}}{−κ_{n}} .

This is our first lower bound on chromatic number. While an upper bound on the chromatic number requires presenting a coloring, in order to prove a lower bound, we need to show that all attempted colorings with fewer colors fail. So the question of lower bounds is more profound and accordingly leads to deeper results.

Exercise 3.41 We prove Wilf’s theorem, in steps.

1. For a graph G, let G_{v} denote the graph obtained by deleting vertex v; that is, the induced subgraph on V \{v}. Show that deg v < χ(G)−1 ⇒ χ(G_{v}) = χ(G).

2. Conclude that G has an induced subgraph H with χ(G) = χ(H) and deg_{min}(H) ≥ χ(G) − 1.

3. Use this to finish the proof of the theorem.

(Hint: recall Exercise 3.12.)

Exercise^{+} 3.42 (Biggs) We show Hoffman’s theorem, in steps.

1. If a real symmetric matrix A is in block form

A = [ \begin{matrix}P & Q \\ Q^{t} & R \end{matrix} ] ,

where P, Q, R are n × n matrices, then

λ_{max}(A) + λ_{min}(A) ≤ λ_{max}(P) + λ_{max}(R).

(Hint: a somewhat delicate application of Rayleigh quotients, see Def. 2.24.)

2. Show by induction: if A is a real symmetric matrix in block form with t^{2} submatrices A_{ij} (1 ≤ i, j ≤ t) such that the diagonal submatrices A_{ii} are square, then

λ_{max}(A) + (t − 1)λ_{min}(A) ≤ ∑_{i=1}^{t} λ_{max}(A_{ii}).

3. Deduce Hoffman’s theorem.

(Hint: consider a partition of the vertices by color to apply the previous part of the exercise. Then observe that λ_{min} < 0 to complete the proof.)

Next, we consider a special class of graphs for which the spectral gap is as big as possible.

Definition 3.43 A Ramanujan graph G is a regular graph of degree r such that (∀i ≥ 2)(|κ_{i}| ≤ \sqrt{2r − 1}).

Note that κ_{1} = deg G = r, so there is a large gap between κ_{1} and κ_{2}. It follows, by Hoffman’s theorem, that χ(G) ≥ 1 + \frac{r}{\sqrt{2r−1}} = Ω(\sqrt{r}). In fact, this bound on the eigenvalues is asymptotically tight; that is, the

\sqrt{2r − 1} bound in the definition of Ramanujan graphs cannot be replaced with any smaller value. This fact is quite difficult to show, and can be found in the work of Lubotzky-Phillips-Sarnak.

While it is hard to get a good upper bound on κ_{2}, we can obtain lower bounds with less work. The next exercise provides one such bound.

Exercise 3.44 We will show that, for all r-regular graphs on n vertices with sufficiently large n, the second eigenvalue is at least \sqrt{r}.

1. Show that for r-regular graphs G, we have

diam(G) = 3 ⇒ n ≤ r^{3} − r^{2} + r + 1.

2. Conclude that for such graphs with r ≥ 2, n ≥ r^{3} ⇒ diam(G) ≥ 4.

3. Show that, if n is sufficiently large relative to r then we have κ_{2}(G) ≥ \sqrt{r}. (Hint: use the diameter information to find induced subgraphs which are disjoint, and reason from there using the results of Exercise 3.16 in Part 1 of the Linear algebra handout.)