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

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

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

$\cdots$????

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

記号

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

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

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

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

$V_e$の元のうち,$e$で指定した頂点小集合からとった頂点だけを取り出すのが$\pi_e$です.裏を返せば,その逆像が$\pi^{-1}_e(X)=X\times V_{J\backslash e},(X\subset V_e)$と表現できます.逆像$\pi^{-1}_e(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\backslash e}$です.あるいは$V_J=V_e\times V_{J\backslash e}$から$V_e$の一部の元と

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

最後に$E_e$に対して$\pi_e^{-1}(V_e\backslash E_e)$を考えると,$V_e\backslash 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 {J \choose 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{align} H(D_H)&=\left\{ (v_j)_{j\in J}\in \prod_{i\in J}V_j:\forall e\in E ,(v_j)_{j\in e} \in E_e \subset V_e \right\} \end{align}
でした.$\sharp H(D_H)$は
「グラフ$D_H$中に含まれる,各頂点小集合に頂点を1つずつもつような$H$と同型な部分グラフの個数」
を表していました.

定義より,
\begin{align} \mathbb E \left( \prod_{e\in E}\mathbf 1_{E_e}\Bigg|V_J \right)&=\frac{1}{\sharp V_J}\sum_{v\in V_J}\prod_{e\in E}\mathbf 1_{E_e}(v)\\ \end{align}
$\sharp V_J=\Pi_{j \in J}\sharp V_j$です.
$\sum_{v\in V_J}\prod_{e\in E}\mathbf 1_{E_e}(v)=\sharp 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)=\sharp H(D_H)$が確かめられました.

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

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

と

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

これも大丈夫でしょう.
$\mathbb E(\mathbf 1_{E_e\backslash E'_e}|V_J)=\mathbb E(\mathbf1_{\pi_e(E_e)\backslash\pi_e(E'_e)}|V_e)$より分かります.

複雑度条件

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

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

証明の流れ

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

次回

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

感想

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

謝辞

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