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