This write-up will be about expander graphs, an indispensable tool in computer science. Expanders are widely used in error-correcting codes, complexity theory, hashing and computer networks.
Let $G=(V,E)$ be a graph. Let $S,T \subseteq V$. We define $E(S,T) := \{(u,v)\mid \{u,v\} \in E, u\in S, v\in T\}$: this is the edges $u\to v$ from $S$ to $T$. Let $e(S,T) = |E(S,T)|$. Note that if $S$ and $T$ have a non-empty intersection then we count the edges between $S$ and $T$ twice. We define the edge boundary of a set $S \subseteq V$ as $\partial S := E(S,V\setminus S)$. The vertex boundary is the number of neighbors of $S$ that are not in $S$.
<aside>
Definition A graph is a $\varepsilon$-edge expander if all subsets $S \subset V$ such that $|S| \leq |V|/2$ satisfy:
$$ h(S) = \frac{|\partial S|}{|E(S,V)|} \geq \varepsilon $$
</aside>
Intuitively, we can think of it as follows: a social network is a $1/2$ expander if for all groups of people, the number of friends outside of the group is at least $1/2$ the total number of friends of the group. We have a name for the largest $\varepsilon$ this definition works for: the isoperimetric number, or Cheeger constant.
$$ h(G) := \text{inf}_{S}[h(S)] $$
An adjacent definition, an $\varepsilon$-vertex expander is a graph where all $S \subset V$ with $|S|\leq |V|/2$ have $N(S) \geq \varepsilon |S|$. These two notions of expansion are combinatorial and well-motivated. Let's see an example
Consider $K_n$. We can prove that it is a $1$-vertex expander (which is actually optimal) and a $\frac{1}{2} + O(1/n)$ edge expander. This is a good exercise that we will leave for the end. Cycle graphs and Cayley graphs are interesting constructions of expanders.
Beyond the combinatorial definitions, we can also talk about spectral expansion. Let $G$ be $d$ -regular, and consider its normalized adjacency matrix: $A_G = A/d$. Let $\lambda_1\geq \lambda_2\geq\cdots\geq \lambda_n$ be the spectrum of $A_G$. By the Perron-Frobenius Theorem we can show that:
<aside>
Definition $G$ is a $\lambda$-spectral expander if
$$ \lambda(G) := \max\{|\lambda_2|,|\lambda_n|\} \leq \lambda $$
</aside>
We define the spectral gap of a graph as $1-\lambda_2$. What does the spectrum of a graph have anything to do with its expansion properties? The answer is that they are closely related, as we will see in the following theorem:
<aside>
Theorem: Expander Mixing Lemma Let $G$ be a $d$-regular graph with normalized adjacency matrix $A_G$ whose spectrum is $\lambda_1 \geq \cdots \geq \lambda_n$. Then, for all $S,T \subseteq V$, we have:
$$ \left|e(S,T)-\frac{d|S||T|}{n}\right|\leq \lambda(G)\cdot d\sqrt{|S|\cdot |T|} $$
</aside>
Proof: We kick things off with an important observation:
$$ 1_S^T (d A_G) 1_T = e(S,T) $$
This is because $(d A_G) 1_T$ gives for every $v \in V$ the number of neighbors in $T$, and subsequently multiplying by $1_S$ only keeps $v \in S$. Now, let us consider an orthonormal eigenbasis $\{v_1,...,v_n\}$ for $A_G$. We can write $1_S = \sum \alpha_i v_i$ and $1_T = \sum \beta_i v_i$ and then
$$ 1_S^T (A_G) 1_T = \sum\limits_{i=1}^n\alpha_i v_i^T\left(\sum\limits_{i=1}^n \lambda_i v_i v_i^T\right)\sum\limits_{i=1}^n\beta_i v_i = \sum\limits_{i=1}^n \lambda_i \alpha_i \beta_i $$