EC01_yyoshida

𠮷田悠一

Extremal Combinatorics:
◦ Combinatorics: 多分離散的なので安心してください。
◦ Extremal: ある対象(数,グラフ,ベクトル,集合 etc.)がある性
質を満たす時、その対象はどれだけ大きくor小さくなり得るか。


これらを解くための道具を身につけるのが目標。
特に
◦
◦
◦
◦
極値集合論
線形代数
確率的手法
ラムゼー理論(Additive Combinatoricsの匂いもする)

初回なのでささっと駆け抜けて早めに終わる。

１章 Counting
◦ Double Counting

２章 Advanced Counting
◦ Double Countingの他の例

３章 The Principle of Inclusion and Exclusion
◦ 包除原理の変化形

今回現れる手法は特に目新しくないはず。

1.1～1.3

1.5: The Averaging Principle


任意の数の集合は、平均以上の数と平均以下の数を
含む。
ちゃんとした応用は後々出てくるかと。





パーティーで奇数回握手をした人の数は偶数。
Turan数 T(n,k,l): smallest number of l-element
subsets of an n-element set X such that every
k-element subset of X contains at least one of
these sets.
例: l=2の時、n頂点のグラフのどのk頂点を取ってきて
も少なくとも一本その間に枝があるような枝の最小数。
[命題1.8] 任意のlknに対してT(n,k,l)nCk/kCl
証明は次のページ。

F: 条件を満たす大きさlの集合の族で最小のもの。
◦ |F|=T(n,k,l)

|F|行nCk列の行列M=(mA,B)を考える
◦ 行: AF 全体
◦ 列 : 大きさkの集合全体
◦ mA,B : ABなら1、そうでないなら0
B1
B2
B3
B4
B5
A1
0
1
1
1
1
A2
0
0
1
0
1
A3
1
1
0
1
0
A4
0
1
1
0
0

方針: M中の1の個数をDouble Count
rA: 行A中の1の数: rA=n-lCk-l
cB: 列B中の1の数: cB1

最後の等式も簡単なDouble Countingから。 


◦ 練習1.10

[補題2.1] A1,…,Anを大きさrの集合とし、X=Aiとする。
任意のijに対して|AiAj|kならば

直感: kが小さければ|X|は大きく無いといけない。
こんな行列を思い描くとDouble Countしやすい。

x1
x2
x3
x4
x5
A1
0
1
1
1
1
A2
0
0
1
0
1
A3
1
1
0
1
0
A4
0
1
1
0
0


(証明) ひたすら数える。
各iに対して
◦ d(x)  #{Ai|xAi}

全てのiで和をとると

二つを比較して
(Nr)2N|X|(r+(N-1)k) 


[補題2.2] Xをn要素からなる集合とする。A1,…,ANX
の平均の大きさは少なくともn/wであるとする。N2w2
なら、あるijが存在して|AiAj|n/2w2
直感: 集合の平均の大きさが大きければ、そのうち或
る二つの集合は多くの要素を共有する。
(証明) d(x)2=i,j|AiAj|をDouble Counting

d(x)2はx, d(x)=N/wの時、最小化される。


もし任意のijに対して|AiAj|<n/2w2とすると、
(1)に矛盾。

ka(n): 部の大きさnで枝数k以上の任意の二部グラフ
が二部クリークKa,aを持つような最小のk
n
a

定理2.4 ka(n)(a-1)1/an2-1/a+(a-1)
◦ 下限: ka(n)cn2-2/a (確率的手法より)




G=(V1,V2,E): 部の大きさがnで枝数kでa*a二部のク
リークを持たない。
xV1, BV2, |B|=aがK1,aをなす時スターと呼び、S(x,B)
と書く。
x1
y1
x1
y2
x3
y3
D: G中のスターの総数
Dを二通りの方法で数える。
a=2
S(x2,{y2,y3}),
S(x3,{y1,y2}),
S(x3,{y1,y3}),
S(x3,{y2,y3})

Bを固定すると、高々a-1通りのS(x,B)しか作れない。
◦ そうでなければ二部クリークKa,aが出来る。

xを固定すると、少なくともd(x)Ca通りのS(x,B)を作れる。
◦ 不等式はJensenの不等式から(nCaは上に凸な関数)

|E|(a-1)1/an2-1/a+(a-1)が得られる。 





H: m*nの0-1行列
Hがa-dense: Hの要素の少なくともaが1
Hの行がa-dense, 列がa-dense: 同様
Hがa-denseならば、どれぐらいの行と列が密か。
[系2.9] 2a-denseな行列Hの列のうちa1/2か行のa1/2
は(a/2)-denseである。







空間W=A1A2…Ak
HWの密度: m(H)=|H|/|W|
Hibを(a1,…,ai-1,b,ai+1,…,ak)Hであるような
(a1,…,ai-1,ai+1,…,ak)全体。
m(Hib)=|Ai|m{aH|ai=b}
[補題2.8] Bi={bAi|m(Hib)m(H)/2k}と置き、
B=B1B2…Bkとする。この時m(B)m(H)/2
(証明) m(B)m(HB)=m(H)-m(H＼B)




(系2.9の証明)
補題2.8でk=2の時を考える。あるi{1,2}に対して、
m(Bi)(m(H)/2)1/2





包除原理
A1,…,Anを集合Xの部分集合とする。
I[n]に対してAI = iI Aiとする。A=Xとする。
[命題3.1] A1,…,Anを集合Xの部分集合とする。以下が
成り立つ。

[命題3.3] A1,…,Anを集合Xの部分集合、I[n]とする。
以下が成り立つ。

証明: S=iI Ai, Bk=SAk(k[n]＼I)と置く。
Sに属し、どのBkにも属さない要素の数を数える。
命題3.1から





[命題3.4] fとgを有限集合の部分集合に対して定義さ
れた関数とする。f(A)=BAg(B)とすると、
g(A)=BA(-1)|A＼B|f(B)

証明:

最後のはC=Aの時1、それ以外の時0になる。



5/18(月): 高井、照山
◦ ５章 System of Distinct Representatives
◦ ６章 Colorings

5/25(月): 脊戸
◦ ４章 The Pigeonhole Principle

6/1(月)～未定

Download Report