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

153

この著者は初心者として投稿しています。間違いや考慮が足りていない点が含まれている可能性が高いです。見つけたらコメント欄で優しく指摘してあげましょう。

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

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

記法

$(H; (V_{j})_{j \in J})$ を $r$ グラフ型とする. $J$ の部分集合 $e \subset J$ に対して,以下の記法を用いる. $V_{e} = \prod_{j \in e} V_{j}$ と略記し,とくに $V_{J} = \prod_{j \in J} V_{j}$ とする. $π_{e} : V_{J} ↠ V_{e}$ を標準射影とする.また, $A_{e} = {π_{e}^{- 1} (E_{e}) \in (V_{J}) : E_{e} \in (V_{e})}$ とする.

強化版ハイパーグラフ除去補題

正整数 $k$ と正の実数 $ε > 0$ に対して, $δ = δ_{S H R L} (k, ε)$ および $C = C_{S H R L} (k, ε) > 0$ が存在して,以下が成立する. $((J, E); (V_{j})_{j \in J})$ を $♯ J = k$ であるような $r$ グラフ型 $(r \in [k])$ とし,各 $e \in E$ ごとに $E_{e} \in A_{e}$ を考える.
$\begin{array}{r} E (\prod_{e \in E} 1_{E_{e}} | V_{J}) \leq δ \end{array}$
が満たされるならば,ある $(E_{e}^{'})_{e \in E} \in \prod_{e \in E} A_{e}$ が存在して
$\begin{array}{r} ⋂_{e \in E} E_{e}^{'} = \emptyset \end{array}$
かつ任意の $ε \in E$ に対して
$\begin{array}{r} E (1_{E_{e} ∖ E_{e}^{'}} | V_{J}) \leq ε \end{array}$
が成立.さらに以下の複雑度条件を満たすように $(E_{e}^{'})_{e \in E}$ をとることができる.各 $f \in R = {f \in B (J) : ♯ f \in [0, r - 1]}$ に対して $B_{f}$ が $A_{f}$ の部分加法族であるような族 $(B_{f})_{f \in R}$ が存在して,任意の $f \in R$ に対して
$\begin{array}{r} c p x (B_{f}) \leq C \end{array}$
が成り立ち,任意の $e \in E$ に対して
$\begin{array}{r} E_{e}^{'} \in \underset{f ⊊ e}{⋁} B_{f} \end{array}$
が成り立つ.

$\dots$ ????

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

記号

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

集合族 $(V_{j})_{j \in [k]}$

$(V_{j})_{j \in [k]} = {V_{1}, \dots, V_{k}}$ である.各頂点小集合 $V_{j}$ は頂点の有限個の集合.

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

直積 $V_{e} = \prod_{j \in e} V_{j}$

$\begin{array}{r} V_{e} = \prod_{j \in e} V_{j} = {(v_{j})_{j \in e} : (v_{j} \in V_{j}), \forall j \in e} \end{array}$
である. $V_{j}$ は頂点小集合で, $V_{e}$ は指定した $♯ e$ 個の頂点小集合から１つずつ元(頂点)をとってきた組のこと.

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

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

標準射影

$e \subset J$ とし,全射写像 $π_{e}$ を
$\begin{array}{r} π_{e} : \prod_{j \in J} V_{j} \to \prod_{j \in e} V_{j} \\ (v_{j})_{j \in J} \mapsto (v_{j})_{j \in e} \end{array}$
と定義する.

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

さて,加法族 $A_{e}$ を構成します.

加法族 $A_{e}$

$A_{e} = {π_{e}^{- 1} (E_{e}) \in P (V_{J}) : E_{e} \in P (V_{e})}$ と定義する.

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

$A_{e}$ の元とは $V_{e}$ の部分集合 $X$ を選んだ直積 $X \times V_{J ∖ e}$ です.あるいは $V_{J} = V_{e} \times V_{J ∖ e}$ から $V_{e}$ の一部の元と

また,任意の $E_{e}, E_{e}^{'}$ を取ってきて, $π_{e}^{- 1} (E_{e}) \cup π_{e}^{- 1} (E_{e}^{'})$ を考えると, $π_{e}^{- 1} (E_{e}) \cup π_{e}^{- 1} (E_{e}^{'}) = (E_{e} \times V_{J ∖ e}) \cup (E_{e}^{'} \times V_{J ∖ e}) = (E_{e} \cup E_{e}^{'}) \times V_{J ∖ e}$ となり,これは確かに $A_{e}$ に含まれています.

最後に $E_{e}$ に対して $π_{e}^{- 1} (V_{e} ∖ E_{e})$ を考えると, $V_{e} ∖ E_{e} \subset V_{e}$ より,確かに $A_{e}$ に含まれています.

よって $A_{e}$ が加法族であることが分かりました.また,作り方より $V_{e}$ と $A_{e}$ は1対1で対応していることも分かりました.

定理の主張

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

k

部ハイパーグラフ版ハイパーグラフ除去補題

正整数 $k$ と正の実数 $ε > 0$ に対して, $δ = δ_{P H R L} (k, ε)$ が存在して,以下が成立する. $(H; (V_{j})_{j \in J})$ を $♯ J = k$ であるような $r$ グラフ型 $(r \in [k])$ , $E$ を $H$ の辺集合とする.各 $e \in E$ ごとに集合 $E_{e} \subset Π_{i \in J} V_{j}$
を考える.もし
$\begin{array}{r} ♯ H ((V_{j})_{j \in J}; (E_{e})_{e \in E}) \leq δ Π_{j \in J} ♯ V_{j} \end{array}$
が満たされるならば,各 $e \in E$ に対して $E_{e}^{'} \subset \prod_{j \in J} V_{j}$ であるような族 $(E_{e}^{'})_{e \in E}$ が存在して

$\begin{array}{r} H ((V_{j})_{j \in J}; (E_{e}^{'})_{e \in E}) = \emptyset \end{array}$
かつ任意の $e \in E$ に対して
$\begin{array}{r} ♯ (E_{e} ∖ E_{e}^{'}) \leq ε Π_{j \in J} ♯ V_{j} \end{array}$
が成り立つ.

仮定の記述の対応

まず

強化版

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

E_{e}

について

強化版に出てくる $E_{e}$ は $r$ 個の各頂点小集合に頂点をもち, $k - r$ 個の残りの頂点小集合については頂点の選び方が自由であるようなグラフたちの頂点集合( $V_{J}$ の部分集合)です.

$k$ 部版に出てくる $E_{e}$ は $V_{e}$ の部分集合です. $k - r$ 個の残りの頂点小集合について考えているか否かの違いがあります.

$k$ 部版の $E_{e}$ は強化版の $E_{e}$ を用いて $π_{e} (E_{e})$ と表されます.

強化版

各 $e \in E$ ごとに $E_{e} \in A_{e}$ を考える.
$\begin{array}{r} E (\prod_{e \in E} 1_{E_{e}} | V_{J}) \leq δ \end{array}$
が満たされるならば

これは $k$ 部版では

$k$ 部版

もし
$\begin{array}{r} ♯ H ((V_{j})_{j \in J}; (E_{e})_{e \in E}) \leq δ Π_{j \in J} ♯ V_{j} \end{array}$
が満たされるならば

に対応します.

$H = (J, E), D_{H} = ((V_{j})_{j \in J}; (E_{e})_{e \in E})$ として
$\begin{aligned} H (D_{H}) & = {(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}} \end{aligned}$
でした. $♯ H (D_{H})$ は
「グラフ $D_{H}$ 中に含まれる,各頂点小集合に頂点を1つずつもつような $H$ と同型な部分グラフの個数」
を表していました.

定義より,
$\begin{aligned} E (\prod_{e \in E} 1_{E_{e}} | V_{J}) & = \frac{1}{♯ V_{J}} \sum_{v \in V_{J}} \prod_{e \in E} 1_{E_{e}} (v) \end{aligned}$
$♯ V_{J} = Π_{j \in J} ♯ V_{j}$ です.
$\sum_{v \in V_{J}} \prod_{e \in E} 1_{E_{e}} (v) = ♯ H (D_{H})$ であることを確認します.

$\prod_{e \in E} 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} 1_{E_{e}} (v)$ は

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

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

強化版

ある $(E_{e}^{'})_{e \in E} \in \prod_{e \in E} A_{e}$ が存在して
$\begin{array}{r} ⋂_{e \in E} E_{e}^{'} = \emptyset \end{array}$
かつ任意の $ε \in E$ に対して
$\begin{array}{r} E (1_{E_{e} ∖ E_{e}^{'}} | V_{J}) \leq ε \end{array}$
が成立.

$k$ 部版

各 $e \in E$ に対して $E_{e}^{'} \subset \prod_{j \in J} V_{j}$ であるような族 $(E_{e}^{'})_{e \in E}$ が存在して

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

$\begin{array}{r} ⋂_{e \in E} E_{e}^{'} = \emptyset \end{array}$

と

$\begin{array}{r} H ((V_{j})_{j \in J}; (E_{e}^{'})_{e \in E}) = \emptyset \end{array}$

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

強化版

かつ任意の $ε \in E$ に対して
$\begin{array}{r} E (1_{E_{e} ∖ E_{e}^{'}} | V_{J}) \leq ε \end{array}$
が成立.

$k$ 部版

かつ任意の $e \in E$ に対して
$\begin{array}{r} ♯ (E_{e} ∖ E_{e}^{'}) \leq ε Π_{j \in J} ♯ V_{j} \end{array}$
が成り立つ.

これも大丈夫でしょう.
$E (1_{E_{e} ∖ E_{e}^{'}} | V_{J}) = E (1_{π_{e} (E_{e}) ∖ π_{e} (E_{e}^{'})} | V_{e})$ より分かります.

複雑度条件

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

複雑度条件

各 $f \in R = {f \in B (J) : ♯ f \in [0, r - 1]}$ に対して $B_{f}$ が $A_{f}$ の部分加法族であるような族 $(B_{f})_{f \in R}$ が存在して,任意の $f \in R$ に対して
$\begin{array}{r} c p x (B_{f}) \leq C \end{array}$
が成り立ち,任意の $e \in E$ に対して
$\begin{array}{r} E_{e}^{'} \in \underset{f ⊊ e}{⋁} B_{f} \end{array}$
が成り立つ.

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

証明の流れ

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

正則化補題+数え上げ補題
$⟹$ ハイパーグラフ除去補題

次回

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

感想

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

謝辞

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

投稿日：2024年4月25日

更新日：2024年4月26日

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

itou

147

13478

数学勉強中. https://twitter.com/G7UOMb0Zd8V7LdP

他の人のコメント

コメントはありません。

読み込み中

itou

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

$\cdots$????
記号
定理の主張
仮定の記述の対応
$H$の除去の記述の対応
複雑度条件
証明の流れ

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

記法

⋯????

記号

集合族(Vj)j∈[k]

直積Ve=∏j∈eVj

加法族Ae

定理の主張

仮定の記述の対応

強化版

強化版

k部版

Hの除去の記述の対応

強化版

k部版

強化版

k部版

複雑度条件

複雑度条件

証明の流れ

次回

感想

謝辞

この記事を高評価した人

この記事に送られたバッジ

投稿者

コメント

他の人のコメント

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

$\dots$ ????

集合族 $(V_{j})_{j \in [k]}$

直積 $V_{e} = \prod_{j \in e} V_{j}$

加法族 $A_{e}$

$k$ 部版

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

$k$ 部版

$k$ 部版