エクスパンダーグラフ

Cheegerの不等式(グラフ) の系「正則グラフの場合」により $\frac12(d-\lambda_2)\le h(G_j)\le\sqrt{2d(d-\lambda_2)}$ である。$h(G_j)\ge\varepsilon$ なら $d-\lambda_2\ge\varepsilon^2/(2d)$ であり、$d-\lambda_2\ge\delta$ なら $h(G_j)\ge\delta/2$ である。$\square$

$A\mathbf 1=d\mathbf 1$ なので、スペクトル定理 により、$u_1=\mathbf 1/\sqrt n$ から始まる固有ベクトルの正規直交基底 $u_1,\dots,u_n$、$Au_i=\lambda_iu_i$ がとれる（$\lambda_1=d$。$d$ の重複度が $2$ 以上でも、固有空間の正規直交基底を $u_1$ から始めればよい）。$\mathbf 1_S=\sum_i\alpha_iu_i$、$\mathbf 1_T=\sum_i\beta_iu_i$ と展開すると、$\alpha_1=\mathbf 1_S^{\mathsf T}u_1=s/\sqrt n$、$\beta_1=t/\sqrt n$ であり
$$ e(S,T)=\mathbf 1_S^{\mathsf T}A\mathbf 1_T=\sum_{i=1}^n\lambda_i\alpha_i\beta_i=\frac{d\,st}n+\sum_{i\ge2}\lambda_i\alpha_i\beta_i $$
である。$i\ge2$ では $\lvert\lambda_i\rvert\le\lambda$ なので、Cauchy–Schwarzの不等式 により
$$ \Bigl\lvert\sum_{i\ge2}\lambda_i\alpha_i\beta_i\Bigr\rvert\le\lambda\sum_{i\ge2}\lvert\alpha_i\beta_i\rvert\le\lambda\Bigl(\sum_{i\ge2}\alpha_i^2\Bigr)^{1/2}\Bigl(\sum_{i\ge2}\beta_i^2\Bigr)^{1/2} $$
である。$\sum_i\alpha_i^2=\mathbf 1_S^{\mathsf T}\mathbf 1_S=s$ から $\sum_{i\ge2}\alpha_i^2=s-s^2/n=s(1-s/n)$、同様に $\sum_{i\ge2}\beta_i^2=t(1-t/n)$ である。これで最初の不等式が示された。2 つ目は $0\le1-s/n\le1$ などによる。$\square$

$S$ を独立集合（どの 2 頂点も隣接しない集合）とし、$s:=\lvert S\rvert>0$ とする。$e(S,S)=0$ なので、thm-exp-mixing を $T=S$ に使うと $ds^2/n\le\lambda s(1-s/n)$、すなわち $ds\le\lambda(n-s)$ である。これを $s$ について解くと $s\le n\lambda/(d+\lambda)$ を得る。各色の頂点の集合は独立集合なので、$n\le\chi(G)\cdot n\lambda/(d+\lambda)$ である。$\square$

$v$ から出る 後戻りしない歩道、すなわち頂点の列 $P=(w_0,w_1,\dots,w_m)$ で、$w_0=v$、$w_{i}$ と $w_{i-1}$ が隣接し、$w_{i+1}\neq w_{i-1}$ となるもの（$m\ge0$）の全体を $\mathcal T$ とする。$m\ge1$ の $P$ から最後の頂点を除いたものを $P$ の 親、$P$ の後ろに $w_m$ の隣接頂点 $y\neq w_{m-1}$ を付け加えたものを $P$ の 子 という。$G$ は単純で $d$-正則なので、子は $m=0$ なら $d$ 個、$m\ge1$ なら $d-1$ 個ある。
$\mathcal T$ の上の歩みから $G$ の歩道へ． $P_0=(v)$ から始め、各段で子か親へ移って $2k$ 段後に $(v)$ に戻る列 $P_0,P_1,\dots,P_{2k}$ を 木の上の閉じた歩み という。各 $P_i$ の最後の頂点 $x_i$ を並べると、子へ移れば新しい最後の頂点は隣接頂点であり、親へ移れば最後の頂点は直前の頂点 $w_{m-1}$ なので、$(x_0,\dots,x_{2k})$ は $v$ から $v$ への長さ $2k$ の歩道である。この対応は単射である。実際、$P_i=(w_0,\dots,w_m)$ と $x_{i+1}$ が分かれば、$m\ge1$ かつ $x_{i+1}=w_{m-1}$ のときは $P_i$ の後ろに $x_{i+1}$ を付けた列が後戻りするので $P_{i+1}$ は親であり、それ以外のときは親の最後の頂点が $x_{i+1}$ でないので $P_{i+1}$ は $P_i$ の後ろに $x_{i+1}$ を付けた子である。よって $P_0$ から順に $P_i$ がすべて決まる。
木の上の閉じた歩みを数える． 子へ移る段を $+1$、親へ移る段を $-1$ と書くと、$P_i$ の長さ $m$ はそこまでの和であり、$0$ 以上で、最後に $0$ に戻る。よって段の種類の列は長さ $2k$ の Dyck 列である（Catalan数 の定義「Dyck 列と Catalan 数」）。逆に Dyck 列を 1 つ決めると、$-1$ の段では直前の長さが $1$ 以上なので親がただ 1 つあり、$+1$ の段では子の選び方が $d-1$ 通り以上ある。よって木の上の閉じた歩みは $C_k(d-1)^k$ 個以上あり、単射により主張が従う。$\square$

$A$ の固有値は $\lambda_1=d$ と、絶対値が $\lambda:=\lambda(G)$ 以下の $n-1$ 個なので、トレースと固有値 により $\operatorname{tr}A^{2k}=\sum_i\lambda_i^{2k}\le d^{2k}+(n-1)\lambda^{2k}$ である。一方 $\operatorname{tr}A^{2k}$ は、隣接行列 の定理「隣接行列の冪と歩道の数」により、各頂点から出て戻る長さ $2k$ の歩道の個数の和であり、lem-exp-closed-walks により $nC_k(d-1)^k$ 以上である。2 つを合わせて最初の不等式を得る。
後半を示す。$\varepsilon$ を小さくすると条件は弱くなるので、$0<\varepsilon<2\sqrt{d-1}$ としてよい。$\rho:=2\sqrt{d-1}-\varepsilon$、$q:=\rho/(2\sqrt{d-1})\in(0,1)$ とおく。$\binom{2k}k$ は和が $4^k$ の $2k+1$ 個の数 $\binom{2k}j$（$0\le j\le2k$）の最大のものなので $\binom{2k}k\ge4^k/(2k+1)$ であり、$C_k(d-1)^k\ge(4(d-1))^k/((k+1)(2k+1))$ である。$\lambda(G)\le\rho$ なら、$\rho^{2k}=q^{2k}(4(d-1))^k$ と最初の不等式、$n\ge n-1$ から
$$ (n-1)\,(4(d-1))^k\Bigl(\frac1{(k+1)(2k+1)}-q^{2k}\Bigr)\ \le\ d^{2k} $$
である。$q<1$ なので、$q^{2k}\le\frac1{2(k+1)(2k+1)}$ となる $k$ を $d$ と $\varepsilon$ だけから選べる。この $k$ について $n-1\le2(k+1)(2k+1)\,d^{2k}/(4(d-1))^k$ であり、右辺は $G$ によらない。頂点の個数が有界な $d$-正則単純グラフは同型を除いて有限個なので、主張が従う。$\square$

1 つの集合についての確率． $S\subset L$ を $\lvert S\rvert=s$ の集合、$T\subset R$ を $\lvert T\rvert=m\ge s$ の集合とする（添字で $\{1,\dots,n\}$ の部分集合とみる）。$N(S)=\bigcup_j\pi_j(S)$ である。一様な置換による $S$ の像は $s$ 元部分集合の上で一様に分布し（各 $s$ 元部分集合はちょうど $s!(n-s)!$ 個の置換の像になる）、$\pi_j$ は独立なので
$$ P\bigl(N(S)\subset T\bigr)=\Bigl(\binom ms\Big/\binom ns\Bigr)^{d}\le\Bigl(\frac mn\Bigr)^{sd} $$
である（$\binom ms/\binom ns=\prod_{i=0}^{s-1}\frac{m-i}{n-i}$ の各因子は $m/n$ 以下）。$S\subset R$ についても、$\pi_j^{-1}$ が独立で一様なので同じである。
$L$ の側の確率が $0$ に近づくことは、$S$ と $T$ の選び方の個数と上の確率を掛けて足し合わせる計算で確かめられる。

• $a'\le n/2$ のとき、$\lvert N(A)\setminus B\rvert\ge\frac32a'-b'\ge\frac12a'\ge\frac14\lvert U\rvert$ である。
• $a'>n/2$ のとき、$b'\le n-a'< n/2$ なので $b'\le(n-1)/2$ である。$A$ の $\lfloor n/2\rfloor$ 元部分集合 $A_0$ をとると $\lvert N(A_0)\setminus B\rvert\ge\frac32\lfloor\frac n2\rfloor-b'\ge\frac34(n-1)-\frac12(n-1)=\frac{n-1}4$ であり、$n\ge5$ なら $\frac{n-1}4\ge\frac n5\ge\frac15\lvert U\rvert$ である。
  頂点は $2n$ 個なので、$h(G_n)$ の定義の集合は $1\le\lvert U\rvert\le n$ のものであり、$h(G_n)\ge1/5$ を得る。$\square$

頂点 $v$ からの距離が $r$ 以下の頂点の集合を $B_r$ とする。$\lvert B_r\rvert\le n/2$ なら $\lvert\partial B_r\rvert\ge h\lvert B_r\rvert$ であり、$\partial B_r$ の辺の $B_r$ の外の端は $B_{r+1}\setminus B_r$ にある。各頂点にはこれらの辺が高々 $d$ 本しか来ないので $\lvert B_{r+1}\setminus B_r\rvert\ge h\lvert B_r\rvert/d$、すなわち $\lvert B_{r+1}\rvert\ge(1+h/d)\lvert B_r\rvert$ である。$\lvert B_r\rvert>n/2$ となる最小の $r$ を $r_0$ とすると（$h>0$ なので $G$ は連結で $r_0$ は存在する）、$r< r_0$ では $\lvert B_r\rvert\ge(1+h/d)^r$ なので $(1+h/d)^{r_0-1}\le n/2$、すなわち $r_0\le1+\log(n/2)/\log(1+h/d)$ である。$r_0$ は中心の頂点によるが、この上界は中心によらない。2 頂点 $u,v$ のそれぞれを中心とし、それぞれの $r_0$ を半径とする球はどちらも半分より多くの頂点を含むので交わり、$u,v$ の距離は 2 つの $r_0$ の和以下、したがって $2+2\log(n/2)/\log(1+h/d)$ 以下である。$\square$