８．Intersecting Families B4　鈴木洋介

Intersectingな集合族 集合の集合（集合族）がある どの２つの集合をとっても共通要素がある

Intersectingな集合族 集合の集合（集合族）がある どの２つの集合をとっても共通要素がある

８．１ Erdos－Ko－Radoの定理 １ ２ ３ ・・・ ｎ 図のような族において、Fは最大でいくつの集合を持つ か？ n≧2k とする １　２　３　・・・　ｎ

共通要素を１つだけ固定してみる 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 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( )/n=( ) n k n-1 k-1

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

Preposition 8.3. 全ての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 D E F G O 1 2 3 4 5 6

Maximal intersecting k-uniformな例（ｋ＝３、ｎ＝k -k+1=7） どの２つの集合も１要素のみ共有 どの集合も要素数ｋ どの要素もｋ個の集合に属する これ以上要素を追加すると 　Intersectingにならない 2 A B C D E F G O 1 2 3 4 5 6

Theorem 8.4. １ ２ ３ ・・・ ｎ Fを「ｎ個の要素からｋ個とった集合」の集合族とする。 ｎ≦k/2logkのときFのサブセット数はｋ以上。 F k要素の集合 k要素の集合 ・・・ １　２　３　・・・　ｎ

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

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

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

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’に対してresponsibleという Fは（　　） 個以上の集合族を持つ n-1 k-1

Proposition 8.7. Fがintersectingな系なら|F|≦k( ) F∈F 最小の族 とする |∪F|≦|F|k(　　) |F|≦|F|k(　　)/|F| n-1 k-1 n-1 k-1

Fのカーネル：Fの集合全ての共通部分

Proposition 8.8. Fはn≧k の要素を持つ集合上にあるintersectingな系 少なくとも１つの集合F1でKer(F1)= Φ ⇒|F|＜（　　） n-1 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なので |F|＜（　　） n-1 k-1

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

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

Proposition 8.10. k:1以上の整数 F：intersectingな系 F1：Fの族 Ker（F1)={x} ⇒|F|<(1+ε)(　　) 　n→∞のときあるε→0に対して n-1 k-1

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