PCP定理とその証明 (準備編)

後半の「特に, ...」の部分は前半の主張に$T=\overline{S}$を代入して$|\overline{S}|\geq \frac{n}{2}$を用いれば簡単に示せるので, 以後, 前半の主張を証明します.

$G$の隣接行列を$A\in\binset^{V\times V}$, $S,T\subseteq V$の支持ベクトルをそれぞれ$\indicator_S,\indicator_T\in\binset^V$とします. $G$は正則グラフなので, 唯一の第一固有ベクトルは$\indicator=\indicator_V$であり, それ以降の固有ベクトルは全て$\indicator$に直交します. ここで, 二つのベクトル$x:=\indicator_S-\frac{|S|}{n}\indicator, y:=\indicator_T-\frac{|T|}{n}\indicator$はどちらも$\indicator$に直交するので,
\begin{align*} |E(S,T)| &= \indicator_S^\top A \indicator_T \\ &= \left(\indicator_S - \frac{|S|}{n}\indicator\right)^\top A \left( \indicator_T - \frac{|T|}{n}\indicator\right) + \frac{|S||T|}{n^2}\indicator^\top A \indicator \\ &= x^\top A y + \frac{d}{n}|S||T|. \end{align*}
従って
\begin{align*} \left||E(S,T)| - \frac{d}{n}|S||T|\right| &= |x^\top A y| \\ &\leq d\lambda \|x\|\|y\| \\ &= \frac{d\lambda}{n}\sqrt{|S||T||\overline{S}||\overline{T}|} \end{align*}
より主張を得ます.

与えられた制約グラフを$G=((V,E),\Sigma,\mathcal{C})$とし, 変換後の制約グラフを$G'=((V',E'),\Sigma,\mathcal{C}')$と書くことにします.

元のグラフの各頂点$v\in V$に対し, $[v]=\{(v,e)\colon v\in e\}$とします. すなわち$v$とそれに接続する辺$e$の組からなる集合です. 新しいグラフの頂点集合$V'$は$V'=\bigcup_{v\in V}[v]$とします.

直感的には, 元のグラフの各頂点$v$に対しそれを$\deg(v)$個にコピーし, それぞれのコピーに接続辺$e$のラベルを一個ずつ付与したものを新たな頂点としています.
なお, 元の制約グラフが自己ループ$vv$を含む場合, $[v]$は$(v,vv)$を二つ含む(つまり多重集合になる)とします. このようにすることによって, 各辺$uv$に対して二つの頂点$(u,uv),(v,uv)$が生成されるので, $|V'|=2|E|$が成り立ちます (なお, 自己ループを一つの頂点として$[v]$を定義した場合でも同じ証明が回るので問題ありません).

次に新しいグラフの辺集合$E'$を次の定義します.

1. 定理2を用いて各$v\in V$に対して$[v]$を頂点集合とした$\deg(v)$-頂点$d_0$-正則$\lambda_0$-エクスパンダーグラフ$X_v$を構成します. このステップで追加された辺を内部辺と呼び, 等号制約$\{(a,b)\in \Sigma^2\colon a=b\}$を付与します.

2. 同じ辺ラベルを持つ二つの$V'$の頂点$(u,uv),(v,uv)$の間に辺を追加します. このステップで追加された辺$\{(u,uv),(v,uv)\}$を外部辺と呼び, 元の制約グラフの辺$uv$の制約$c(uv)$を付与します.

上記の二つのステップで構成された辺集合を$E'$と定めます.

$G'$の構造グラフのイメージ図.

図からすぐわかるように, ステップ2で追加された辺は$V'$上のマッチングになっています. 図では$d_0=2$としたときの例になっていますが, 定理2の$d_0$の値によっては, 例えば6-正則3頂点グラフなどを考えることもありますが, その際は多重辺や自己ループを適当につけることにします.

定義より構造グラフ$(V',E')$は$(d_0+1)$-正則グラフになっています. 頂点数は$|V'|=2|E|$で, 辺数は$|E'|=\frac{|V'|(d_0+1)}{2}=(d_0+1)|E|$です. 次に$\UNSAT(G')$の値を評価します.

$\UNSAT(G,\sigma)=\UNSAT(G)$を達成する割当を$\sigma\in\Sigma^V$とします. $G'$の割当$\sigma'\colon V'\to \Sigma$を$\sigma'(v,e)=\sigma(v)$で定めます.
$\sigma'$は内部辺の等号制約を全て満たすので, 充足されない辺の本数は$\sigma$のそれと一致します. よって
\begin{align*} \UNSAT(G')\leq \UNSAT(G',\sigma') = \frac{|E|\UNSAT(G,\sigma)}{(d_0+1)|E|} = \frac{1}{d_0+1}\cdot \UNSAT(G) \end{align*}
を得ます.

次に$\UNSAT(G')$の下界, すなわち, ある($G$に依存しない)定数$c>0$に対して$\UNSAT(G',\sigma')\geq c\cdot \UNSAT(G,\sigma)$を満たすことを示します.
$\sigma'\colon V'\to\Sigma$を$\UNSAT(G',\sigma')=\UNSAT(G)$を達成する$G'$の割当とし, 各$v\in V$に対して$\sigma(v)=$「$W_v$内の$\sigma'(\cdot)$の値の中での多数決」, すなわち
\begin{align*} \sigma(v) = \argmax_{a\in\Sigma}\left\{\Pr_{i\sim W_v}[\sigma'(i)=a]\right\} \end{align*}
とします. $F\subseteq E$を, $G$の辺であって$\sigma$によって充足されないものの集合とし, $F'\subseteq E'$を同様に$G'$の辺であって$\sigma'$によって充足されないものの集合とします. つまり$\UNSAT(G',\sigma')=\frac{|F'|}{|E|}$, $\UNSAT(G,\sigma)=\frac{|F|}{|E|}$です.
$S\subseteq V'$を多数決によって意見が採用されなかった頂点の集合, すなわち
$$ S = \{(v,e)\in V'\colon \sigma'(v,e) \neq \sigma(v)\} $$
とします.

ここで, 以下の二つのケースを考えます:

ケース1. $|S|\geq \frac{\UNSAT(G,\sigma)}{2}|E|$の場合.

各$v\in V,a\in\Sigma$に対して$S^v=[v]\cap S$, $S^v_a = \{(v,e)\in S^v\colon \sigma'(v,e)=a\}$とします. なお, 意見$a$が多数決で採用されている場合(つまり$\sigma(v)=a$の場合)は$S^v_a=\emptyset$であり, そうでない場合は過半数をとれていないはずなので$|S^v_a|\leq \frac{|[v]|}{2}$が成り立ちます.

$[v]$内の各頂点$(v,e)$は意見$\sigma'(v,e)$を持ち, その多数決によって$\sigma(v)$を定める. 多数決にならなかった頂点$(v,e)$の集合(=青い領域)を$S$とする.

そこで$[v]$内部のグラフ$X_v$とその頂点部分集合$S^v_a$に対して定理3(エクスパンダー混交補題)を適用することによって,
$$ |E(S^v_a,[v]\setminus S^v_a)| \geq \frac{(1-\lambda)d_0}{2}|S^v_a| $$
を得ます. この式の左辺は$S^v_a$とその外側をつなぐ内部辺の本数を意味しますが, これらの辺は$G'$において, 内部辺の等号制約を満たしていないはずであり, すなわち$F'$に属すので
\begin{align*} |F'|\geq \frac{1}{2}\sum_{v,a}|E(S^v_a,[v]\setminus S^v_a)| \geq \frac{(1-\lambda_0)d_0}{4}|S| \end{align*}
により, $|S|$の仮定から
$$ \UNSAT(G')\geq \frac{(1-\lambda_0)d_0}{8(d_0+1)}\cdot \UNSAT(G) $$
を得ます.

ケース2. $|S|< \frac{\UNSAT(G,\sigma)}{2}|E| $の場合.

任意の辺$e=uv\in F$に対して, その両端点が多数決で意見が変わらなかったならば, $E'$の辺$\{(u,e),(v,e)\}$もまた$F'$に属しているはずです. 一方でそうでなかったならば$(u,e)$または$(v,e)$の少なくとも一方が$S$に属します. すなわち
$$ |F|\leq |F'|+|S| $$
が成り立ちます. ここから
\begin{align*} |F'|&\geq |F|-|S| \\ &\geq |E|\cdot\UNSAT(G) - \frac{\UNSAT(G)}{2}|E| \\ &= \frac{1}{2(d_0+1)}\UNSAT(G)\cdot |E'| \end{align*}
を得ます.

以上より, $c=\min\left\{\frac{(1-\lambda_0)d_0}{8(d_0+1)},\frac{1}{2(d_0+1)}\right\}$に対して$\UNSAT(G')\geq c\UNSAT(G)$を得ます.

与えられた制約グラフを$G=((V,E),\Sigma,\mathcal{C})$とし, 変換後の制約グラフを$G'=((V',E'),\Sigma,\mathcal{C}')$と書くことにします.

$G'$の構成は簡単です.

1. 頂点集合$V$上の$d_0$-正則$\lambda_0$エクスパンダーを構成してその辺集合を$E$に追加する (多重辺を許す).
2. 各頂点に対して自己ループを付与する.
3. ステップ1,2で追加された辺$e$には常に充足される自明な制約$c(e)=\Sigma\times \Sigma$を付与する.

元のグラフ$(V,E)$が$d$-正則ならば, $G'$の構造グラフは$(d+d_0+2)$-正則になります (自己ループの辺の次数は2つ分にカウントしている).

$\sigma,\sigma,\colon V\to \Sigma$をそれぞれ$G,G'$の割当とします. 追加された辺は全て自明な制約しか付与されていないので, 充足されなかった辺の本数は$G,G'$で一致します.
よって$|E|\UNSAT(G)=|E'|\UNSAT(G')$なので
$$ \UNSAT(G') = \frac{|E|}{|E'|}\UNSAT(G) = \frac{d}{d+d_0+2}\UNSAT(G) $$
を得ます.

最後に$(V,E')$のエクスパンダー性を示します.
$A,A'$をそれぞれ$(V,E),(V,E')$の隣接行列とし, $B$をステップ1で追加したエクスパンダーグラフの隣接行列とし, $I$を単位行列とします. $(V,E')$の定義より$A'=A+B+2I$です (自己ループの次数が2としてカウントされているので$2I$になっています). 対称行列$M$の固有値が$\lambda_1\geq \dots\geq \lambda_n$のとき, $\lambda(M)=\max\{\lambda_2,|\lambda_n|\}$とします. 第二固有値に関するmin-max定理(Courant–Fischerの最大最小定理)より,
\begin{align*} \lambda(A') \leq \max_{\|x\|=1,x\bot \indicator=0}|x^\top A' x| \leq \lambda(A) + \lambda(B) + 2\lambda(I) \leq d + \lambda_0 d_0 + 2 \end{align*}
より, $P'=\frac{1}{d+d_0+2}A'$を$(V,E')$の遷移確率行列とすると
$$ \lambda(P') \leq \frac{d+\lambda_0 d_0+2}{d+d_0+2} $$
となります. すなわち, $\lambda:=\frac{d+\lambda_0 d_0+2}{d+d_0+2}<1$に対して$(V,E')$は$\lambda$-エクスパンダーです.