EC06_takai

6章 Colorings
修士課程2回
高井唯史
Coloring
F=｛A,B,C,・・・｝
A=｛x1,x2,x3｝
B={x2,x4}
C={x1,x3,x4}
・・・
問題
X={x1,x2,x3・・・}をそれぞれr色で塗り分けるとき、
∀α∈Fが単一色にならないように塗れるか？
例
F=｛A,B,C｝
X={x1,x2,x3}
r=2
A={x1,x2,x3}
B={x1,x3}
C={x2,x3}
Coloring
F=｛A,B,C,・・・｝
A=｛x1,x2,x3｝
B={x2,x4}
C={x1,x3,x4}
・・・
問題
X={x1,x2,x3・・・}をそれぞれr色で塗り分けるとき、
∀α∈Fが単一色にならないように塗れるか？
例
F=｛A,B,C｝
X={x1,x2,x3}
r=2
A={x1,x2,x3}
B={x1,x3}
C={x2,x3}
Coloring
F=｛A,B,C,・・・｝
A=｛x1,x2,x3｝
B={x2,x4}
C={x1,x3,x4}
・・・
問題
X={x1,x2,x3・・・}をそれぞれr色で塗り分けるとき、
∀α∈Fが単一色にならないように塗れるか？
例
F=｛A,B,C｝
X={x1,x2,x3}
r=2
A={x1,x2,x3}
B={x1,x3}
C={x2,x3}
Coloring
F=｛A,B,C,・・・｝
A=｛x1,x2,x3｝
B={x2,x4}
C={x1,x3,x4}
・・・
問題
X={x1,x2,x3・・・}をそれぞれr色で塗り分けるとき、
∀α∈Fが単一色にならないように塗れるか？
例
F=｛A,B,C｝
X={x1,x2,x3}
r=2
A={x1,x2,x3}
B={x1,x3}
C={x2,x3}
Coloring
F=｛A,B,C,・・・｝
A=｛x1,x2,x3｝
B={x2,x4}
C={x1,x3,x4}
・・・
問題
X={x1,x2,x3・・・}をそれぞれr色で塗り分けるとき、
∀α∈Fが単一色にならないように塗れるか？
例
F=｛A,B,C｝
X={x1,x2,x3}
r=2
A={x1,x2,x3}
B={x1,x3}
C={x2,x3}
Coloring
F=｛A,B,C,・・・｝
A=｛x1,x2,x3｝
B={x2,x4}
C={x1,x3,x4}
・・・
問題
X={x1,x2,x3・・・}をそれぞれr色で塗り分けるとき、
∀α∈Fが単一色にならないように塗れるか？
例
F=｛A,B,C｝
X={x1,x2,x3}
r=3
A={x1,x2,x3}
B={x1,x3}
C={x2,x3}
r-colorableという
Coloring
F={A,B,C}
A={x1,x2,x3}
B={x2,x3,x4}
C={x1,x3,x4}
集合の大きさが全てkで同じ時k-uniformという
この場合は3-uniform
2-uniformならばグラフで表すことができる
F={A,B,C,D}
A={x1,x2}
B={x2,x3}
C={x1,x4}
D={x3,x4}
1
2
3
4
Coloring
F={A,B,C}
A={x1,x2,x3}
B={x2,x3,x4}
C={x1,x3,x4}
集合の大きさが全てkで同じ時k-uniformという
この場合は3-uniform
2-uniformならばグラフで表すことができる
F={A,B,C,D}
A={x1,x2}
B={x2,x3}
C={x1,x4}
D={x3,x4}
1
A
C
B
2
D
4
3
定理6.1


A=Bでない∀A,∀B∈Fにおいて、|A∩B|≠1
ならば、Fは2-colorableである。
証明
X={x1,x2,x3,x4,x5}
A={x1,x3,x5}
B={x2,x4,x5}
C={x1,x3,x4}
定理6.1


A=Bでない∀A,∀B∈Fにおいて、|A∩B|≠1
ならば、Fは2-colorableである。
証明
X={x1,x2,x3,x4,x5}
A={x1,x3,x5}
B={x2,x4,x5}
C={x1,x3,x4}
D={x2,x3}
定理6.1


A=Bでない∀A,∀B∈Fにおいて、|A∩B|≠1
ならば、Fは2-colorableである。
証明
X={x1,x2,x3,x4,x5}
A={x1,x3,x5}
B={x2,x4,x5}
C={x1,x3,x4}
D={x2,x3}
定理6.1


A=Bでない∀A,∀B∈Fにおいて、|A∩B|≠1
ならば、Fは2-colorableである。
証明
X={x1,x2,x3,x4,x5}
A={x1,x3,x5}
B={x2,x4,x5}
C={x1,x3,x4}
D={x2,x3}
定理6.1


A=Bでない∀A,∀B∈Fにおいて、|A∩B|≠1
ならば、Fは2-colorableである。
証明
X={x1,x2,x3,x4,x5}
A={x1,x3,x5}
B={x2,x4,x5}
C={x1,x3,x4}
D={x2,x3}
定理6.1


A=Bでない∀A,∀B∈Fにおいて、|A∩B|≠1
ならば、Fは2-colorableである。
証明
X={x1,x2,x3,x4,x5}
A={x1,x3,x5}
B={x2,x4,x5}
C={x1,x3,x4}
D={x2,x3}
|A∩B|=1のため失敗
このような状況は|A∩B|=1の時にしか起こらない
定理6.2

∀A∈Fが大きさk以上で
は2-colorableである。
k=3の場合|F|<4
F={A,B,C}
A={x1,x2,x3}
B={x1,x3,x4}
C={x2,x3,x4}
1
F  2k ならば、F
A={x1,x2,x3}
B={x1,x3,x4}
C={x2,x3,x4}
2-colorable!!
A={x1,x2,x3}
B={x1,x3,x4}
C={x2,x3,x4}
A  k  F  2k 1  2  colorable
証明6.2

C(A):Aが単一色で塗られた時の塗り方の数
例
F={A,B,C}
A={x1,x2}
B={x1,x3}
C={x1,x2,x3}
C(A)=4
C ( A)  2  2
重複を許す
n A
A={x1,x2}
B={x1,x3}
C={x1,x2,x3}
A={x1,x2}
B={x1,x3}
C={x1,x2,x3}
A={x1,x2}
B={x1,x3}
C={x1,x2,x3}
A={x1,x2}
B={x1,x3}
C={x1,x2,x3}
 2n( k 1)
全塗り方の通り数
n ( k 1)
n ( k 1)
n
C
(
A
)

2

F

2

2


AF
AF
定理6.3
全ての集合が大きさk

∀A,∀B∈FにおいてA∩B≠0
Fがk-uniformであり、intersectingであり
F  k k のとき、2-colorabe
k=2のとき
F={A,B,C,D,E}
A={x1,x2}
B={x1,x3}
C={x1,x4}
D={x1,x5}
E={x1,x6}
としなければならない
A={x1,x2}
B={x2,x3}
C={x1,x3}
D={x1,x4}
E={x1,x5}
とするとC∩D=0
定理6.3
全ての集合が大きさk

∀A,∀B∈FにおいてA∩B≠0
Fがk-uniformであり、intersectingであり
F  k k のとき、2-colorabe
k=2のとき
F={A,B,C,D,E}
A={x1,x2}
B={x1,x3}
C={x1,x4}
D={x1,x5}
E={x1,x6}
としなければならない
A={x1,x2}
B={x2,x3}
C={x1,x3}
D={x1,x4}
E={x1,x5}
とするとC∩D=0
証明6.3
k  uniform, intersecti ng , F  k k  2  colorable

2-colorableでないなら F  k kを証明する
頂点集合Y={x1,x2,x3,…,xk}を考える。
ここでd(Y)={#A|Y⊆A,A∈F}である。
例
F={A,B,C,D}
A={x1,x2,x3}
B={x1,x3,x4}
C={x2,x3,x5}
D={x2,x4,x5}
Fの集合とは関係なし
に構成する
Y={x2,x3}のとき
Y⊆B、Y⊆Cよりd(Y)=2
d(Yi)≧|F|･k-iを満たすようにYを構成できればi=kより証明完
ただし、Yi={x1,x2,…,xi}
1≧d(Yk)≧|F|･k-kよりkk≧|F|
Fはk-uniformなため
証明6.3
k  uniform, intersecti ng , F  k k  2  colorable


2-colorableでないなら F  k kを証明する
d(Yi)≧|F|･k-iを満たすようにYを構成する
i=1において。
∃A∈Fを考える。Aは|F|個の集合とintersectingしている。
よって、d(x1)≧|F|/kとなるx1が存在する。
A={x1,x2,x3}
x2
B={x2,x4,x5}
x1
x1
C={x1,x4,x6}
d(x1)=2≧|F|/k
x2,x3
D={x1,x5,x6}
E={x2,x3,x4}
証明6.3
k  uniform, intersecti ng , F  k k  2  colorable


2-colorableでないなら F  k kを証明する
d(Yi)≧|F|･k-iを満たすようにYを構成する
i=iまで正しくYiが構成できたとする。(帰納法)
このときYi∩E=0であるE∈Fが存在する。(さもなくば2-colorable)
A={x1,x2,x4,x5}
B={x2,x3,x5,x6}
C={x1,x3,x5,x7}
Yi={x1,x2}
Bi ⊆Aである全てのAとEはintersectingしているため、
少なくともd(Bi)/|E|個の集合と交差しているxi+1が存在する。
するとd(Bi+1)≧ d(Bi)/|E|≧|F|･k-(i+1)が成り立つ。証明完
証明6.3
k  uniform, intersecti ng , F  k k  2  colorable


2-colorableでないなら F  k kを証明する
d(Yi)≧|F|･k-iを満たすようにYを構成する
i=iまで正しくYiが構成できたとする。(帰納法)
このときYi∩E=0であるE∈Fが存在する。(さもなくば2-colorable)
A={x1,x2,x4,x5}
B={x2,x3,x5,x6}
C={x1,x3,x5,x7}
Yi={x1,x2}
Yiを同一色、Yi以外を
もう一つの色でぬると
2-colorable
Bi ⊆Aである全てのAとEはintersectingしているため、
少なくともd(Bi)/|E|個の集合と交差しているxi+1が存在する。
するとd(Bi+1)≧ d(Bi)/|E|≧|F|･k-(i+1)が成り立つ。証明完
証明6.3
k  uniform, intersecti ng , F  k k  2  colorable


2-colorableでないなら F  k kを証明する
d(Yi)≧|F|･k-iを満たすようにYを構成する
i=iまで正しくYiが構成できたとする。(帰納法)
このときYi∩E=0であるE∈Fが存在する。(さもなくば2-colorable)
A={x1,x2,x4,x5}
B={x2,x3,x5,x6}
C={x1,x3,x5,x7}
E={x4,x5,x6,x7}
Yi={x1,x2}
このようなEが存在する
E={x4,x5,x6,x7}
x4,x5
A={x1,x2,x4,x5}
x6
B’={x1,x2,x3,x6}
x6,x7
C’={x1,x2,x6,x7}
d(Yi)個存在
証明6.3
k  uniform, intersecti ng , F  k k  2  colorable


2-colorableでないなら F  k kを証明する
d(Yi)≧|F|･k-iを満たすようにYを構成する
Yi ⊆Aである全てのAとEはintersectingしているため、
少なくともd(Yi)/|E|個の集合と交差しているxi+1が存在する。
するとd(Yi+1)≧ d(Yi)/|E|≧|F|･k-(i+1)が成り立つ。
d(x5)=d(Yi+1)=d(Yi∪x5)
d(x5)=3≧d(Yi)/|E|≧|F|･k-(i+1)
E={x4,x5,x6,x7}
x4,x5
A={x1,x2,x4,x5}
x6
B’={x1,x2,x3,x6}
x6,x7
C’={x1,x2,x6,x7}
d(Yi)個存在
定理6.4 2-colorableでない時のお話
k-uniformなどんなFにおいても、単一色な
集合の数が|F|･21-k以下となるような、
2-coloringが存在する
証明：ある頂点集合Sにおいて、M(S)をS全て
を同じ色で塗り、S以外をもう一つの色で
塗った時の単一色な集合の数とする。

例
F={A,B,C,D,E}
A={x1,x2,x3}
B={x1,x3,x4}
C={x2,x3,x5}
D={x3,x4,x5}
E={x4,x5,x6}
S={x1,x2,x3}
定理6.4 2-colorableでない時のお話
k-uniformなどんなFにおいても、単一色な
集合の数が|F|･21-k以下となるような、
2-coloringが存在する
証明：ある頂点集合Sにおいて、M(S)をS全て
を同じ色で塗り、S以外をもう一つの色で
塗った時の単一色な集合の数とする。

例
F={A,B,C,D,E}
A={x1,x2,x3}
B={x1,x3,x4}
C={x2,x3,x5}
D={x3,x4,x5}
E={x4,x5,x6}
S={x1,x2,x3}
M(S)=2となる
定理6.4 2-colorableでない時のお話

k-uniformなどんなFにおいても、単一色な
集合の数が|F|･21-k以下となるような、
2-coloringが存在する
全てのSの集合のM(S)合計 = A∈Fが単一色になるSの数において、全Aの合計
重複を許す
nk
n  k 1


M
(
S
)

2

S
:
S

A

F

2

2

F

2


SX
AF
2n個の集合
以上より M (S )  F  21k となるSが存在する
定理6.5 differently coloring
今までのcoloringはA∈Fが単一色にならなければよかった
例：
F={A,B,C,D}
A={x1,x2,x3}
B={x1,x2,x4}
C={x3,x5,x6}
D={x4,x5,x7}
E={x1,x4,x7}
Fは3-coloringである
定理6.5 differently coloring
differently coloringでは∀xi,∀xj∈Aの
xiとxjが違う色にならなければならない
例：
F={A,B,C,D}
A={x1,x2,x3}
B={x1,x2,x4}
C={x3,x5,x6}
D={x4,x5,x7}
E={x1,x4,x7}
differently coloring
differently coloringでない
定理6.5 differently coloring
定理6.5
任意のr-uniformなFにおいて、少なくとも(r!/rr)|F|個の集合
がdifferently coloringであるような塗り方が存在する
例：3-uniform 3-coloring
F={A,B,C,D,E,F,G,H,I}
A={x1,x2,x3}
B={x1,x2,x4}
C={x1,x2,x5}
D={x1,x3,x5} differently coloringは4つ＞3!/33*9=2
E={x1,x4,x5}
F={x2,x3,x4}
G={x2,x3,x5}
H={x2,x4,x5}
I={x3,x4,x5}
定理6.5 differently coloring
定理6.5
任意のr-uniformなFにおいて、少なくとも(r!/rr)|F|個の集合
がdifferently coloringであるような塗り方が存在する
D(C)：ある塗り方Cにおいてdifferently coloringであるA∈Fの個数
F={A,B,C,D}
A={x1,x2,x3}
B={x1,x2,x4}
C={x1,x3,x5}
D={x3,x4,x5}
塗り方C={x1,x2,x3,x4,x5}において
D(C)=2
定理6.5 differently coloring
定理6.5
任意のr-uniformなFにおいて、少なくとも(r!/rr)|F|個の集合
がdifferently coloringであるような塗り方が存在する
D(C)：ある塗り方Cにおいてdifferently coloringであるA∈Fの個数
全ての塗り方CのD(C)合計=A∈Fがdifferently coloringになるCの数において、全Aの合計
重複を許す
nr
nr


D
(
C
)

C
:
A
が
differentl
y
coloring

r
!

r

F

r
!

r



C
AF
rnの塗り方パターン
AF
以上より D(C )  F  r!/ r r となるCが存在する
混色の三角形



nクリーク完全グラフKnにおいて
赤と青二色で枝を塗ると、赤と青の色が混
在した三角形は少なくとも何個できるか？
ただし、赤い枝の本数=青い枝の本数±1
例：K5
(balanced coloring)
混色の三角形



nクリーク完全グラフKnにおいて
赤と青二色で枝を塗ると、赤と青の色が混
在した三角形は少なくとも何個できるか？
ただし、赤い枝の本数=青い枝の本数±1
例：K5
(balanced coloring)
この塗り方では6個のmixed三角形
問題を面白く(?)するために
ゲームを考える






Alice、Bob、Carole3人が存在する。
balanced coloringされたKnを作る
Caroleは三角形がない(triangle-free)、
Knの部分グラフGが与えられる。
AliceはGのうち赤い枝のグラフ、BobはG
のうち青い枝のグラフがわかっている。
CaroleはAlice、Bobに0,1の文字列の
certificateを送信し、実際にGがmixedfreeな事を二人に納得させたい
その通信量は少なくともどのくらい必要か？
communication complexity
balanced coloringなKnを作成する
communication complexity
Knのtriangle-freeな部分グラフG
communication complexity
Carole
Bob
Alice
１
１
２
１
５２
３
４
５２
３
４
５
３
４
communication complexity
枝2,3は存在しないですよ
3角形1,2,3はmixedかも？
3角形1,2,3はmixedかも？
Carole
Bob
Alice
１
１
２
１
５２
３
４
５２
３
４
５
３
４
communication complexity
3角形1,2,3はないんだな
3角形1,2,3はないんだな
Carole
Bob
Alice
１
１
２
１
５２
３
４
５２
３
４
５
３
４
communication complexity
これを繰り返してなるべく少ない通信量でmixed-freeな事を納得させる
自明に全ての枝情報を送るとできるので、その時の通信量はnC2
Carole
Bob
Alice
１
１
２
１
５２
３
４
５２
３
４
５
３
４
定理6.6
このゲームの通信量はΩ(n2)である

まず、どのようにKnを色分けしても
(balanced)、mixedであり、 collisionfreeな三角形が少なくともΩ(n2)個存在す
る事を証明したい。
collision-freeについては後述。
おおまかにはお互いに干渉しない三角形

定理：6.7 任意のbalanced-coloringな
Knはある定数ε>0 が存在し、collisionfreeな三角形を少なくともεn2個もつ
頂点へのルール

balanced-coloringなKnにおいて、ある頂
点から出る赤い(青い)枝が0.8n本より多い
時、その頂点は赤い(青い)頂点と呼ぶ。赤
でも青でもない頂点はmixdな頂点と呼ぶ
例：K6
頂点へのルール

balanced-coloringなKnにおいて、ある頂
点から出る赤い(青い)枝が0.8n本より多い
時、その頂点は赤い(青い)頂点と呼ぶ。赤
でも青でもない頂点はmixdな頂点と呼ぶ
例：K6
5>0.8×6本の青い枝
主張6.8
mixedな頂点が少なくとも0.1n個ある


赤い頂点が0.5n個以下な事を示す。
0.5n個以上として背理法で示す
･･･
主張6.8
mixedな頂点が少なくとも0.1n個ある


赤い頂点が0.5n個以下な事を示す。
0.5n個以上として背理法で示す
0.8n本の赤い枝を持つ
･･･
主張6.8
mixedな頂点が少なくとも0.1n個ある


赤い頂点が0.5n個以下な事を示す。
0.5n個以上として背理法で示す
0.8n - 1本の赤い枝を持つ(重複を削除)
･･･
赤い枝の合計数
≧0.8n ＋ 0.8n-1
主張6.8
mixedな頂点が少なくとも0.1n個ある


赤い頂点が0.5n個以下な事を示す。
0.5n個以上として背理法で示す
0.8n - 2本の赤い枝を持つ(重複を削除)
･･･
赤い枝の合計数
≧0.8n ＋ 0.8n-1 +
0.8n - 2
主張6.8
mixedな頂点が少なくとも0.1n個ある


赤い頂点が0.5n個以下な事を示す。
0.5n個以上として背理法で示す
0.8n – (0.5n-1)本の赤い枝を持つ(重複を削除)
･･･
赤い枝の合計数
 0.5n 
  0.275n 2  0.25n  0.25n 2
  0.8n  (i  1)  0.8n  0.5n  
i 1
2 
0.5 n
全枝数の半数を超えてしまう。
balanced-coloringである事に矛盾。青い頂点も同様に証明可能
主張6.8
mixedな頂点が少なくとも0.1n個ある



赤い、青い頂点はそれぞれ0.5n個以下(証明済)
mixedな頂点が少なくとも0.1n個あることを示す
mixedな頂点が0.1n個より少ないとする。
0.4n個以上(R個とする)
0.4n個以上(B個とする)
0.1n個より少ない
主張6.8
mixedな頂点が少なくとも0.1n個ある
赤い頂点からは最大0.2n本の青い枝が出ている。
それら全てが青い頂点に入ってるとして、
赤い頂点から青い頂点に伸びる赤い枝の本数は
≧B-0.2n≧(1/2)･B
赤い頂点から青い頂点に入っている枝について考える
0.4n個以上(R個とする)
0.4n個以上(B個とする)
0.1n個より少ない
主張6.8
mixedな頂点が少なくとも0.1n個ある
つまり、赤い頂点と青い頂点の間の枝の半数以上が赤い枝である。
同様に青い頂点を中心に考えると、半数以上が青い枝であり、矛盾となる。
mixedな頂点が0.1nより少ないと仮定した事が問題なので、0.1n以上ある
0.4n個以上(R個とする)
赤い枝：(½)B本
0.4n個以上(B個とする)
青い枝：0.2n本
0.1n個より少ない

主張6.8：mixedな頂点が少なくとも0.1n個
ある（証明済み）

定理６．７：任意のbalanced-coloringな
Knはある定数ε>0 が存在し、collisionfreeな三角形を少なくともεn2個もつ
mixedな頂点が0.1n個以上存在する。
mixedなためそれぞれの頂点から
0.2n以上の赤い枝、0.2n以上の青い枝が出ている。
赤い枝：0.2n本
青い枝：0.2n本
mixedな頂点からmixedでない頂点へは
赤い枝が0.1n以上、青い枝が0.1n以上出ている
赤い枝：0.2n本
青い枝：0.2n本
mixedな頂点からmixedでない頂点へは
赤い枝が0.1n以上、青い枝が0.1n以上出ている
赤い枝：0.1n本
青い枝：0.1n本
ここで下記の三角形に注目する。
mixedな頂点をtop-vertexとしたmixedな三角形
の数を考える。
mixedな頂点：top-vertex
黒い枝：free-edge
ここで下記の三角形に注目する。
mixedな頂点をtop-vertexとしたmixedな三角形
の数を考える。
w(e)：ある枝がそれをfree-edgeと
するようなmixedな頂点の個数
ここではw(e)>cnの枝eのみを数える。
そのような枝集合をPとおく。
(c>0であり、十分小さな定数)
w(e)=2
全三角形の個数
 0.1n 
3
3


w
(
e
)

0
.
1
n


0
.
0005
n

2
cn
･･･①

2 
eE


w(e)：ある枝がそれをfree-edgeと
するようなmixedな頂点の個数
3
w
(
e
)

E

P

cn

cn
･･･②

eE  P
 w(e)  P  0.1n･･･③
eP
ここではw(e)>cnの枝eのみを数える。
そのような枝集合をPとおく。
(c>0であり、十分小さな定数)
①、②、③を解くと
2cn 3  cn 3
P
 10cn 2
0.1n
図のようにfree-edgeが接していると、
同じmixedな頂点に対してｃｏｌｌｉｓｉｏｎとなる。
よってcollision-freeな三角形の数を考える
よってfree-edgeの最大独立集合を考える
図のようにfree-edgeが接していると、
同じmixedな頂点に対してｃｏｌｌｉｓｉｏｎとなる。
よってcollision-freeな三角形の数を考える
よってfree-edgeの最大独立集合を考える
あるfree-edgeは最大2(n-2)<2n本のfree-edgeと交わる。
よって大きさ|P|/2nの独立集合が存在する。
最大n-2本
最大n-2本
Pに属するfree-edgeはcn個以上のmixedな頂点を持つ。
また、|P|≧10cn2よりcn･|P|/2n≧5cn2>cn2個の
collision-freeでmixedな三角形が得られた
Pに属するfree-edgeはcn個以上のmixedな頂点を持つ。
また、|P|≧10cn2よりcn･|P|/2n≧5c2n2>c2n2個の
collision-freeでmixedな三角形が得られた
cn本
定理6.6

定理6.7：どのようにKnを色分けしても
(balanced)、mixedであり、 collisionfreeな三角形が少なくともΩ(n2)個存在す
る

定理6.6
このゲームの通信量はΩ(n2)である
free-edgeでない枝の一方を削除して
triangle-freeなサブグラフGを作成する。
free-edgeでない枝の一方を削除して
triangle-freeなサブグラフGを作成する。
( n2 )
個のサブグラフを作成できる。
また、それらはどの二つのグラフの和をとってきても、
triangle-freeなグラフになっていない。
2
( n2 )
個のサブグラフを作成できる。
また、それらはどの二つのグラフの和をとってきても、
triangle-freeなグラフになっていない。
2
( n2 )
個のサブグラフを作成できる。
また、それらはどの二つのグラフの和をとってきても、
triangle-freeなグラフになっていない。
2
和
( n2 )
個ため通信量は
( n 2 )
2
log( 2
)  (n )となる
 これより少ないbitで通信を行うと、何ら
かの情報を削除しなければならない。
 削除されたbit分だけ枝情報の通信が
行えていないので、その枝に関する和
集合がtriangle-freeでないのに受理
してしまう
 このゲームの通信量はΩ(n2)である

サブグラフの種類は2
色を塗ろう


今までは色の塗り方の存在についての議論
を行っていた。
次に実際に色を塗るアルゴリズムとその計
算量についての話を行う。
色を塗ろう！



{0,1}nのn-cubeの頂点を色分けしたい
{0,1}nにおいて、1の数が奇数個の頂点は
赤に、偶数個の頂点は青に塗る。
例：n=3
{000} {011} {101}{110}
{001} {010}{100} {111}
色を塗ろう！！
2n頂点塗るのにどれだけの計算量がかか
るかを考える
 以下にルールを設ける
1. 最初はどの頂点も塗られていない
2. 一回のステップでは頂点Cを黒、または白
どちらかしか塗れない
3. 頂点Cは{0,1,*}nで表現される
({0*1}={001}と{010}を表現する)
4. 一度塗られた頂点の色は変わらない

サンプルアルゴリズム
例：n=3
1. {100}{010}{001}{111}を赤で塗る
2. {***}を青で塗る
{000}
{001}
 計5ステップ

{010}
{011}
{100}
{101}
{110}
{111}
上記のように自明に2n-1+1ステップで色を塗れる
サンプルアルゴリズム！
例：n=3
1. {100}{010}{001}{111}を赤で塗る
2. {***}を青で塗る
{000}
{001}
 計5ステップ

{010}
{011}
{100}
{101}
{110}
{111}
上記のように自明に2n-1+1ステップで色を塗れる
サンプルアルゴリズム！！
例：n=3
1. {100}{010}{001}{111}を赤で塗る
2. {***}を青で塗る
{000}
{001}
 計5ステップ

{010}
{011}
{100}
{101}
{110}
{111}
上記のように自明に2n-1+1ステップで色を塗れる
効率のいいアルゴリズム
n=kmとする。k,mはint
 C={0,1,*}nをk個のsubcubeに分割する。
C={C1,C2,…,Ck}。Ci={0,1,*}m
1. j=0,1,…,kと以下を行う
2. j個のCi={*}mであり、残りのk-j個のCiの
1の数の合計が偶数の全ての頂点を、jが
偶数のときは青、奇数のときは赤を塗る。

アルゴリズム動作例(n=4,k=2,m=2)

j=0


j=1



{00**},{11**},{**00},{**11}を赤でぬ
る
j=2


{0000},{0011},{1100},{1111}を青でぬ
る。
{****}を青でぬる
計９ステップ
このアルゴリズムの正しさは省略
アルゴリズムの計算量

ステップjはkCj通りの{*}mのCi集合それぞ
れに対して、(2m-1)k-j通りの頂点がある。
 k  m 1
  2

j 0  j 
k



k j

 2
m 1

1
k
m=3のとき、5n/3<1.71nの計算量である。
計算量の下界


定理6.10 どんなアルゴリズムでもn-cube
n 1
3
 
を色分けするには 2 2  のステップを要する
Snをn-cubeを塗るのに必要な最低ステップ
数とする。S1=2,S2=3が示される。
Sn≧(3/2)Sn-1を示す。
証明：定理6.10
Sn≧
3
2 
2
n 1
もっとも効率のよい塗り方Pを以下で表す
(C1,a1),(C2,a2),(C3,a3),…,(C|P|,a|P|)
 Ci={0,1,*}n、ai={赤、青}
 ここでPをP0,P1,P*に分ける
 P0はCiのうち0Ci’の形の物(P1、P*も同様)
 例:P=({001}赤)({010}赤) ({100}赤)({111}

赤)({***}青)のとき
P0=({001}赤)({010}赤)、
P1=({100}赤)({111}赤),P*=({***}青)

Sn=|P|=|P0|+|P1|+|P*|
証明：定理6.10



P0
P1
P*
Sn≧
3
2 
2
n 1
ここでP0+P*に注目する
|P0|+|P*|≧Sn-1が言える
なぜならP0+P*は、先頭bitが0であるn-cube
を全て正しく塗っているため、先頭bitを除いた
n-1cubeを正しく色分けしている。
{010}、赤
{001}、赤
{100}、赤
{111}、赤
{***}、青
P0+P*
{010},赤
{001},赤
{***},青
{000}
{001}
{010}
{011}
{100}
{101}
{110}
{111}
証明：定理6.10



P0
P1
P*
Sn≧
3
2 
2
n 1
ここでP0+P*に注目する
|P0|+|P*|≧Sn-1が言える
なぜならP0+P*は、先頭bitが0であるn-cube
を全て正しく塗っているため、先頭bitを除いた
n-1cubeを正しく色分けしている。
{010}、赤
{001}、赤
{100}、赤
{111}、赤
{***}、青
P0+P*
{010},赤
{001},赤
{***},青
{000}
{001}
{010}
{011}
証明：定理6.10



P0
P1
P*
Sn≧
3
2 
2
n 1
ここでP0+P*に注目する
|P0|+|P*|≧Sn-1が言える
なぜならP0+P*は、先頭bitが0であるn-cube
を全て正しく塗っているため、先頭bitを除いた
n-1cubeを正しく色分けしている。
{010}、赤
{001}、赤
{100}、赤
{111}、赤
{***}、青
P0+P*
{010},赤
{001},赤
{***},青
{00}
{01}
{10}
{11}
証明：定理6.10





Sn≧
3
2 
2
n 1
ここでP0+P*に注目する
|P0|+|P*|≧Sn-1が言える。
なぜならP0+P*は、先頭bitが0であるn-cube
を全て正しく塗っているため、先頭bitを除いた
n-1cubeを正しく色分けしている。
P1+P*も同様に先頭bitが1であるn-cubeは
全て正しく塗っているため、先頭bitを除いて、
色を反転させる事でn-1cubeを正しく塗ってい
る|P1|+|P*|≧Sn-1
|P|=|P0|+|P1|+|P*|≧Sn-1+max(|P0|,|P1|)
証明：定理6.10





Sn≧
3
2 
2
n 1
Sn≧Sn-1+max(|P0|,|P1|)を示した。
|P0|+|P1|≧Sn-1を示す
n-1cubeのある頂点yを考える。
yはPにおいてCi={0y,1y,*y}の形で表れる
が、必ず対応する0yや1yが存在する。
*yだけしか存在しないとすると、Pが色をきちん
と塗れていない。
P
{0000}青
{0011}青
{1100}青
{1111}青
{00**}赤
{11**}赤
{**00}赤
{**11}赤
{****}青
{000}
{001}
{010}
{011}
{100}
{101}
{110}
{111}
全てのyは対応するP0かP1が存在する
証明：定理6.10






Sn≧
3
2 
2
n 1
Sn≧Sn-1+max(|P0|,|P1|)を示した。
|P0|+|P1|≧Sn-1を示す
n-1cubeのある頂点yを考える。
yはPにおいてCi={0y,1y,*y}の形で表れる
が、必ず対応する0yや1yが存在する
n-1cubeの全ての頂点はP0もしくは、P1に表
れる。|P0|+|P1|≧Sn-1
Sn≧Sn-1+max(|P0|,|P1|)≧
Sn-1+(|P0|+|P1|/2)≧(3/2) Sn-1

Download Report