AC02_yyoshida

吉田悠一


Szemerediの定理のk=3の場合の証明の概要を述
べる。iが成り立つと仮定してi+1を証明する。1の証
明は5章で行う。
1. Regularity Lemma
◦ 任意のグラフは定数サイズの近似表現を持つ

2. Triangle Removal Lemma
◦ グラフがo(n3)個の三角形しか含まなければ、o(n2)個の枝を
取り除くことで、全ての三角形を取り除ける。


3. 有限群に対するSzemerediの定理(k=3)
4. 整数に対するSzemerediの定理

定理2.1.1: 有限群に対するSzemerediの定理(k=3)
任意のdに対して、あるnが存在して、任意のN>nに
対して、任意のA{1,…,N}, |A|dNは長さ3の等差
列を持つ(あるa,b,cAが存在してb-a=c-b(mod N))。

定理2.1.2: 整数に対するSzemerediの定理(k=3)
任意のdに対して、あるnが存在して、任意のN>nに
対して、任意のAZN, |A|dNは長さ3の等差数列を
つ(あるa,b,cAが存在してb-a=c-b)。
上を仮定して、下を示す。






dを固定し、適当なA{1,…,N}, |A|dNを選ぶ。
AをZ2Nの部分集合と思うと|A|d/2(2N)である。
定理2.1.1より、Nが十分大きければ、a,b,cAが存在
してb-a=c-b(mod 2N)が成り立つ。
しかしa,b,cは1からNの中から選ばれているので、b-a
とc-bの取りうる範囲は1-NからN-1までである。
なので、b-a=c-b(mod 2N)は、b-a=c-bを意味する。よっ
て定理2.1.2が成り立つ。
定理2.2.1(Triangle Removal Lemma)
任意のdに対して、あるe(d)が存在し、任意のn
頂点のグラフGは次のいずれかを満たす。
1. Gからdn2本未満の枝を削除することでtrianglefreeに出来る。
2. Gはen3個以上の三角形を含む。


定理2.2.1から定理2.1.1を証明する。





Hを群、 A H |A| d|H|とする。
V=X Y Z, |X|=|Y|=|Z|=|H|を頂点集合とするグラフGを
作る。X,Y,Zの各頂点はHの各要素と対応する。
もし a A s.t. y=x+aならば、x Xとy Yを結ぶ。
もし c A s.t. z=y+cならば、y Yとz Zを結ぶ。
もし b A s.t. z=x+b+bならば、x Xとz Zを結ぶ。
X
y=x+a
x
z=y+b+b
Z
Y
y
z=y+c
z
任意のx Xとa Aに対して(x,x+a,x+a+a)は三角形に
なっており、しかもそれらはすべて互いに素。
なのでGをtriangle-freeにするのには、少なくとも
|H||A| d|H|2 dn2本の枝の削除が必要。
e=e(d)とすると、定理2.2.1からGは少なくとも
en3=9e|H|3の三角形を含む。

グラフGの三角形とAの長さ3の等差数列は|H|対1の
関係にある。
◦ 三角形x,y,zがあったとすると、y=x+a,z=y+c,z=x+2bなので、ab=b-c。
◦ 逆に等差数列a,b,cから、任意のx Xに対して、三角形
x,x+a,x+2bが作られる。



よってAは少なくとも9e|H|2個の等差数列を含む。
自明なもの(a=b=c)を除くと
y=x+a
X
x
y
9e|H|2-d|H|個。
z=y+b+b
z=y+c
|H|が十分大きければ正。
Z
z
Y


互いに素な頂点集合AとBの密度を
d(A,B)=(AB間の枝数)/|A||B|と定義する。
互いに素な頂点集合AとBは任意のS A,|S| e|A|と
T B,|T| e|B|に対して|d(S,T)-d(A,B)| eを満たす時、
A
B
S
T

定理2.3.3(Semeredi’s Regularity Lemma)
任意のe,tに対して、あるk(e,t)tが存在し、任意のグラ
フG=(V,E)は分割(V1,…,Vk), |V1|=|V2|=…=|Vk-1||Vk|を持ち、
少なくとも(1-e)kC2個の組(Vi,Vj)はe正則である。
定理2.3.3からTriangle Removal Lemmaを示す。
任意のdに対して、あるe(d)が存在し、任意のn頂点
のグラフGは次のいずれかを満たす。
1.
Gからdn2本未満の枝を削除することでtriangle-free
に出来る。
2.
Gはen3個以上の三角形を含む。



e=d/10, t=10/dとしてグラフGにRegularity
Lemmaを適用して得られた分割を考える。
Gから不要な枝を取り除く。
V1
正則でない V2
V6
V3
密度がd/2以下
V5
V4
Viの内部の枝

Gに以下の操作を施してG’を作る。
◦ 正則でないペア(Vi,Vj)の間の枝を取り除く:
正則でないペアは多くともdkC2/10個であり、それぞれ高々
(n/k)2本の枝を持つので、全体で高々dn2/10本。
◦ 各Vi内の枝を取り除く:
一つのVi内で高々n/kC2本。全体で高々kn/kC2=n2/k
dn2/10本。
◦ 密度がd/2以下のペア(Vi,Vj)の間の枝を取り除く:
各ペアにつき高々d n/kC2/2本。全体でkC2ペアあるので、全
体で高々dn2/2本。
合計でdn2/10 + dn2/10 + dn2/2  dn2本




もしG’が三角形を含まなければTriangle Removal
Lemmaの一つ目の条件が成立している。
以下では一つ目の条件が成立しなかったと仮定して、
G’がen3個の三角形を持つことを示す。
G’中のある三角形が所属する部をA,B,Cとする。
AとBに枝が有るということは、G’の作り方からAとBに
は沢山枝があるということである。





m=n/k(Viの大きさ)と置く。
Bのdm/4頂点以下にしか隣接していないAの頂点は
高々m/4個である。
もしそうでなければ、A’A, |A’||A|/4が存在して、
d(A’,B)d/4となる。d(A,B)d/2であったから、
|d(A,B)-d(A’,B)|d/4d/10となり、AとBの正
盾。
同様にCのdm/4頂点以下にしか隣接していないAの
頂点は高々m/4個である。
Aの少なくともm/2頂点はBにもCにもdm/4点以上隣接
している。



そのような性質を満たすAの頂点vを考え、vに隣接し
ているBの頂点集合をS, Cの頂点集合をTと置く。
|S|,|T| dm/4である。
d(B,C) d/2であり、B,Cはd/10正則なので、SとTの間
の枝の数は少なくとも(d/2-d/10)|S||T| d3m2/64である。
B
A
v
S
T
C

Aの１頂点からd3m2/64個の三角形が得られた。
A全体ではm/2*d3m2/64=d3m3/128=d3n3/128k3個の
三角形が存在する。 

Regularity Lemmaの証明は5章で行う。


Download Report