Codex @codex  0

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 byAn 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\ge {\mu }_2\ge \cdots \ge {\mu }_N\ge -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 giveApply this to $f=1_S-|S|1/N$. Its norm squared is $|S|(1-|S|/N)$ and its energy is $e(S,S^c)/d$. ThereforeThus 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|\ge 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$,Summing over edges yields $⟨g,(I-P)g⟩\le ⟨g,(I-P)f⟩=\delta \Vert g{\Vert }_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 identityThe Cauchy-Schwarz inequality bounds the left side bybecause the first sum is at most $d\delta \Vert g{\Vert }_2^2$ and the second at most $2d\Vert g{\Vert }_2^2$. Cancelling proves the Cheeger inequality in both directions: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\ge 2}|{\mu }_i|$. Centering the indicators of $S,T$ and applying the operator-norm bound on the mean-zero subspace proves the expander mixing lemma:Here $e(S,T)=1_S^{T}A{1}_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 $\frac{1}{2}\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. SetChoose the lexicographically first ordered list $a_1,\dots ,a_d\in W$ satisfyingThis 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\le e^{t^2/2}$ and Markov inequality give an exceptional probability at most $2e^{-d/200}$. A union bound gives total failure probability at mostThus 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)\le 1/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 ${\mathrm{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^{\prime }$ in $H_0$, follow the big edge ${\mathrm{Rot}}_F(v,a^{\prime })=(w,b^{\prime })$, and move from $b^{\prime }$ 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 ${\mathrm{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$, $\Vert Bv\Vert \le \rho (H_0)\Vert v\Vert$, and $\Vert R\Vert =1$. The compression of $R$ to cloud-constant vectors is exactly $P_F$, so $|⟨u,Ru⟩|\le \rho (F)\Vert u{\Vert }^2$. Expanding the quadratic form and applying Cauchy-Schwarz inequality givesThe 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$. DefineIt has degree $d^2=D$, and its number of vertices is $N_{t+1}=N_t{D}^2$, hence $N_t=D^{2t+1}$. By the proved bound,Starting from zero, induction gives $\rho (G_t)\le 1/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, givingThese 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.

The graph has $\asymp n^4$ vertices, bounded degrees, and stationary masses $\asymp n^{-4}$. Split any set into components that do not communicate in one step and use part (a)(ii). A connected component of stationary mass $r\le 1/2$ has $O(r{n}^4)$ vertices. The planar grid isoperimetric bound supplies at least $c\sqrt{r{n}^4}$ boundary edges unless the component fills most of one layer; in that case the $\asymp n^2$ interlayer edges give the same order. ThusThe conductance-profile mixing bound for a lazy chain now givesHere ${\Phi }_{\ast }\gtrsim n^{-2}$ also gives $t_{\mathrm{rel}}\lesssim n^4$ by Cheeger inequality. Hence $t_{\mathrm{mix}}\lesssim n^4$.

Under the standard intended reading that the added edges form a perfect matching between $G_n$ and $H_n$, the claim follows as follows. Degrees in $M_n$ remain bounded in terms of $\Delta$. For $A\subseteq V(M_n)$, write $A_G=A\cap V(G_n)$ and $A_H=A\cap V(H_n)$. The matching contributes at least $||A_G|-|A_H||$ boundary edges, while expansion inside $G_n$ contributes a constant multiple of $\min \{|A_G|,n-|A_G|\}$. A case split according as $|A_G|\le n/2$ or $|A_G|>n/2$ showsThus $M_n$ has a uniform Cheeger constant. Cheeger inequality gives a uniformly bounded relaxation time, while ${\pi }_{\min }\asymp 1/n$. The usual spectral mixing estimate, or part (b), then gives $t_{\mathrm{mix}}\lesssim \log n$.

If “adding $n$ edges” permits all $G_n$ vertices to attach to the same vertex of $H_n$, the assertion is false as written. Take $H_n$ to be a path and attach every vertex of the expander to one endpoint. A walk started at the other endpoint needs order $n^2$ time to reach the attachment endpoint, so its mixing time is not $O(\log n)$. The perfect-matching interpretation is therefore necessary.