グリーン・タオの定理6　ハイパーグラフ除去補題の証明②~理解~

こんにちは,itouです.今回は以下の定理,強化版ハイパーグラフ除去補題を理解していきましょう.強化版ハイパーグラフ除去補題はハイパーグラフ除去補題を前回用意した道具を使って書き直したものです.

まずは定理のステートメントを見てみます.

$\cdots$????

情報量が濃すぎて何を言っているのかよくわかりません.少しずつ解剖していきます.まずは記号を確認しておきます.かなり丁寧にやるので,わかってる方は飛ばしてください.

記号

定理中の$J$は$\mathrm{♯}J=k$なので,$[k]$と考えてもよいです.

頂点小集合$V_j$たちのうち,$r$個を指定するのが$e\subset J$です.$\mathrm{♯}e=r$個の頂点小集合$V_j$に対し,その直積を考えます.

直積$V_e$頂点小集合$V_j$は全然違うので混同しないよう注意してください.なお,$\mathrm{♯}{V}_e={\mathrm{\Pi }}_{j\in e}\mathrm{♯}{V}_j$です.(この$\mathrm{\Pi }$は総積記号)

標準射影の話をします.(本書では説明がない)

$V_e$の元のうち,$e$で指定した頂点小集合からとった頂点だけを取り出すのが${\pi }_e$です.裏を返せば,その逆像が${\pi }_e^{-1}(X)=X\times V_{J\mathrm{\setminus }e},(X\subset V_e)$と表現できます.逆像${\pi }_e^{-1}(X)$は$V_J$の部分集合です.

さて,加法族${\mathcal{A}}_e$を構成します.

$V_e$から任意に部分集合$E_e$をとってきて${\pi }_e^{-1}(E_e)$を考え,すべて集めて集合にしたのが${\mathcal{A}}_e$です.これが実際に加法族であることを確認します.まず,$\varnothing \subset V_e$を取ってくると${\pi }_e^{-1}(\varnothing )=\varnothing$です.(空集合と有限集合の直積は空集合なので)

${\mathcal{A}}_e$の元とは$V_e$の部分集合$X$を選んだ直積$X\times V_{J\mathrm{\setminus }e}$です.あるいは$V_J=V_e\times V_{J\mathrm{\setminus }e}$から$V_e$の一部の元と

また,任意の$E_e,E_e^{\prime }$を取ってきて,${\pi }_e^{-1}(E_e)\cup {\pi }_e^{-1}(E_e^{\prime })$を考えると,${\pi }_e^{-1}(E_e)\cup {\pi }_e^{-1}(E_e^{\prime })=(E_e\times V_{J\mathrm{\setminus }e})\cup (E_e^{\prime }\times V_{J\mathrm{\setminus }e})=(E_e\cup E_e^{\prime })\times V_{J\mathrm{\setminus }e}$となり,これは確かに${\mathcal{A}}_e$に含まれています.

最後に$E_e$に対して${\pi }_e^{-1}(V_e\mathrm{\setminus }{E}_e)$を考えると,$V_e\mathrm{\setminus }{E}_e\subset V_e$より,確かに${\mathcal{A}}_e$に含まれています.

よって${\mathcal{A}}_e$が加法族であることが分かりました.また,作り方より$V_e$と${\mathcal{A}}_e$は1対1で対応していることも分かりました.

定理の主張

主張を追っていきます.前前回の$k$部ハイパーグラフ版ハイパーグラフ除去補題(以下$k$部版という)の主張と照らし合わせて見ていきます.

仮定の記述の対応

まず

$r$グラフ型を用意し,$e\in E\subset (\genfrac{}{}{0ex}{}{J}{r})$をとり,加法族${\mathcal{A}}_e$を考えます.注意すべきは$E_e$を${\mathcal{A}}_e$の元として取っていることです.つまり$E_e\subset V_J$です.先ほどは$V_e$の部分集合として取っていました.($E_e$の取り方は与えられる必要がある)

これは$k$部版では

に対応します.

$H=(J,E),D_H=((V_j{)}_{j\in J};(E_e{)}_{e\in E})$として
$$\begin{array}{rl}H(D_H)& =\{(v_j{)}_{j\in J}\in \prod _{i\in J}{V}_j:\mathrm{\forall }e\in E,(v_j{)}_{j\in e}\in E_e\subset V_e\}\end{array}$$
でした.$\mathrm{♯}H(D_H)$は
「グラフ$D_H$中に含まれる,各頂点小集合に頂点を1つずつもつような$H$と同型な部分グラフの個数」
を表していました.

定義より,
$$\begin{array}{rl}\mathbb{E}\left(\prod _{e\in E}{\mathbf{1}}_{E_e}|V_J\right)& =\frac{1}{\mathrm{♯}{V}_J}\sum _{v\in V_J}\prod _{e\in E}{\mathbf{1}}_{E_e}(v)\end{array}$$
$\mathrm{♯}{V}_J={\mathrm{\Pi }}_{j\in J}\mathrm{♯}{V}_j$です.
$\sum _{v\in V_J}\prod _{e\in E}{\mathbf{1}}_{E_e}(v)=\mathrm{♯}H(D_H)$であることを確認します.

$\prod _{e\in E}{\mathbf{1}}_{E_e}(v)$は$v\in V_J$が各$E_e$すべてに含まれている場合のみ$1$,そうでないなら$0$を返す関数です.
つまり,$v$が$k$個の各頂点小集合に頂点を1つずつもつ$H$と同型な部分グラフの頂点集合である場合,$1$を返す(カウントする)ということです.

そして,すべての$v\in V_J$について数え上げるので,結局
$\sum _{v\in V_J}\prod _{e\in E}{\mathbf{1}}_{E_e}(v)$は

「各頂点小集合に頂点を1つずつもつ$H$と同型な部分グラフの個数」
であるので
$\sum _{v\in V_J}\prod _{e\in E}{\mathbf{1}}_{E_e}(v)=\mathrm{♯}H(D_H)$が確かめられました.

$H$の除去の記述の対応

この対応を見ていきます.

と

の対応はわかりやすいですね.$H$を除去した後,もう$H$が含まれていないことを表しています.$E_e$の取り方が違うので,強化版の方がすっきりと記述できています.

これも大丈夫でしょう.
$\mathbb{E}({\mathbf{1}}_{E_e\mathrm{\setminus }{E}_e^{\prime }}|V_J)=\mathbb{E}({\mathbf{1}}_{{\pi }_e(E_e)\mathrm{\setminus }{\pi }_e(E_e^{\prime })}|V_e)$より分かります.

複雑度条件

最後に複雑度条件について考えます.

$f$は$e$同様に$J$の中からいくつか指定する働きを持っています.$f$ごとに加法族${\mathcal{A}}_f$をとると,その「あまり複雑でない」部分加法族の集合$({\mathcal{B}}_f{)}_{f\in R}$について
$$\begin{array}{r}{E}_e^{\prime }\in \underset{f⊊e}{\bigvee }{\mathcal{B}}_f\end{array}$$
であるということです.イメージが付きづらいですが,多次元セメレディの定理の証明には不要だそうなので,とりあえず流しておきます.

証明の流れ

正則化補題,数え上げ補題を先に示し,それらを用いてハイパーグラフ除去補題を証明します.

次回

定理を理解するのにかなり時間がかかりましたが,次こそは証明に入ります.正則化補題をやります.

感想

主張理解するだけでこんなにかかるとは...

謝辞

ここまで読んで下さりありがとうございました.誤植等指摘よろしくお願いいたします.