f(b)$ for some implicitly given non-decreasing function $f: (0,1] \rightarrow (0,1]$. Informally, this is understood to mean that $a$ is small enough in relation to $b$. We sometimes also write $a \ll_f b$ when we wish to be specific about the function $f$.

Spectral partitioning
---------------------

Given a graph $G$ and $S \subseteq V(G)$, the *conductance* of $S$, written $\Phi(S) = \Phi_G(S)$, is given by $$\Phi(S) := \frac{e_G(S,\overline{S})}{\min({\text{vol}}_G(S),{\text{vol}}_G(\overline{S}))},$$ where ${\text{vol}}_G(S) = {\text{vol}}(S):=\sum_{i\in S}d(i)$ refers to the volume of $S$. The *edge expansion* $\Phi(G)$ of $G$ is defined by $\Phi(G) := \min_{S\subseteq V(G)}\Phi(S)$.

We write $A_G \in \mathbb{R}^{V(G) \times V(G)}$ for the adjacency matrix of $G$, where $A_G$ is the matrix whose rows and columns are indexed by vertices of $G$ and is defined by $$\begin{aligned}
(A_G)_{uv} := 
\begin{cases}
1 &\text{if } uv \in E(G); \\
0 &\text{otherwise}.
\end{cases}\end{aligned}$$ We write $$L_G := I-D^{-\frac{1}{2}}A_GD^{-\frac{1}{2}}$$ for the normalized Laplacian of $G$, where $I \in \mathbb{R}^{V(G) \times V(G)}$ is the identity matrix and $D$ is the diagonal matrix of degrees (where $D_{uu} = d(u)$ for each $u \in V(G)$ and $D_{uv}=0$ for $u \not= v$).

Suppose the eigenvalues of $L_G$ are ordered $\lambda_1 \leq \lambda_2 \leq \ldots \leq \lambda_n$. The following gives an 