ハイパーグラフ除去補題ー３

前正則化補題 , とし、関数は任意のに対してを満たすとする(に依存してもよい)。各に対して加法族はを満たすとする。このとき、および各 毎に加法族の組であってを満たすものが存在して、次が成り立つ:

−①
−②
−③
−④

前正則化補題 Szemerédiの正則化補題 弱正則化補題

という流れについては別途記事を書く予定。

証明. 次のアルゴリズムを考える:
0. 初期化 . (.)
1. 代入 このとき、データに対して記事２の補題２を適用。その結果、ダイコトミーのどちらであっても任意の に対してが定まる。
2. If Randomness then 停止
3. If Structure then 代入 1.へ

3. から1. へ移行する度に補題２の③より

は少なくともだけ増加する。一方、この量はで押さえられるため、回の移行の後アルゴリズムは必ず停止する。すると、の初期値がであることに注意して、補題２の④より①の成立が従う。②は構成から従い、③、④は補題２の①、②から従う。 Q.E.D.

正則化補題 に対して一様ハイパーグラフをおよびによって定義する。および任意のに対してが成り立つような加法族をとる。を前正則化補題と同じ条件の関数とする。このとき、

が成り立つようなおよび任意のに対してなる加法族の組が存在して、次が成り立つ:

証明. を固定してに関する帰納法で証明する*1。帰納法が進行する上での定数部分は変わるが、高々回なので問題ない。のときは自明に成立している(と主張を読む)。とし、では主張が成立していると仮定する。と同じ条件を満たす関数を後で選択する(少なくとも各点では成り立つようなもの)。として前正則化補題を適用すると、および任意の に対してなる加法族の組が存在して、

が成り立つ。これらを用いて帰納法の仮定(の場合)を適用すると、

が成り立つようなおよび任意のに対してなる加法族の組が存在して、

が成り立つ。であることから、

が成り立つようにをとのみに依存して選ぶことができる。これで証明が完了する。 Q.E.D.

*1:すなわち、ハイパーグラフ系を部分的に動かす。