Lovászの局所補題

$i$ と、$\Gamma(i)\cup\{i\}$ と交わらない $T$ をとる。$W:=\bigcup_{j\in T}U_j$ とおくと、$D$ の定め方から $W\cap U_i=\emptyset$ であり、$C_T$ に属するかどうかは $W$ の座標だけで決まる。$U:=U_i$ とし、$\omega$ を $U$ の部分 $\omega_U$、$W$ の部分 $\omega_W$、残り $\omega_R$ に分ける。積の確率の定義から、$U$ の座標の値の組 $a$ について $P(\omega_U=a)=\prod_{v\in U}P_v(\{a_v\})$ であり、$W$・$R$ についても同様で、$P(\omega_U=a,\ \omega_W=b)=P(\omega_U=a)\,P(\omega_W=b)$ である（残り $R$ の座標について和をとると、その因子の和は $1$ になる）。$A_i$ を与える $U$ の値の集合を $\mathcal A$、$C_T$ を与える $W$ の値の集合を $\mathcal C$ とすると
$$ P(A_i\cap C_T)=\sum_{a\in\mathcal A}\sum_{b\in\mathcal C}P(\omega_U=a)\,P(\omega_W=b)=P(A_i)\,P(C_T) $$
である。$\square$

主張。 $T\subset\{1,\dots,m\}$、$i\notin T$ で $P(C_T)>0$ なら、$P(A_i\mid C_T)\le x_i$ である。
$\lvert T\rvert$ についての帰納法で示す。$T_1:=T\cap\Gamma(i)$、$T_2:=T\setminus T_1$ とおく。$T_2$ は $\Gamma(i)\cup\{i\}$ と交わらないので、依存グラフの条件から $P(A_i\cap C_{T_2})=P(A_i)P(C_{T_2})$ であり、$C_T\subset C_{T_2}$ から $P(C_{T_2})\ge P(C_T)>0$ である。
$T_1=\emptyset$ なら $T=T_2$ で、$P(A_i\mid C_T)=P(A_i)\le x_i$ である（$x_i$ に掛かる積は $1$ 以下）。$T_1=\{j_1,\dots,j_r\}$（$r\ge1$）とする。$C_T=C_{T_1}\cap C_{T_2}$ なので
$$ P(A_i\mid C_T)=\frac{P(A_i\cap C_{T_1}\cap C_{T_2})}{P(C_{T_1}\cap C_{T_2})}\le\frac{P(A_i\cap C_{T_2})}{P(C_{T_1}\cap C_{T_2})}=\frac{P(A_i)}{P(C_{T_1}\mid C_{T_2})} $$
である。分母は 条件付き確率 の命題「乗法公式」により
$$ P(C_{T_1}\mid C_{T_2})=\prod_{l=1}^r\Bigl(1-P\bigl(A_{j_l}\bigm|C_{T_2\cup\{j_1,\dots,j_{l-1}\}}\bigr)\Bigr) $$
と書ける。条件の事象はどれも $C_T$ を含むので確率が正であり、$T_2\cup\{j_1,\dots,j_{l-1}\}$ は $j_l$ を含まず、要素の個数は $\lvert T\rvert-1$ 以下である。帰納法の仮定から各因子は $1-x_{j_l}$ 以上であり、$\{j_1,\dots,j_r\}\subset\Gamma(i)$ と $0<1-x_j\le1$ から
$$ P(C_{T_1}\mid C_{T_2})\ge\prod_{j\in T_1}(1-x_j)\ge\prod_{j\in\Gamma(i)}(1-x_j)>0 $$
である。仮定 $P(A_i)\le x_i\prod_{j\in\Gamma(i)}(1-x_j)$ と合わせて $P(A_i\mid C_T)\le x_i$ を得る。
結論。 $k=1,\dots,m$ について $Q_k:=C_{\{1,\dots,k\}}$、$Q_0:=\Omega$ とおく。$P(Q_{k-1})>0$ なら主張から
$$ P(Q_k)=P(Q_{k-1})\bigl(1-P(A_k\mid Q_{k-1})\bigr)\ge P(Q_{k-1})(1-x_k)>0 $$
であり、$P(Q_0)=1$ から順に $P(Q_k)\ge\prod_{i\le k}(1-x_i)$ が成り立つ。$k=m$ として結論を得る。$\square$

$d=0$ なら $\Gamma(i)=\emptyset$ なので、$x_i:=p\le1/e<1$ とおけば thm-lll-main の仮定が成り立つ。$d\ge1$ なら $x_i:=\frac1{d+1}$ とおく。$(1+\frac1d)^d\le e$（$\log(1+t)\le t$ による）なので $(1-\frac1{d+1})^d=(1+\frac1d)^{-d}\ge\frac1e$ であり、$\lvert\Gamma(i)\rvert\le d$ から
$$ x_i\prod_{j\in\Gamma(i)}(1-x_j)\ge\frac1{d+1}\Bigl(1-\frac1{d+1}\Bigr)^d\ge\frac1{e(d+1)}\ge p\ge P(A_i) $$
である。thm-lll-main により結論を得る。$\square$

$x_i:=2P(A_i)$ とおく。仮定から $x_i\le\frac12<1$ である。$0\le t_j\le1$ について $\prod_j(1-t_j)\ge1-\sum_jt_j$（$t_j$ の個数についての帰納法）なので
$$ x_i\prod_{j\in\Gamma(i)}(1-x_j)\ge2P(A_i)\Bigl(1-2\sum_{j\in\Gamma(i)}P(A_j)\Bigr)\ge2P(A_i)\Bigl(1-\frac12\Bigr)=P(A_i) $$
である。thm-lll-main により結論を得る。$\square$

各命題変数の真理値を独立に確率 $\frac12$ ずつで決める（$2^N$ 通りの付値が等確率の有限確率空間）。節 $c$ が偽になる事象を $A_c$ とする。$c$ が偽になるのは $c$ の $k$ 個のリテラルがすべて偽のときで、それらは相異なる変数のリテラルなので $P(A_c)=2^{-k}$ である。$A_c$ は $c$ に現れる変数の値だけで決まるので、lem-lll-variables により、変数を共有する節どうしを結んだグラフは依存グラフであり、その次数は $d$ 以下である。$e\cdot2^{-k}(d+1)\le1$ なので、cor-lll-symmetric により、どの節も偽にならない付値が存在する。$\square$

節がなければ明らかなので、節が 1 つ以上あるとし、各変数が現れる節の個数の最大値を $t$ とする（$1\le t\le2^k/(ek)$）。節 $c$ と変数を共有するほかの節は、$c$ の $k$ 個の変数のそれぞれについて高々 $t-1$ 個なので、次数は $d:=k(t-1)$ 以下であり、$d+1\le kt\le2^k/e$ である。thm-lll-ksat による。$\square$

各辺の色を独立に確率 $\frac12$ ずつで決める。$k$ 個の頂点の集合 $S$ ごとに、$S$ の中の $\binom k2$ 本の辺が同じ色になる事象を $A_S$ とすると、$P(A_S)=2\cdot2^{-\binom k2}$ である。$A_S$ は $S$ の中の辺の色だけで決まるので、lem-lll-variables により、$S$ と $T$ が辺を共有する、すなわち $\lvert S\cap T\rvert\ge2$ のときに結んだグラフは依存グラフである。$\lvert S\cap T\rvert\ge2$ となる $T\neq S$ は、$S\cap T$ に含まれる 2 頂点を選び（$\binom k2$ 通り）、残りの $k-2$ 頂点を選ぶ（$\binom{n-2}{k-2}$ 通り）ことで、重複を許してすべて数えられるので、次数は $d:=\binom k2\binom{n-2}{k-2}$ 以下である。仮定は $e\,P(A_S)(d+1)\le1$ なので、cor-lll-symmetric により、どの $A_S$ も起こらない塗り分けがある。$\square$

$[n]$ の各元の色を独立に確率 $\frac12$ ずつで決める。$[n]$ の中の $k$ 項の等差数列 $Q$ ごとに、$Q$ が単色になる事象を $A_Q$ とすると $P(A_Q)=2^{1-k}$ である。$A_Q$ は $Q$ の元の色だけで決まるので、lem-lll-variables により、共通の元をもつ等差数列どうしを結んだグラフは依存グラフである。
その次数を数える。$x\in[n]$ を含む $k$ 項の等差数列は、$x$ が何項目か（$k$ 通り）と公差 $\delta$ で決まる。$x$ が $j+1$ 項目（$0\le j\le k-1$）なら、最初の項 $x-j\delta\ge1$ と最後の項 $x+(k-1-j)\delta\le n$ から $(k-1)\delta\le n-1$ である。よって $x$ を含むものは高々 $k\frac{n-1}{k-1}$ 個である。$Q$ と共通の元をもつ $Q'\neq Q$ は $Q$ の $k$ 個の元のどれかを含むので、高々 $k^2\frac{n-1}{k-1}\le2k(n-1)$ 個である（$k\ge2$ で $\frac{k}{k-1}\le2$）。$d:=2k(n-1)$ とおくと $d+1\le2kn$ なので
$$ e\,P(A_Q)(d+1)\le e\cdot2^{1-k}\cdot2kn=\frac{e\,k\,n}{2^{k-2}}\le1 $$
である。cor-lll-symmetric により、どの $A_Q$ も起こらない塗り分けがある。$\square$