グリーン・タオの定理7　ハイパーグラフ除去補題の証明③ ～正則化補題～

こんにちは,itouです.今回はハイパーグラフ除去補題の証明に用いる正則化補題の解説をしていきます.

気持ちとしては,グラフに含まれるハイパーグラフを除去するためにその個数を数え上げたいので,グラフに上手く分割構造を与えることでランダムグラフのようにします(正則化補題).ランダムグラフなら数えやすいからです.そのように正則化したグラフを数え上げるのが数え上げ補題です.

今回は正則化補題を解説していきます.すべての補題,命題の証明はせず,重要な部分のみ解説します.

正則化補題

定義,補題

まだ新しい言葉が出てくるのかと思いますが,今までの内容の延長にすぎません.

今後は$e$に対する加法族を直接考えていくのでなく,$e$の骨格からできる加法族たちを用いて間接的に取り扱っていきます.

食い違い${\mathrm{△}}_e(A|\mathcal{B})$が小さいとき,$A$は$\mathcal{B}$のほとんどのアトム上で「ランダムな」ように振る舞います.これが求めている状況です.

(証明略)
正則化補題は反復アルゴリズムによって示されるのですが,エネルギーはそのための量です.
次の命題は食い違いがエネルギーを増加させることを示します.

(証明略)
骨格からできる加法族たちについて,それらを細分すると複雑度は高々1しか増加せず,エネルギーが増加するということです.${\mathcal{B}}_f$たちには「良い」分割が取れるのです.これが骨格を考える理由です.

前正則化補題

前正則化補題を示し,それにより正則化補題を示します.前正則化補題の主張は以下の通りです.

$e$に対する加法族${\mathcal{A}}_e$の部分加法族たちを$f\in \partial E$に対する加法族${\mathcal{A}}_f$の部分加法族たちによって取り扱います.${\mathcal{B}}_f$たちの細分を取っていくとエネルギーが増加するが,食い違いが小さくなってくれるようにできるということです.複雑度の条件はあまり気にしなくてよいです.これを反復アルゴリズムによって示します.

前正則化補題のアルゴリズム

前半

(状態1)か(状態2)のどちらかが実現されると停止するアルゴリズムを考えます.

以上のアルゴリズムにより,必ず(状態1),(状態2)のいずれかが成立するようにできます.$(\mathrm{ii})$で停止すれば(状態1)です.

後半

証明
$r\in [k]$に関する数学的帰納法で証明する.ただし,$r$ごとにある正整数$C_{RL}^{(r)}(k,M,F)$が存在することを示し,最終的に$C_{RL}^{(r)}(k,M,F)=\underset{r\in [k]}{max}{C}_{RL}^r(k,M,F)$とする.

関数$F^{\prime }=F^{\prime }(k,r,F):{\mathbb{Z}}_{>0}\to {\mathbb{Z}}_{>0}$を$r=1$のときは$F,r\ge 2$のとき($r-1$における正則化補題の成立が仮定されているとき)は各$n\in {\mathbb{Z}}_{>0}$に対して
$$\begin{array}{r}{F}^{\prime }(n)=max\{F(n),\underset{l\in [n]}{max}{C}_{RL}^{r-1}(k,l,m)\}\end{array}$$
と定義する(これは単調増大).データ$(m,\epsilon ,F)$を$(M_0,F(M_0{)}^{-1},F^{\prime })$として前正則化補題を適用すると,正整数$M_1$および$f\in \partial E$について${\mathcal{B}}_f\subset {\mathcal{B}}_f^{\prime }\subset {\mathcal{A}}_f$であるような$V_J$上の加法族のペアの族$(({\mathcal{B}}_f,{\mathcal{B}}_f^{\prime }){)}_{f\in \partial E}$が存在して,以下が成立する.

これで$r=1$のときは示された.実際,$C^{(}1{)}_{RL}(k,m,F)=F(C_{PRL}(k,M,F(M{)}^{-1},F))$とすればよい.以下,$r\ge 2$として$r-1$における正則化補題の成立を仮定する.

データ$(k,M_1,F)$および$(r-1)$グラフ型$((J,\partial E);(V_j{)}_{j\in J})$,上の$({\mathcal{B}}_f{)}_{f\in \partial E}$に対して帰納法の仮定を適用して,
$$\begin{array}{r}{M}_1\le F(M_1)\le M_2\le F(M_2)\le \cdots \le M_r\le F(M_r)\le C_{RL}^{(r-1)}(k,M_1,F)\end{array}$$
を満たす整数列$(M_j{)}_{j\in [2,r]}$が存在し,さらに各$f\in \bigcup _{j\in [2,r]}{\partial }^{j}E$について${\mathcal{B}}_f\subset {\mathcal{B}}_f^{\prime }\subset A_f$であるような$V_J$上の加法族のペアの族$(({\mathcal{B}}_f,{\mathcal{B}}_f^{\prime }){)}_{f\in \bigcup _{j\in [2,r]}{\partial }^{j}E}$が存在して,全ての$j\in [2,r],f\in {\partial }^{j}E$に対して
$$\begin{array}{r}\mathrm{c}\mathrm{p}\mathrm{x}({\mathcal{B}}_{\mathrm{f}})\le {\mathrm{M}}_{\mathrm{j}}\end{array}$$
が成り立ち,全ての$j\in [r-1],e\in {\partial }^{j}E$および$E_e\in {\mathcal{B}}_e$に対して
$$\begin{array}{r}{\mathcal{E}}_{E_e}\left(\underset{f\in \partial e}{\bigvee }{\mathcal{B}}_f^{\prime }\right)-{\mathcal{E}}_{E_e}\left(\underset{f\in \partial e}{\bigvee }{\mathcal{B}}_f\right)\le \frac{1}{F(M_j{)}^2}\end{array}$$
および
$$\begin{array}{r}{\mathrm{△}}_e\left(E_e|\underset{f\in \partial e}{\bigvee }{\mathcal{B}}_f^{\prime }\right)\le \frac{1}{F(M_r)}\end{array}$$
が成り立つ.

このとき,$F^{\prime }$の定義より
$$\begin{array}{r}F(M_r)\le C_{RL}^{(r-1)}(k,M_1,F)\le F^{\prime }(M_1)\end{array}$$
なので,$F^{\prime }(M_1{)}^{-1}\le F(M_r{)}^{-1}$が成立.また,

$$\begin{array}{r}{C}_{RL}^{(r)}(k,M,F)=\underset{n\in [C_{PRL}(k,M,F(M{)}^{-1},F^{\prime }(k,r,F))]}{max}{C}_{RL}^{(r-1)}(k,n,F)\end{array}$$

と定めると,$C_{RL}^{(r-1)}(k,M_1,F)\le C_{RL}^{(r)}(k,M_0,F)$である.したがって,$r$の場合も示された.