Spectral bounds on the chromatic number

Posted on 4th July 2023

Recently Clive Elphink gave us a nice seminar where he discussed some of his "conjectures in spectral graph theory". Clive has an interesting history: after a career in business, he is now semi-retired and returned to research mathematics. By his own admission, he is more on the experimental side, and his talk said almost nothing about proofs. Here is a old result in this area:

Theorem [Hoffman]: We have that $χ (G) \geq 1 + \frac{λ_{1}}{- λ_{n}}$ .

I explain the notation shortly, but in words, this result relates a vertex colouring of a graph to the eigenvalues of the adjacency matrix. To me, this seems hugely surprising, as why would the spectrum of $A$ have anything to do with a vertex colouring? I want to explain the elegant arguments of Elphick and Wocjan, and also some generalisations to quantum colourings (in part 2).

The setup

Let us set the scene. Here a graph is $G = (V, E)$ where $V$ is a finite set of vertices, and $E$ is a set of undirected edges. We disallow loops, and between a pair of vertices there can be at most one edge, so our graph is simple. Often we write $u \sim v$ to indicate there is an edge between vertices $u$ and $v$ . Set $n = | V |$ and $m = | E |$ ; sometimes we identify $V$ with $[n] = {1, 2, \dots, n}$ . A colouring of $G$ is an assignment $f : V \to [c]$ such that $u \sim v ⟹ f (u) \neq f (v)$ , that is, adjacent vertices are coloured distinctly. The minimal $c$ we can choose is the chromatic number $χ (G)$ .

The adjacency matrix of $G$ is $A = A_{G}$ , the ${0, 1}$ -valued matrix indexed by $V \times V$ with $A_{u, v} = 1$ if and only if $u \sim v$ . As $G$ is undirected, $A$ is symmetric/hermitian, and so has real eigenvalues and a complete set of orthogonal eigenvectors. Let $λ_{1} \geq λ_{2} \geq \dots \geq λ_{n}$ be the eigenvalues listed in non-increasing order.

Lemma: If $G$ is non-trivial, then $λ_{1} > 0$ . Further, $\sum_{i} λ_{i} = 0$ and so $λ_{n} < 0$ .

Proof: Let $(e_{u})$ be the standard unit vector basis of $C^{V}$ , choose $u \sim v$ , and set $ξ = e_{u} + e_{v}$ . Then $(ξ | A ξ) = A_{u, u} + A_{u, v} + A_{v, u} + A_{v, v} = 2$ , so $- A$ is not positive. Thus there must be some strictly positive eigenvector, so $λ_{1} > 0$ .

The sum of the eigenvalues is the trace of $A$ , which is $0$ .

That $λ_{1} > 0$ is also a consequence of the Perron–Frobenius theorem.

Colourings to matrix properties

As this is an informal writeup, I will not give precise references, but instead list some further reading at the end. For now, I follow a couple of papers of Elphick and Wocjan. The first hint of a link between colourings and matrices is the observation that given a colouring $f : V \to [c]$ (wlog every colour is used), we can permute the vertices to list them in colour order, that is, find $1 = n_{0} < n_{1} < \dots < n_{c - 1} < n_{c} = n$ so that $f (u) = i$ exactly when $n_{i - 1} \leq u < n_{i}$ . We partition the standard basis $(e_{i})_{i = 1}^{n}$ of $C^{n}$ according to this partition, and hence view matrices in $M_{n}$ as $c \times c$ block matrices. As vertices which share a colour cannot be adjacent, if we view $A$ as such a block matrix, the diagonal blocks are all zero. $A = (\begin{matrix} 0_{n_{1}} & * & \dots & * \\ * & 0_{n_{2} - n_{1}} & ⋮ & * \\ ⋮ & ⋱ & ⋱ & ⋮ \\ * & * & \dots & 0_{n - n_{c - 1}} \end{matrix})$

Letting $P_{i}$ be the orthogonal projection on the $i$ th block, that is, the span of $e_{n_{i - 1}}, \dots, e_{n_{i} - 1}$ , we equivalently have that $P_{i} A P_{i} = 0$ for each $i \in [c]$ . This sort of operation has a name in Quantum Information Theory (QIT).

Pinchings and twirlings

Definition: Let $(P_{i})_{i = 1}^{c}$ be orthogonal projections which sum to $1 \in M_{n}$ . The operation $C : M_{n} \to M_{n}; x \mapsto \sum_{i = 1}^{c} P_{i} x P_{i}$ is called a pinching.

There is a seemingly unrelated operation using unitary matrices.

Definition: Let $(U_{i})_{i = 1}^{d}$ be a collection of unitary matrices in $M_{n}$ . The operation $D : M_{n} \to M_{n}; x \mapsto \frac{1}{d} \sum_{i = 1}^{d} U_{i} x U_{i}^{*}$ is called a twirling.

In fact, any pinching can be expressed as a twirling. Let $(P_{i})_{i = 1}^{c}$ be orthogonal projections which sum to $1$ and let $ζ$ be a $c^{th}$ root of unity (so $ζ^{c} = 1$ and $ζ^{k} \neq 1$ for $1 \leq k < c$ ; e.g. we could have $ζ = e^{2 π i / c}$ ). Set $U = \sum_{k = 1}^{c} ζ^{k} P_{k} ⟹ U^{*} U = \sum_{k, l = 1}^{c} ζ^{- l} ζ^{k} P_{l} P_{k} = \sum_{k = 1}^{c} ζ^{k - k} P_{k} = 1,$ and similarly $U U^{*} = 1$ , so $U$ is unitary. Here we used that the projections are orthogonal and sum to $1$ . Similarly, that the projections are orthogonal shows that $U^{t} = \sum_{k = 1}^{c} ζ^{k t} P_{k}$ . For any matrix $x$ , $D (x) = \frac{1}{c} \sum_{k = 1}^{c} U^{k} x (U^{*})^{k} = \frac{1}{c} \sum_{k, t, s = 1}^{c} ζ^{k (t - s)} P_{t} x P_{s} = \sum_{t = 1}^{c} P_{t} x P_{t} = C (x),$ using that $\frac{1}{c} \sum_{k = 1}^{c} ζ^{k r} = δ_{r, 0}$ .

The proof

We can now prove Hoffman's bound.

Proof (of Hoffman's Theorem): As argued above, if $G$ admits a vertex colouring using $c$ colours then, after permuting the vertices, we can find "coordinate" projections $(P_{i})_{i = 1}^{c}$ such that the pinching of the adjacency matrix satisfies $C (A) = 0$ . (Here "coordinate projection" means a projection onto the span of some of standard unit vector basis elements $(e_{i})_{i = 1}^{n}$ .)

Form $U$ as above, so the twirling also satisfies $D (A) = 0$ . As $ζ^{c} = 1$ we see that $U^{c} = \sum_{k = 1}^{c} P_{k} = 1$ and hence $D (A) = 0 ⟹ A = \sum_{k = 1}^{c - 1} U^{k} (- A) (U^{*})^{k} .$ Let $v$ be a unit length eigenvector for the eigenvalue $λ_{1}$ , so $(v | A v) = (v | λ_{1} v) = λ_{1}$ while $\sum_{k = 1}^{c - 1} (v | U^{k} (- A) (U^{*})^{k} v) = \sum_{k = 1}^{c - 1} ((U^{*})^{k} v | (- A) (U^{*})^{k} v) \leq (c - 1) λ_{max} (- A),$ where $λ_{max} (- A) = - λ_{n}$ is the greatest eigenvalue of $- A$ . Here we used that for each $(U^{*})^{k} v$ is a unit vector, for any $k$ .

We have hence shown that $λ_{1} \leq (c - 1) (- λ_{n})$ or equivalently, $c \geq 1 + \frac{λ_{1}}{- λ_{n}}$ . As $χ (G)$ is the minimal choice for $c$ , this establishes Hoffman's bound.

Many other spectral bounds on $χ (G)$ can be established in a rather similar way; for details see the papers by Elphick and Wocjan listed below.

References / Further reading

Bhatia, Rajendra "Pinching, trimming, truncating, and averaging of matrices." Am. Math. Mon. 107, No. 7, 602-608 (2000). Zbl 0984.15024

Elphick, Clive; Wocjan, Pawel "Spectral lower bounds for the quantum chromatic number of a graph." J. Comb. Theory, Ser. A 168, 338-347 (2019). Zbl 1421.05042

Elphick, Clive; Wocjan, Pawel "An inertial lower bound for the chromatic number of a graph." Electron. J. Comb. 24, No. 1, Research Paper P1.58, 9 p. (2017). Zbl 1358.05104

Elphick, Clive; Wocjan, Pawel "Unified spectral bounds on the chromatic number." Discuss. Math., Graph Theory 35, No. 4, 773-780 (2015). Zbl 1326.05080

Wocjan, Pawel; Elphick, Clive "New spectral bounds on the chromatic number encompassing all eigenvalues of the adjacency matrix." Electron. J. Comb. 20, No. 3, Research Paper P39, 18 p. (2013). Zbl 1295.05112