3 Expander graphs

Definition 14 Expansion by a factor of \(\delta \)

Let \(G=(V,E)\) be a graph on \(n\) vertices. We say every set of at most \(m\) vertices expands by a factor of \(\delta \) if for all \(S \subseteq V\) with \(|S| \le m\),

\[ \bigl|\{ \, y : \exists \, x \in S \text{ with } (x,y)\in E\, \} \bigr| {\gt} \delta \, |S|. \]

Definition 15 Unbalanced bipartite \((c,d)\)-regular graph

An unbalanced bipartite graph has its vertices split into two sets with no edges inside a set. It is \((c,d)\)-regular if every vertex on one side has degree \(c\) and every vertex on the other side has degree \(d\). By counting edges, the number of \(c\)-regular vertices exceeds the number of \(d\)-regular vertices by the factor \(d/c\).

Definition 16 \((c,d,\epsilon ,\delta )\)-expander

A graph is a \((c,d,\epsilon ,\delta )\)-expander if it is a \((c,d)\)-regular graph in which every subset of at most an \(\epsilon \) fraction of the \(c\)-regular vertices expands (into the \(d\)-regular side) by a factor of at least \(\delta \). We use families of \((c,d,\epsilon ,\delta )\)-expanders in which \(c,d,\epsilon ,\delta \) are constant as the number of vertices grows.

Proposition 17 Proposition 1: random graphs are good expanders

Let \(B\) be a randomly chosen \((c,d)\)-regular bipartite graph between \(n\) \(c\)-regular vertices and \((c/d)n\) \(d\)-regular vertices. Then for all \(0{\lt}\alpha {\lt}1\), with high probability all sets of \(\alpha n\) \(c\)-regular vertices in \(B\) have at least

\[ n\! \left(\frac{c}{d}\bigl(1-(1-\alpha )^d\bigr) - \sqrt{\frac{2c\alpha \, H(\alpha )}{\log _2 e}}\right) \]

neighbours, where \(H(\cdot )\) is the binary entropy function.

Proof ▶

This is Theorem 44, proved in Appendix II.

Theorem 18 Theorem 2: Lubotzky–Phillips–Sarnak, Margulis

For every pair of primes \(p,q\) congruent to \(1\) modulo \(4\) such that \(p\) is a quadratic residue modulo \(q\), there is a \((p+1)\)-regular Cayley graph of \(PSL(2,\mathbb {Z}/q\mathbb {Z})\) with \(q(q^2-1)/2\) vertices whose second-largest eigenvalue is at most \(2\sqrt{p}\). A graph with this eigenvalue separation is a good expander.

Proposition 19 Proposition 3: polynomial-time construction of Theorem 2 graphs

Each graph described in Theorem 18 can be constructed in time polynomial in its number of vertices. Moreover there is an algorithm that, given a logarithmic-size description of the graph, produces the labels of the neighbours of a node in time polynomial in the length of the labels (i.e. polylogarithmic in the number of vertices).

Definition 20 Definition 4: edge-vertex incidence graph

Let \(G\) be a graph with edge set \(E\) and vertex set \(V\). The edge-vertex incidence graph of \(G\) is the bipartite graph with vertex set \(E \cup V\) and edge set \(\{ (e,v) \in E\times V : v \text{ is an endpoint of } e\} \). If \(G\) is \(d\)-regular on \(n\) vertices, this is a \((2,d)\)-regular graph with \(dn/2\) vertices on one side and \(n\) on the other.

Lemma 21 Lemma 5: Alon–Chung

Let \(G\) be a \(d\)-regular graph on \(n\) vertices with second-largest eigenvalue \(\lambda \). Let \(X\) be a subset of the vertices of \(G\) of size \(\gamma n\). Then the number of edges contained in the subgraph induced by \(X\) in \(G\) is at most

\[ \frac{dn}{2}\left(\gamma ^2 + \frac{\lambda }{d}\, \gamma (1-\gamma )\right). \]