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.

The K3xK3 graph with two highlighted equitable partitions. Think of the lines as cliques of size 3. This is a picture from my Master thesis many, many years ago.

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: