Proving Spectral Bounds With Quotient Matrices

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 $ {T}$-designs (not to be confused with $ {t}$-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 $ {T}$-design, while people working on latin squares call them $ {k}$-plexes, for instance see here. For this post just recall the following facts on equitable partitions:

• A bipartition $ {V_1 \cup V_2}$ of the vertex set $ {V}$ of a regular graph is equitable if there exist constants $ {b_{ij}}$ such that each vertex in $ {V_i}$ has $ {b_{ij}}$ neighbours in $ {V_j}$.
• The eigenvalues $ {\mu_1 \geq \mu_2}$ of the $ {(2\times 2)}$-marix $ {B = (b_{ij})}$ are eigenvalues of the adjacency matrix $ {A}$ of the graph.
• Let $ {W_i}$ be the eigenspace of $ {\mu_i}$ for $ {i \in \{ 1, 2 \}}$ (for $ {A}$, not $ {B}$). The characteristic vector of $ {V_j}$ lies in $ {W_1 + W_2}$ for $ {j \in \{ 1, 2 \}}$.

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

$ \displaystyle A = \begin{pmatrix} A_{11} & A_{21} \\ A_{12} & A_{22} \end{pmatrix} $

such that all $ {A_{ij}}$ have a constant row sum of $ {b_{ij}}$. 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 $ {A}$ be a Hermitean $ {(v \times v)}$-matrix with eigenvalues $ {\lambda_1 \geq \lambda_2 \geq \ldots \geq \lambda_v}$ partitioned as

$ \displaystyle A = \begin{pmatrix} A_{11} & A_{21} \\ A_{12} & A_{22} \end{pmatrix}. $

Let $ {b_{ij}}$ be the average row sum in $ {A_{ij}}$ and let $ {B}$ be the quotient matrix, that is

$ \displaystyle B = \begin{pmatrix} b_{11} & b_{12} \\ b_{21} & b_{22} \end{pmatrix}. $

Then the eigenvalues $ {\mu_1 \geq \mu_2}$ of $ {B}$ satisfy $ {\lambda_1 \geq \mu_1}$ and $ {\lambda_2 \geq \mu_2 \geq \lambda_v}$. Here $ {(\mu_1, \mu_2) = (\lambda_i, \lambda_j)}$ 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 $ {X}$ that is $ {r}$-regular and has $ {v}$ vertices. The eigenvalues of its adjacency matrix are $ {\lambda_1, \ldots, \lambda_v}$. We denote the eigenspace of $ {\lambda_1}$ by $ {W_1}$ and the eigenspace of $ {\lambda_v}$ by $ {W_v}$.

1. The Bounds

The first eigenvalue inequality is the namesake for this blog.

Theorem 2 (Hoffman’s Ratio Bound) The independence number $ {\alpha}$ satisfies

$ \displaystyle \alpha \leq \frac{v}{1-r/\lambda_v}. $

Equality holds if the characteristic vector of $ {Y}$ lies in $ {W_1 + W_v}$.

Proof: Let $ {Y}$ be an independent set of maximum size. We partition the vertices as $ {Y}$ and $ {V \setminus Y}$. Then the quotient matrix for this partition (for some positive number $ b$ which is the average number of neighbours of a vertex of $ V \setminus Y$ in $ Y$) is

$ \displaystyle B = \begin{pmatrix} 0 & r \\ r – b & b \end{pmatrix}. $

The eigenvalues of this matrix are $ {r}$ and $ {b-r}$. A simple double counting argument shows that $ {r-b = r \cdot \frac{\alpha}{v-\alpha}}$. Using $ {b-r \geq \lambda_v}$ and rearranging shows the claimed bound. In the case of equality, the partition is equitable. This proves the second part of the assertion. $ \Box$

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 $ {V_1 \cup V_2}$, let $ {\delta V_1}$ be the set of edges between $ {V_1}$ and $ {V_2}$. The number

$ \displaystyle h(X) := \min\left\{ \frac{|\delta V_1|}{|V_1|}: 0 < |V_1| < v/2 \right\} $

is known as the Cheeger constant of $ {X}$. 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

$ \displaystyle 2h(X) \geq d-\lambda_2. $

Equality holds only iff the characteristic vector of $ {V_1}$ is in $ {W_1 + W_2}$ and $ |V_1|=v/2$.

Proof: Let $ {y}$ be the size of $ {V_1}$. We write $ {h}$ for $ {h(X)}$. As before, we write down the matrix $ {B}$ for our partition. Just this time, we might have edges in $ {V_1}$. So

$ \displaystyle B = \begin{pmatrix} a & r-a \\ r – b & b \end{pmatrix}. $

and, by double counting, $ {r-b = (r-a) \cdot \frac{y}{v-y}}$. The eigenvalues of $ {B}$ are $ {r}$ and $ {a+b-r}$. Clearly,

$ \displaystyle h = \min\left\{ \frac{y(r-a)}{v-y}: y \leq v/2 \right\}. $

Using $ {\lambda_2 \geq a+b-r}$ and $ {a = r+h – v \frac{h}{y} \leq r-h}$, we obtain that

$ \displaystyle \lambda_2 \geq r – 2h. $

The bound follows. Again, equality holds iff $ \frac{v}{y} = 2$ and we have an equitable partition which shows the second part of the claim. $ \Box$

 

 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 $ {(q, q^2)}$, 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 $ {G_q(4, 2)}$ for $ {q}$ 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 $ {1}$ 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 $ {2}$-to-$ {2}$ games conjecture that, in some sense, $ {G_2(n, k)}$ lacks good expansion properties if $ {n}$ and $ {k}$ are sufficiently large.