EC07_okada

SUNFLOWER
B４岡田翔太
SUNFLOWERとは？
S1～Skの集合があったとき
すべてのi≠jにおいてSj∩Si=Yとなっているときk個の
petalをもったSunflowerという。
 S-Yをpetal、Yをcoreと呼ぶ。
 すべてのSjが独立で、Yが空でもSunflowerとする。

たとえば・・・
1
1
1
3
1
5
16
4
6
7
17
10
それぞれの集合は1を共有しているので、これはSunflowerである。
1
1
3
16
1
3
6
1
4
16
8
10
これはアウト
SUNFLOWER LEMMA
s個の要素をもった集合の族をFとする。
 |F|＞s!(k-1)s であるとき Fはkのpetalをもつ
Sunflowerを含んでいる。

証明（数学的帰納法より証明）
 S=1のときは明らか。
 S≥2のとき
Fに独立な集合がk個以上あるならば、Sunflower
Fの独立な集合がｋ-1個以下のとき→族をBとする
B
要素数はs(k-1)以下
Fに属するそれぞれの集合は
Bの要素を含んでいる。
少なくとも(s-1)!(k-1)s-1 個の集合に含まれる
この要素xを削除すると・・・
s-1個の要素を持つ集合が、少なくとも(s-1)!(k-1)s-1 個ある。
→k-petalなSunflowerをもつ。
そこに、xを加えてもSunflowerとなる。
条件を厳しくする。

すべてのi≠jにおいて|Sj∩Si|=λとなっているときweakΔ-systemであるという。
補題7.1
 Fがweak-Δ-systemであるとき、
|F|≥s2-s+2
であるならば、FはSunflowerである。

Sunflowerは２つの性質を持っている
Yはすべての集合Sに属している。
 S１-Y…Sk-Yは完全に独立である。


この性質を拡張していく
COREの拡張
Coreの条件の拡張を行う。
Si-Yは一部のみ独立とする。
 Common part Y(F)を以下のように定める。

このとき、Fがs-uniformであり、common part Yがs未
満の要素しか持たないのであれば、それぞれのS-Yは
独立である。
5
2
3
4
5
1
7
13
6
8
9
11 10
12
1
13
14
15
16
17
補題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
B0
B
Y
Sj
Si
花びらの条件を変える（FLOWER）
ある族Fのblocking setとは、その集合がFのすべての
集合にまたがっていることである。
 blocking numberとは、blocking setを最小とするとき
の要素数である。τ(F)とする。

3
1
2
3
4
5
9
6
7
8
10
11
Blocking setは
{3,6,9},{1,4,6,9}等
τ(F)=3
FLOWERを定義する。
FY=｛S-Y:S ∊F,S⊇Y｝とすると
k個のpetalとcoreをYをもつflowerとは τ(FY)≥kである
ような族Fのことである。
flowerであっても、sunflowerでないものも存在する。
補題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を含む。
その他への応用

リテラルに応用
ｎ変数リテラルによる関数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 …
補題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すべてにまたがる
→矛盾
x1
x3
x2
x1
x6
x5
x4
x7
x8
・・・
x9
F
Y
t+1枚の花弁をもち、
すべての花弁を選ぶには
t+1個の要素が必要
Yはmintermの部分集合
→Yに含まれないCが存在。
Cはすべての花弁にまたがっている。
x7
xn
補題7.5
F=F 1∨F2… ∨Ft を、bottom-fan-in=kであるOr-AndOr関数とする。
Fはs個未満の1しか持たないvectorを受理しないなら
ば、Fに受理されるｓ個の1を持つvectorはtks個以上存
在しない。
bottom fan in k・・・各Clauseが最大k個の正リテラル
しかもたない。
証明
tks個以上存在すると仮定
A:s個の1を含むvectorの集合 →u
B:最大s-1個の1を含むvectorの集合 →v
vの中にuと同じ結果を返すvectorが存在することをいう。
BはFjによって受理されないはずである。
F=C1∧C2…∧Cm
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である）

Download Report