SUNFLOWER B４　岡田翔太.

Presentation on theme: "SUNFLOWER B４　岡田翔太."— Presentation transcript:

1 SUNFLOWER B４　岡田翔太

2 Sunflowerとは？ S1～Skの集合があったとき
すべてのi≠jにおいてSj∩Si=Yとなっているときk個の petalをもったSunflowerという。 S-Yをpetal、Yをcoreと呼ぶ。 すべてのSjが独立で、Yが空でもSunflowerとする。

3 たとえば・・・ 1 1 1 1 3 5 4 7 16 6 17 10 それぞれの集合は1を共有しているので、これはSunflowerである。
これはアウト 4 8 16 6 16 10

4 Sunflower Lemma s個の要素をもった集合の族をFとする。
|F|＞s!(k-1)s であるとき　Fはkのpetalをもつ Sunflowerを含んでいる。

5 Fに独立な集合がk個以上あるならば、Sunflower Fの独立な集合がｋ-1個以下のとき→族をBとする
証明（数学的帰納法より証明） S=1のときは明らか。 S≥2のとき Fに独立な集合がk個以上あるならば、Sunflower Fの独立な集合がｋ-1個以下のとき→族をBとする 要素数はs(k-1)以下 Fに属するそれぞれの集合は Bの要素を含んでいる。 B 少なくとも(s-1)!(k-1)s-1 個の集合に含まれる この要素xを削除すると・・・ s-1個の要素を持つ集合が、少なくとも(s-1)!(k-1)s-1 個ある。 →k-petalなSunflowerをもつ。 そこに、xを加えてもSunflowerとなる。

6 条件を厳しくする。 すべてのi≠jにおいて|Sj∩Si|=λとなっているときweak- Δ-systemであるという。 補題7.1
Fがweak-Δ-systemであるとき、 |F|≥s2-s+2 であるならば、FはSunflowerである。

7 Sunflowerは２つの性質を持っている
Yはすべての集合Sに属している。 S１-Y…Sk-Yは完全に独立である。 この性質を拡張していく

8 Coreの拡張 Coreの条件の拡張を行う。 Si-Yは一部のみ独立とする。 Common part Y(F)を以下のように定める。
このとき、Fがs-uniformであり、common part Yがs未 満の要素しか持たないのであれば、それぞれのS-Yは 独立である。 5 5 13 1 13 1 6 15 2 10 3 7 11 14 9 17 4 12 8 16

9 補題7.2 要素数が最大sである集合の族集合をFとする。 |F|>ksであるとき、k+1個の集合はcommon part に 含まれる要素数がs未満である。 証明 要素数がsの集合をB0、B0∩S=B　F(B)=S-Bとすると |F(B)|>(k-1)s-|B|となる。 　　→そうでないと|F|>ks を満たさない。 帰納法より、S-Bのcommon part Yはs-|B|以下の要 素をもつ。 Bを加えて考えると、S1…Sk,B0のcommon part は |Y|+|B|< (s- |B|) + |B|=s

10 B0 B Y Si Sj

11 花びらの条件を変える（flower） ある族Fのblocking setとは、その集合がFのすべての 集合にまたがっていることである。
blocking numberとは、blocking setを最小とするとき の要素数である。τ(F)とする。 3 9 6 Blocking setは {3,6,9},{1,4,6,9}等 τ(F)=3 1 4 7 10 2 5 11 8 3

12 Flowerを定義する。 FY=｛S-Y:S ∊F,S⊇Y｝とすると
k個のpetalとcoreをYをもつflowerとは τ(FY)≥kである ような族Fのことである。 flowerであっても、sunflowerでないものも存在する。

13 補題7.3 Fをs個の要素をもった集合の族とすると、 |F|>(k-1)sである時、Fはk個のpetalをもったflowerで ある。
証明 s=1は明らか。 s>2のとき、τ(F)≥kならば、F自身がflower そうでないときは、Sunflowerと同様に証明。 少なくとも|F|/(k-1)個の集合に含まれる点xが存在。 → |Fx|>(k-1)s-1となる。（ Fx={S-{x}} ） →s-1個の要素をもった集合が(k-1)s-1個ある。 帰納法よりFはflowerを含む。 xを元に戻しても、ｘはcoreとなり、Fはflowerを含む。

14 その他への応用 リテラルに応用 ｎ変数リテラルによる関数fがあったとき mintermとはM≤Fとなるmonomial M
f:(x1∨ x2)∧ (x3∨x4) ∧ (x5∨x6) mintermは x1x3x5 , x1x4x5 … f:(x1∨ x2)∧ (x3∨x4) ∧ (x1∨x5) mintermはx1x4 …

15 補題7.4 ｆをn変数のｔ-And-Or関数とすると、すべてのs=1…nに ついて、fは大きさsのmintermを多くてもts個しかもたな い。
証明　 f=C1∧C2…∧Cm (|C|<t), mintermの集合をF C={C1,C2,Cm}はFの集合にまたがっている。 |F|> tsとすると、7.3よりFはt+1-petalなFlower Yはmintermの部分集合 　→Cのすべてにまたがることができない。 Yに含まれないCを選ぶとCは、M-Yすべてにまたがる →矛盾

16 x1 x3 x1 x4 x2 x6 x7 x7 ・・・ x5 x8 x9 xn F ・・・ t+1枚の花弁をもち、 すべての花弁を選ぶには t+1個の要素が必要 Y Yはmintermの部分集合 　→Yに含まれないCが存在。 　Cはすべての花弁にまたがっている。

17 補題7.5 F=F 1∨F2… ∨Ft を、bottom-fan-in=kであるOr-And- Or関数とする。 Fはs個未満の1しか持たないvectorを受理しないなら ば、Fに受理されるｓ個の1を持つvectorはtks個以上存 在しない。 bottom fan in k・・・各Clauseが最大k個の正リテラル しかもたない。

18 証明 tks個以上存在すると仮定 A:s個の1を含むvectorの集合 →u B:最大s-1個の1を含むvectorの集合 →v
vの中にuと同じ結果を返すvectorが存在することをい う。 BはFjによって受理されないはずである。 F=C1∧C2…∧Cm

19 vがAに対してk-limit であるということは ベクトルの成分のうちk箇所の値がvと一致し、v≤uとなる vector uがAに存在することである
補題7.6 Aに対してk-limitなv ∊Bが存在する。 C(v)=0となるとする。 Cは正リテラル（S）の和と、負リテラル（T）の和で表わせ られる。（|S|＜ｋ） uは受理されるので、Sの中に1を１つ以上もつか、Tに0 を１つ以上もつ。 前者はc(v)=1になる。（7.6より） 後者もc(v)=1　（v≤uより、uが０ならvも0である）