EC07_ysuzuki

８．Intersecting Families
B4 鈴木洋介
Intersectingな集合族


集合の集合（集合族）がある
どの２つの集合をとっても共通要素がある
Intersectingな集合族


集合の集合（集合族）がある
どの２つの集合をとっても共通要素がある
８．１ Erdos－Ko－Radoの定理


図のような族において、Fは最大でいくつの集合を持つ
か？
n≧2k とする
F
k要素の集合
k要素の集合
１２３・・・ｎ
・・・
共通要素を１つだけ固定してみる

（
n-1
k-1
）個の集合を持つ
Erdos－Ko－Radoの定理

Tｈ８．１上記の条件ではFの持てる最大集合数は
（ n-1
）
k-1
Erdos－Ko－Radoの定理
X:={0,1,…n-1}
Bs:={s,s+1,…s+k-1} s∈X B0∈F
Claim ８．２．
Bsは最大でもｋ個しかFに含まれない。
-1
0
1
2
-2
-(k-2)
K-2
-(k-1)
K-1
Erdos－Ko－Radoの定理
ｆ：ｎ個の置換関数
L:ｆ（Bs）={f(s),f(s+1),…,f(s+k-1)}∈Fとなるような（ｆ,ｓ）の組の
数
１．あるｆに対してFは最大でｋ個のｆ（Bs)を含むのでL≦kn!
２．あるｓとF∈Fに対してｆはk!(n-k)!個とれるので
L=|F|nk!(n-k)!
１．と２．より|F|≦kn!/nk!(n-k)!=k( nk )/n=( n-1
)
k-1
8.2.
ウルトラフィルター
X={1,2,3,4}のウルトラフィルターの例：
 F={{2},{1,2},{2,3},{2,4},{1,2,3},{1,2,4},{2,3,4},{1,2,3,4}}
 どの集合のスーパーセットもFに含まれている
 Xの集合Aに対してA∈F or A∈F
Φ
X
{1}
{2,3,4}
1
{2}
{1, 3,4}
4
{3}
{1,2, 4}
2
{4}
{1,2,3}
{1,2}
{3,4}
{1,3}
{2,4}
3
{1,4}
{2,3}

Preposition 8.3.

全てのintersectingな集合族は集合を追加することでウ
ルトラフィルターに拡張することができる。

Intersecting状態を崩さないような集合を追加してから、
それらの集合全てのスーパーセットを追加する。

任意のサブセットA、A∈Fと仮定すると、最初からある、
あるサブセットBに対してA∩B＝Φ
A∈B∈Fとなり矛盾する

8.3 Maximal Intersecting



集合族FがMaximal Intersectingとは
FがIntersecting
これ以上サブセットを追加できない
Maximal intersecting

k-uniformな例（ｋ＝３、ｎ＝７）
A B C
0
O O O
1
O
2
O
3
O
4
O
D
E
O
O
O
F
G
O
O
O
O
5
O
6
O
O
O
O
O
O
Maximal intersecting
k-uniformな例（ｋ＝３、ｎ＝k 2-k+1=7）
 どの２つの集合も１要素のみ共有
 どの集合も要素数ｋ
 どの要素もｋ個の集合に属する 0
1
 これ以上要素を追加すると
2
Intersectingにならない
3

4
A B C
D
E
O
O
F
G
O
O
O O O
O
O
O
O
O
O
O
5
O
6
O
O
O
O
O
O
Theorem 8.4.


Fを「ｎ個の要素からｋ個とった集合」の集合族とする。
ｎ≦k/2logkのときFのサブセット数はｋ以上。
F
k要素の集合
k要素の集合
１２３・・・ｎ
・・・
Theorem 8.4.





E:F∈F,E∩F=Φとなるk要素の集合
(F,E)の組の数Nを数える
n
Eには少なくともFの集合は入らないのでN≧（ k）-|F|
n-k
Fは最大で（ n-k
）個のEが入らないのでN≦|F|(
)
k
k
(1.12)より|F|≧ｋ 2
Theorem 8.5.
n
n-m

ｍ個のintresectingな集合族の和集合は最大でも2 -2
個の集合を含む。

数学的帰納法で証明する。
ｍ＝１は明らか。
A∈A、B⊇（⊆）A ⇒ B∈A のときAを単調増加（単調
減少）という
Aが単調減少、Bが単調増加のとき
-n
|A∩B|≦2 |A||B|が成立（Kleitmanの定理）




Theorem 8.5.









F:=F1～Fｍの和集合
Fiはmaximal intersecting
n-1
|Fm|=2
n-1
A:=Fm⇒|A|=2 単調減少
B:=F1～Fm-1の和集合⇒単調増加
n n-m+1
帰納法の仮定より|B|≦2 -2
n n-1 n
n-m+1
n-1 n-m
|A∩B|≦2 2 (2 -2
)=2 -2
n-1 n-m
|B∩Fm|=|B|-|A∩B|≧|B|-2 +2
n
n-m
|F|=|B|+|Fm|-|B∩Fm|≦2 -2
8.4 Helly型定理 Theorem 8.6.




F：集合族
ｋ：Fの集合の中で大きさが最小のものの大きさ
Fからどのk+1個の集合をとってもintersectする（共通点
を持つ）
⇒全ての集合が共通点を持つ
8.4 Helly型定理 Theorem 8.6.




Fの全ての集合が全体で共通部分を持たないとする
A={x1,x2,…xk}∈Fを１つとる
任意のi=1,2,…kに対してxi∈BiなるBi∈Fを１つとれる
⇒A∩B1∩・・・∩Bk＝Φとなり矛盾
8.5 Intersectingな系





Fがintersectingな系であるとは：
任意のF、F’∈Fに対してあるF∈Fが存在し、
全てのF’∈F’に対してF ∩F’=Φ
FはF’に対してresponsibleという
Fは（
n-1
k-1 ）
個以上の集合族を持つ
Proposition 8.7.
n-1
k-1)

Fがintersectingな系なら|F|≦k(

F∈F 最小の族とする
他の全ての族は Fの集合と共有部分を持つ
n-1
|∪F|≦|F|k( k-1)
n-1
|F|≦|F|k( k-1)/|F|




Fのカーネル：Fの集合全ての共通部分
Proposition 8.8.



Fはn≧k の要素を持つ集合上にあるintersectingな系
少なくとも１つの集合F1でKer(F1)= Φ
n-1
⇒|F|＜（ k-1 ）
Proposition 8.8.





Theorem 8.6よりF1～Fｒ∈F1 （r≦k+1）は全体で共通集
合を持たない。
H：＝F1～Frの和集合
あらゆるF2≠F1に対してF1にresponsibleなF∈F2があり、
Hと少なくとも２点で交わる
F-{F1}の全ての族はF1にresponsibleなので
n-1
|F|＜（k-1 ）
Proposition 8.9.








Minimal interestingな系：
過剰な集合がない
任意のF ∈F ∈Fに対してF ‘∈F が存在して
FのみがF の中でF ‘に対してresponsible
F：minimal intersectingな系
全てのF∈FでKer(F)≠Φ
4
3
Fが1＜|F|≦n/k、n≧2kなるFを含む
n-1
⇒|F|＜( k-1 )
Proposition 8.9.






すべてのF∈Fに対してF∩F’=ΦとなるF’∈F-{F}とF’∈Fが
存在
F(F): Fがresponsibleな族を全て含むサブ系
F(F)のどの族もF’にresponsibleな集合を含み、その集
合はF’と同じだけFと共通部分を持つ
FとF’と共通部分を持つXのｋ要素サブセットの数はF(F)
によって上限が決まる
n-2
|F(F) |≦k2 ( k-2 )
|F|＜( n-1
)
k-1
Proposition 8.10.




k:1以上の整数
F：intersectingな系
F1：Fの族 Ker（F1)={x}
n-1
⇒|F|<(1+ε)( k-1 ) n→∞のときあるε→0に対して
Proposition 8.10.

F1（の全ての集合）からｘを取り除く

Theorem 8.6.より、その族のl≦k個の集合の共通部分は
Φ
よってF１の集合F1～Flは共通部分{x}を持つ




H:=F1～Flの和集合 |H|≦k2
Fのどの族Fもｘを含まないので、必ずHの少なくとも２要
素を共有する集合を持つ。
n-1
k2 n-2
n-1
|F|≦( k-1 )+( 2 )（ k-2 ）≦(1+ε)( k-1 ）

Download Report