As Anurag Bishnoi likes to point out on his blog, an often overlooked source of wisdom is Willem Haemer’s PhD thesis from 1979. Many of Haemer’s proofs rely on simple properties of partitions of Hermitean matrices. My motivation for this post was a small exercise for myself. I wanted to prove the easy one of the two Cheeger inequalities for graphs using Haemer’s technique. Non-surprisingly, the book “Spectra of Graphs” by Brouwer and Haemers gives this kind of proof.
Earlier on this blog we discussed that there are many different names for equitable partitions. My list from back then is incomplete as (1) I intentionally left out terms such as -designs (not to be confused with -designs) from Delsarte’s PhD thesis, and (2) I realized that for instance Stefan Steinerberger defined a notion of graphical designs which resembles the definition of a -design, while people working on latin squares call them -plexes, for instance see here. For this post just recall the following facts on equitable partitions:
- A bipartition of the vertex set of a regular graph is equitable if there exist constants such that each vertex in has neighbours in .
- The eigenvalues of the -marix are eigenvalues of the adjacency matrix of the graph.
- Let be the eigenspace of for (for , not ). The characteristic vector of lies in for .
The above statement only uses that an adjacency matrix is a Hermitean matrix. Hence, we can forget about the graph. All we need is that we can write
such that all have a constant row sum of . In particular, this means similar statements are true for all Hermitean matrices which one can associate with a graph such as weighted adjacency matrices, the Laplacian matrix, or the normalized Laplacian matrix.
Let us state a simplified version of Theorem 1.2.3 in Willem Haemer’s PhD thesis:
Theorem 1 Let be a Hermitean -matrix with eigenvalues partitioned as
Let be the average row sum in and let be the quotient matrix, that is
Then the eigenvalues of satisfy and . Here iff the partition is equitable.
Now let us spend the rest of this post proving two eigenvalue inequality in spectral graph theory. For simplicity, we always have a graph that is -regular and has vertices. The eigenvalues of its adjacency matrix are . We denote the eigenspace of by and the eigenspace of by .
1. The Bounds
The first eigenvalue inequality is the namesake for this blog.
Theorem 2 (Hoffman’s Ratio Bound) The independence number satisfies
Equality holds if the characteristic vector of lies in .
Proof: Let be an independent set of maximum size. We partition the vertices as and . Then the quotient matrix for this partition (for some positive number which is the average number of neighbours of a vertex of in ) is
The eigenvalues of this matrix are and . A simple double counting argument shows that . Using and rearranging shows the claimed bound. In the case of equality, the partition is equitable. This proves the second part of the assertion.
This proof is in Haemer’s PhD thesis and many other places. Now we come to my small exercise, Cheeger’s inequality for graphs which is not in Haemer’s PhD thesis, but in his book from four decades later. For a bipartition , let be the set of edges between and . The number
is known as the Cheeger constant of . The following easy bound was observed by several researchers independently, for instance Alon and Milman.
Theorem 3 (The Easy Cheeger’s Inequality for Graphs) We have
Equality holds only iff the characteristic vector of is in and .
Proof: Let be the size of . We write for . As before, we write down the matrix for our partition. Just this time, we might have edges in . So
and, by double counting, . The eigenvalues of are and . Clearly,
Using and , we obtain that
The bound follows. Again, equality holds iff and we have an equitable partition which shows the second part of the claim.
2. Small, Instantaneous Update
This is small edit with some context. I first skipped this part, but on second thought I want to include it again.
The proof of Cheeger’s inequality implies that both parts of the partition have the same size. As I am, by academic upbringing, a finite geometer, let me mention that finite geometries provide many examples where equality holds. These are known as hemisystems and are intensively investigated in generalized quadrangles of order , going back to Segre, see for instance this blog post by John Bamberg. Recently also in several families of distance-regular graphs, see for example this result by Jesse Lansdown and Alice Niemeyer.
Another graph in finite geometry with perfect expansion (in the sense of the Cheeger constant) is the Grassmann graph for odd. The first infinite family, which shows equality in Cheeger’s upper bound, is due to Bruen and Drudge from 1998, see here. These are a special type of non-trivial Boolean degree functions in the language of this earlier blog post on a paper of mine together with Yuval Filmus. This is an interesting family of examples as Khot, Minzer, and Safra showed in their famous result on the -to- games conjecture that, in some sense, lacks good expansion properties if and are sufficiently large.