以上の道具立てに基づくRothの定理(Szemerédiの定理のの場合)の証明を実行する。Szemerédiの定理の証明に論理的には必要のない部分であるが、プロトタイプとして一度練習できる*1。また、後のSzemerédiの定理の証明と比較して、特殊な議論によるショートカットが存在する。
(i) 任意の
(ii) 任意の
(iii)
証明. より、
を満たす十分大きい
と或る
が存在して
が成り立つ。よって、或るが存在して
が成り立つ(背理法で示せる)。
の色の類を
とする。
がgoodであるとは
であることと定義し、それ以外のときはbadであるとよぶことにする。
なので*2、
には高々
個しかbadな元が存在しない*3。よって、
は全ての元がgoodであるような区間
を含む。理由:
なので、もし
を長さ
ずつに区切ったときに全ての区間がbadな元を含めば
となって矛盾する。 任意のに対して
とする。すると、goodの定義によっては
に含まれ、
であり、
は-APをなしている*4。 Q.E.D.
次に定理1の有限版を示す。
証明. 背理法で証明する。すなわち、各に対して
となるような
,
を満たす集合
、
色塗り分け写像
が存在して、どの
に対しても
とした際に定理の主張が成り立たないようなものが存在したと仮定する。
を適切に
に平行移動する: どの二つの
もdisjointであるようにどんどん右の方に平行移動し、任意の
に対して「任意の
-APおよび
-APについて、それを構成する少なくとも二つの元が
に含まれている場合は
には含まれない」が満たされるようにする。このとき、
に含まれる
-APおよび
-AP (
)は必ず一つの
に含まれなければならない。
そうして、とする。このとき、
であり、
に含まれる
-APおよび
-AP (
)は必ず一つの
に含まれなければならないことがわかる。
の
色塗り分け写像
を
に対して
で定義する。すると、定理1より或る色の類
および
-AP
の族
が存在して
について(i)〜(iii)が成立する。
(i)との構成より或る
が存在して
は
に含まれ、(iii)より
は
に依存しないことがわかる。すると、
を
だけ平行移動することによって
が主張を満たすことになり、背理法の仮定に矛盾する。 Q.E.D.
(i) 任意の
(ii) 任意の
(iii)
証明. とする。仮定より
である。記事5の系より、パーフェクトカラーの類
および非有界で二重カウンティング性質を満たす
が存在して、
と
は
に沿った密度を持ち、
かつ
が成り立つ。
なる正整数
を
(
は記事4の命題もの)。
は記事4 の③の
に対する
以上。
は記事4 の③の
に対する
以上。
.
(
は記事6の定理のもの)。
は記事4 の③の
に対する
以上。
.
を満たすように選ぶ。
は非有界なので、或る
-AP
が存在する(一つとって固定。
)。そして、
を
と定義する。記事4の命題の(i)より
が成り立つ。色塗り写像を
と定義する。すると、定理2より或る色の類および
-AP
の族
が存在して、
(i) 任意のに対して
は
に含まれる。
(ii) 任意のに対して
.
(iii) は
-APをなす。
が成り立つ*5。の元の色を
とすると、(ii)より任意の
に対して
が成り立つ。(i)より-AP
−①であり
なので、記事4の③より
がわかる。①が成り立つので、記事4の命題の(i)より各について、高々
個の例外を除く
に対して
-AP
−③が成り立つ。よって、記事4の③より
が高々個の例外を除く
に対して成り立つ。このことから、
が従う。理由: ③が成り立つようなをgood、成り立たないような
をbadとよぶことにする。このとき、
なる被覆がある。ここで、はgoodで、
はbadな点から成る集合であり、
および
が成り立つ。このような被覆の存在性は、例えば
の最小元から考えて
がgoodなら
を選んで
に移り、badなら
を
の元として
に移るというアルゴリズムを考えればよい。このような被覆の存在により、④によって
がわかる。 よって、②より
である。鳩ノ巣原理により、或るパリティが存在して
が成り立つ(を取って固定する)。
を
と定義する。 −⑥である。⑤より各
に対して、
であるような
-AP
が少なくとも
個存在する。理由: ⑤の左辺の集合の元を任意にとったとき、その元と
の中点を考えれば
-APが得られる(パリティが揃っているので中点は整数)。
を動かしたときの
のなす集合を
とする。
である。ここで、とすると、(iii)より
は
-長方形である。(i)と
の定義より、任意の
に対して
. 記事6の混合補題の(iii)(高次多重混合)により、或る
が存在して(以下固定)、高々
個の例外を除く
に対して
が成り立ち、⑦より
を得る。⑥より例外個数は高々個である。また、(i)より
-AP
であり、
なので、記事4 の③より
が高々個の例外を除く
に対して成立する。
を最小元から
個ずつに分けると、少なくとも一つの部分集合は⑧と⑨をともに満たす元のみからなる。理由:
個ずつに分けた部分集合達は、⑥より少なくとも
個ある。一方、⑧、⑨のどちらかを満たさないような
の元は高々
個しかない。つまり、
は或る
-AP
であって、どの
も⑧、⑨を満たすようなものが存在する(
の元が同じパリティのもののみから構成されていることに注意)。このとき、⑧と各構成より、各
に対して、
に含まれる
-AP
であって、
,
,
であるようなものが存在する。そうして、
個の
-AP
を考える。は全てAPなので、これは確かに
-APの族である。直前の
の性質および⑨、
から主張の(i), (ii), (iii)を満たしていることがわかる。 Q.E.D.
証明. 定理3から導出する方法は定理2の証明と全く同様なので省略する。 Q.E.D.