= Solution
Let $G$ be a finite undirected $d$-regular <graph> on $N$ <vertices>, with <adjacency matrix> $A$ and normalized <random walk> matrix $P=A/d$. Define <edge> expansion and normalized conductance by
$$
h(G)=\min_{0<|S|\leq N/2}\frac{e(S,S^c)}{|S|},\qquad \Phi(G)=h(G)/d.
$$
An <expander family> has orders tending to infinity, uniformly bounded maximum degree, and a uniform positive lower bound on $h$. For a <regular graph> the constant vector is an <eigenvector> of $P$ with <eigenvalue> one. Write its <eigenvalues> as $1=\mu_1\geq\mu_2\geq\cdots\geq\mu_N\geq-1$, and let $\delta=1-\mu_2$. This <spectral gap> measures the energetic cost of departing from a constant function.
For every mean-zero vector $f$, the <spectral theorem> and the <graph>'s energy identity give
$$
\frac1d\sum_{\{u,v\}\in E}(f(u)-f(v))^2
=\langle f,(I-P)f\rangle\geq\delta\|f\|_2^2.
$$
Apply this to $f=\mathbf1_S-|S|\mathbf1/N$. Its norm squared is $|S|(1-|S|/N)$ and its energy is $e(S,S^c)/d$. Therefore
$$
e(S,S^c)\geq d\delta |S|(1-|S|/N),\qquad
\boxed{\Phi(G)\geq\delta/2.}
$$
Thus a uniform <spectral gap> gives uniform <edge> expansion when $d$ is fixed. This also bounds exterior <vertex> expansion: each exterior <vertex> accounts for at most $d$ boundary <edges>, so $|N(S)\setminus S|\geq e(S,S^c)/d$.
For the converse, take a mean-zero <eigenvector> $f$ for $\mu_2$ and choose its sign so that its positive support has at most $N/2$ <vertices>. Put $g=f^+$, which is nonzero. Truncation decreases energy in the following precise sense: for any two real numbers $a,b$,
$$
(a^+-b^+)^2\leq(a^+-b^+)(a-b).
$$
Summing over <edges> yields $\langle g,(I-P)g\rangle\leq\langle g,(I-P)f\rangle=\delta\|g\|_2^2$. For the threshold sets $S_t=\{v:g(v)^2>t\}$, every nonempty set lies in that small positive support. Integrating its boundary count gives the layer-cake identity
$$
\sum_{\{u,v\}\in E}|g(u)^2-g(v)^2|
=\int_0^\infty e(S_t,S_t^c)\,dt\geq h(G)\|g\|_2^2.
$$
The <Cauchy-Schwarz inequality> bounds the left side by
$$
\left(\sum_E(g(u)-g(v))^2\right)^{1/2}
\left(\sum_E(g(u)+g(v))^2\right)^{1/2}
\leq d\sqrt{2\delta}\,\|g\|_2^2,
$$
because the first sum is at most $d\delta\|g\|_2^2$ and the second at most $2d\|g\|_2^2$. Cancelling proves the <Cheeger inequality> in both directions:
$$
\boxed{\frac{1-\mu_2}{2}\leq\Phi(G)\leq\sqrt{2(1-\mu_2)}.}
$$
Hence bounded-degree regular families have uniform <edge> expansion exactly when their second-largest normalized <eigenvalue> stays uniformly below one.
Absolute <eigenvalues> give additional information. Put $\rho=\max_{i\geq2}|\mu_i|$. Centering the indicators of $S,T$ and applying the operator-norm bound on the mean-zero subspace proves the <expander mixing lemma>:
$$
\left|e(S,T)-\frac{d|S||T|}{N}\right|
\leq d\rho\sqrt{|S|(1-|S|/N)|T|(1-|T|/N)}.
$$
Here $e(S,T)=\mathbf1_S^TA\mathbf1_T$, so internal <edges> are counted as oriented incidences. A small $\rho$ makes <edge> counts resemble uniformly distributed <edges>. It also gives rapid <random walk> mixing: starting at a <vertex>, $P^t$ contracts the mean-zero component of its point mass by at most $\rho^t$ in <Euclidean norm>; <Cauchy-Schwarz inequality> then gives total variation distance at most $\tfrac12\sqrt N\rho^t$ from the uniform distribution. A <bipartite graph> has <eigenvalue> $-1$ and its non-lazy walk alternates sides, even if it has good <edge> expansion. The lazy walk $(I+P)/2$ has nonconstant <eigenvalues> between zero and $1-\delta/2$, resolving this periodicity. It is important to distinguish the gap $1-\mu_2$ controlling cuts from the absolute bound controlling non-lazy mixing.
Here is a fully specified deterministic construction of an infinite family. Its degree is large but fixed. Set
$$
d=2^{16},\qquad D=d^2=2^{32},\qquad W=\mathbb F_2^{64},\quad |W|=D^2.
$$
Choose the lexicographically first ordered list $a_1,\ldots,a_d\in W$ satisfying
$$
\left|\frac1d\sum_{j=1}^d(-1)^{u\cdot a_j}\right|\leq\frac1{10}\qquad\text{for every }u\in W\setminus\{0\}.
$$
This finite deterministic search terminates. To prove existence, choose the list uniformly and independently. For each nonzero $u$, its signs are independent unbiased signs; the exponential-moment estimate $\cosh t\leq e^{t^2/2}$ and <Markov inequality> give an exceptional <probability> at most $2e^{-d/200}$. A <union bound> gives total failure <probability> at most
$$
2(2^{64}-1)e^{-2^{16}/200}<1.
$$
Thus at least one qualifying list exists. Fix it once and for all.
Let $H$ be the <Cayley graph> on $W$ whose $j$th neighbor of $x$ is $x+a_j$. It is an undirected $d$-regular port-labeled <graph>, allowing repeated <edges> and loops in this intermediate construction. Its <characters> $x\mapsto(-1)^{u\cdot x}$ form an <orthogonal> <eigenbasis>, with the displayed averages as normalized <eigenvalues>. Therefore $\rho(H)\leq1/10$. Each loop counts as one transition port; degrees here mean row sums of the <adjacency matrix>.
We next define the <zig-zag product> and prove the bound used for iteration. A port labeling of a $D_0$-regular undirected <graph> $F$ gives an involution $\operatorname{Rot}_F(v,a)=(w,b)$, recording the endpoint and reverse port. If a $d$-regular <graph> $H_0$ has <vertex> set $[D_0]$, the product has <vertices> $(v,a)\in V(F)\times[D_0]$. For each ordered pair of small-graph ports, move from $a$ to $a'$ in $H_0$, follow the big <edge> $\operatorname{Rot}_F(v,a')=(w,b')$, and move from $b'$ to $b$ in $H_0$. The endpoint is $(w,b)$; reversing the steps reverses the two small-graph port labels. The product is undirected, has $|V(F)|D_0$ <vertices>, and has degree $d^2$.
Write $B=I\otimes P_{H_0}$ and let $R$ be the permutation matrix of $\operatorname{Rot}_F$. The normalized product operator is $BRB$. For a mean-zero unit vector, decompose $f=u+v$ into its cloud-constant part and its cloud-orthogonal part. Then $Bu=u$, $\|Bv\|\leq\rho(H_0)\|v\|$, and $\|R\|=1$. The compression of $R$ to cloud-constant vectors is exactly $P_F$, so $|\langle u,Ru\rangle|\leq\rho(F)\|u\|^2$. Expanding the quadratic form and applying <Cauchy-Schwarz inequality> gives
$$
|\langle f,BRBf\rangle|
\leq\rho(F)\|u\|^2+2\rho(H_0)\|u\|\|v\|+\rho(H_0)^2\|v\|^2
\leq\rho(F)+2\rho(H_0)+\rho(H_0)^2.
$$
The operator is symmetric, so its mean-zero <operator norm> is bounded by this same quantity. No unproved product spectral estimate is needed.
Start with the loop-inclusive <complete graph> $G_0$ on $D$ <vertices>, whose normalized matrix is $J/D$ and whose nonconstant <eigenvalues> are all zero. Given a $D$-regular $G_t$, its two-step <graph> $G_t^2$ has degree $D^2$ and normalized operator $P_{G_t}^2$. Label a two-step <edge> by its ordered pair of ports; reversal reverses the path and its reverse ports. These $D^2$ labels are the <vertex> set of the fixed <graph> $H$. Define
$$
G_{t+1}=G_t^2\mathbin{\mathrm{zigzag}}H.
$$
It has degree $d^2=D$, and its number of <vertices> is $N_{t+1}=N_tD^2$, hence $N_t=D^{2t+1}$. By the proved bound,
$$
\rho(G_{t+1})\leq\rho(G_t)^2+\frac{21}{100}.
$$
Starting from zero, induction gives $\rho(G_t)\leq1/2$, since $(1/2)^2+21/100=46/100<1/2$. The cut-energy argument therefore gives multiplicity-counted <edge> expansion at least $D/4$ for every $G_t$.
To obtain ordinary simple <graphs>, delete loops and merge parallel <edges>. The maximum degree is at most $D$, and any one unordered <vertex> pair had multiplicity at most $D$. Thus every cut retains at least $1/D$ of its multiplicity-counted boundary, giving
$$
\boxed{|V(G_t)|=D^{2t+1}\longrightarrow\infty,\qquad \Delta\leq D,\qquad h\geq1/4.}
$$
These simple <graphs> form an <expander family>. Every choice is deterministic: the finite base search is fixed independently of $t$, and the recursive <edge> rules determine all subsequent adjacency lists. Once that base is fixed, adjacency lists can be generated successively using the previous lists, with a constant amount of work per output <edge>. This is <squaring and zig-zag iteration yields bounded-degree expanders>. The spectral argument supplies the uniform expansion guarantee and explains why squaring improves the <eigenvalues> while the product restores a constant degree.
Back to article page
