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

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

$G$の隣接行列を$A\in \{0,1{\}}^{V\times V}$, $S,T\subseteq V$の支持ベクトルをそれぞれ${\mathbf{1}}_S,{\mathbf{1}}_T\in \{0,1{\}}^V$とします. $G$は正則グラフなので, 唯一の第一固有ベクトルは$\mathbf{1}={\mathbf{1}}_V$であり, それ以降の固有ベクトルは全て$\mathbf{1}$に直交します. ここで, 二つのベクトル$x:={\mathbf{1}}_S-\frac{|S|}{n}\mathbf{1},y:={\mathbf{1}}_T-\frac{|T|}{n}\mathbf{1}$はどちらも$\mathbf{1}$に直交するので,
$$\begin{array}{rl}|E(S,T)|& ={\mathbf{1}}_S^{\mathrm{\top }}A{\mathbf{1}}_T\\ & ={({\mathbf{1}}_S-\frac{|S|}{n}\mathbf{1})}^{\mathrm{\top }}A({\mathbf{1}}_T-\frac{|T|}{n}\mathbf{1})+\frac{|S||T|}{n^2}{\mathbf{1}}^{\mathrm{\top }}A\mathbf{1}\\ & =x^{\mathrm{\top }}Ay+\frac{d}{n}|S||T|.\end{array}$$
従って
$$\begin{array}{rl}||E(S,T)|-\frac{d}{n}|S||T||& =|x^{\mathrm{\top }}Ay|\\ & \le d\lambda \parallel x\parallel \parallel y\parallel \\ & =\frac{d\lambda }{n}\sqrt{|S||T||\bar{S}||\bar{T}|}\end{array}$$
より主張を得ます.

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

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

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

次に新しいグラフの辺集合$E^{\prime }$を次の定義します.

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

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

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

$G^{\prime }$の構造グラフのイメージ図.

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

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

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

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

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

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

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

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

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

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

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

以上より, $c=min\{\frac{(1-{\lambda }_0)d_0}{8(d_0+1)},\frac{1}{2(d_0+1)}\}$に対して$\mathrm{UNSAT}(G^{\prime })\ge c\mathrm{UNSAT}(G)$を得ます.

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

$G^{\prime }$の構成は簡単です.

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

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

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

最後に$(V,E^{\prime })$のエクスパンダー性を示します.
$A,A^{\prime }$をそれぞれ$(V,E),(V,E^{\prime })$の隣接行列とし, $B$をステップ1で追加したエクスパンダーグラフの隣接行列とし, $I$を単位行列とします. $(V,E^{\prime })$の定義より$A^{\prime }=A+B+2I$です (自己ループの次数が2としてカウントされているので$2I$になっています). 対称行列$M$の固有値が${\lambda }_1\ge \cdots \ge {\lambda }_n$のとき, $\lambda (M)=max\{{\lambda }_2,|{\lambda }_n|\}$とします. 第二固有値に関するmin-max定理(Courant–Fischerの最大最小定理)より,
$$\begin{array}{r}\lambda (A^{\prime })\le \underset{\parallel x\parallel =1,x\mathrm{\perp }\mathbf{1}=0}{max}|x^{\mathrm{\top }}{A}^{\prime }x|\le \lambda (A)+\lambda (B)+2\lambda (I)\le d+{\lambda }_0{d}_0+2\end{array}$$
より, $P^{\prime }=\frac{1}{d+d_0+2}{A}^{\prime }$を$(V,E^{\prime })$の遷移確率行列とすると
$$\lambda (P^{\prime })\le \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^{\prime })$は$\lambda$-エクスパンダーです.