.
数理解析 第 14 回
ラムゼー理論
.
岡本 吉央
[email protected]
電気通信大学
2013 年 1 月 29 日
最終更新:2013 年 1 月 30 日
岡本 吉央 (電通大)
数理解析 (14)
09:03
2013 年 1 月 29 日
1 / 53
期末試験
▶
日時:2/12 (火) 10:40∼12:10
▶
場所:西 5–209
出題形式
▶
▶
▶
▶
▶
▶
配点:1 題 30 点満点,計 120 点満点
成績において,100 点以上は 100 点で打ち切り
▶
▶
演習問題と同じ形式の問題を 4 題出題する
その中の 3 題は演習問題として提示されたものと同一である
全問に解答する
科目全体の成績は山本先生担当分と総合して判定
持ち込み:A4 用紙 1 枚分 (裏表自筆書き込み) のみ可
岡本 吉央 (電通大)
数理解析 (14)
2013 年 1 月 29 日
2 / 53
概要
.
今日の目標
.
ラムゼー理論の基礎概念を理解する
.
▶
ラムゼー理論とは何か?
▶
ラムゼー数
▶
ラムゼー理論の応用:ゼロ誤り通信路容量
岡本 吉央 (電通大)
数理解析 (14)
2013 年 1 月 29 日
3 / 53
ラムゼー理論とは?
目次
1.
ラムゼー理論とは?
2.
グラフに対するラムゼー理論とは?
3.
グラフに対するラムゼー数
4.
グラフに対する多色ラムゼー数
5.
ラムゼー理論の応用
6.
今日のまとめ
岡本 吉央 (電通大)
数理解析 (14)
2013 年 1 月 29 日
4 / 53
ラムゼー理論とは?
Frank P. Ramsey
イギリスの思想家,経済学者 (1903–1930)
http://en.wikipedia.org/wiki/File:Frank Plumpton Ramsey.JPG
岡本 吉央 (電通大)
数理解析 (14)
2013 年 1 月 29 日
5 / 53
ラムゼー理論とは?
ラムゼー理論とは?
.
D. West の本 (’01) からの引用 (の試訳)
.
「ラムゼー理論」とは大きな構造の分割に関する研究を指す.典型的な
結果は,分割のある類に特殊な部分構造が必ず生起するというものであ
る.モツキンは「完全な無秩序は不可能である」ということばでこれを
表現した.我々が考える対称は単に集合や数であり,
...
.
原文:“Ramsey theory” refers to the study of partitions of large structures. Typical
results state that a special substructure must occur in some class of the partition.
Motzkin described this by saying that “Complete disorder is impossible.” The objects we
consider are merely sets and numbers, ...
.
格言
.
物理学に「物理学的現象」,生物学に「生物学的現象」があるように
数学にも「数学的現象」が存在する
.
岡本 吉央 (電通大)
数理解析 (14)
2013 年 1 月 29 日
6 / 53
ラムゼー理論とは?
ちょっとした例
平面上に,どの 3 点も一直線上にのらないように 10 点置く
必ず,そこには (中に他の点を含まない) 凸五角形が現れる
(Harborth ’78)
岡本 吉央 (電通大)
数理解析 (14)
2013 年 1 月 29 日
7 / 53
ラムゼー理論とは?
ちょっとした例
平面上に,どの 3 点も一直線上にのらないように 10 点置く
必ず,そこには (中に他の点を含まない) 凸五角形が現れる
(Harborth ’78)
岡本 吉央 (電通大)
数理解析 (14)
2013 年 1 月 29 日
7 / 53
ラムゼー理論とは?
集合の 2 分割
有限集合 X = {1, . . . , n},自然数 a, b ,n = a + b − 1
.
観察
.
X の任意の 2 分割 X = X1 ∪ X2 に対して (ただし,X1 ∩ X2 = ∅)
|X1 | ≥ a
または
|X2 | ≥ b
が成り立つ
.
証明:演習問題
岡本 吉央 (電通大)
数理解析 (14)
2013 年 1 月 29 日
8 / 53
ラムゼー理論とは?
集合の r 分割
有限集合 X = {1, . . . , n},自然数 a1 , . . . , ar ,n = a1 + · · · + ar − r + 1
.
観察
.
X の任意の r 分割 X = X1 ∪ · · · ∪ Xr に対して
(ただし,任意の i ̸= j ∈ {1, . . . , r } に対して Xi ∩ Xj = ∅)
|X1 | ≥ a1
または
···
または
|Xr | ≥ ar
.が成り立つ
証明:演習問題
これは鳩の巣原理とも呼ばれる
岡本 吉央 (電通大)
数理解析 (14)
2013 年 1 月 29 日
9 / 53
ラムゼー理論とは?
今から行うこと
▶
集合の分割に対する観察をグラフに対して行う
▶
特に,完全グラフの辺集合を分割する
岡本 吉央 (電通大)
数理解析 (14)
2013 年 1 月 29 日
10 / 53
グラフに対するラムゼー理論とは?
目次
1.
ラムゼー理論とは?
2.
グラフに対するラムゼー理論とは?
3.
グラフに対するラムゼー数
4.
グラフに対する多色ラムゼー数
5.
ラムゼー理論の応用
6.
今日のまとめ
岡本 吉央 (電通大)
数理解析 (14)
2013 年 1 月 29 日
11 / 53
グラフに対するラムゼー理論とは?
復習:完全グラフ
無向グラフ G = (V , E ),自然数 n ∈ N
.
完全グラフとは?
.
G が次のグラフと同型であるとき,G は頂点数 n の完全グラフと呼ばれる
.
▶
頂点集合 = {1, 2, . . . , n}
▶
辺集合 = {{u, v } | 1 ≤ u < v ≤ n}
頂点数 n の完全グラフを Kn と表記する
K1
岡本 吉央 (電通大)
K2
K3
K4
数理解析 (14)
K5
K6
K7
2013 年 1 月 29 日
12 / 53
グラフに対するラムゼー理論とは?
完全グラフの辺集合の分割
K6 の辺集合を 2 分割して,2 つのグラフを得る
岡本 吉央 (電通大)
数理解析 (14)
2013 年 1 月 29 日
13 / 53
グラフに対するラムゼー理論とは?
完全グラフの辺集合の分割
K6 の辺集合を 2 分割して,2 つのグラフを得る
岡本 吉央 (電通大)
数理解析 (14)
2013 年 1 月 29 日
13 / 53
グラフに対するラムゼー理論とは?
K6 に対するラムゼー理論
.
K6 に対するラムゼー理論
.
K6 の辺集合を任意に 2 分割してできたグラフ G1 , G2 において
G1 が K3 を含む または
G2 が K3 を含む
が成り立つ
.
.
比喩的に,次のような言われ方もする
.
6 人出席者のいるパーティーでは,互いに知り合いである 3 人組か,
互いに知り合いではない
3 人組が必ず存在する
.
岡本 吉央 (電通大)
数理解析 (14)
2013 年 1 月 29 日
14 / 53
グラフに対するラムゼー理論とは?
K6 に対するラムゼー理論:証明 (1)
▶
K6 の頂点を 1 つ任意に選んで,v とする
▶
v に接続する辺は 5 つ存在
▶
その中の 3 つは G1 か G2 に存在
▶
この 3 つが G1 に存在する場合を考える
(G2 に存在する場合も同様)
▶
その 3 辺に接続する v 以外の頂点を a, b, c とする
v
(補足:集合の 2 分割)
c v
v
b
a
岡本 吉央 (電通大)
数理解析 (14)
2013 年 1 月 29 日
15 / 53
グラフに対するラムゼー理論とは?
K6 に対するラムゼー理論:証明 (2) 場合分け
場合 1:a, b, c を結ぶ辺がすべて G2 に含まれるとき
▶
a, b, c を頂点集合とする K3 が G2 に含まれる
場合 2:そうではないとき
▶
a, b, c を結ぶ辺の 1 つは G1 に含まれる
▶
それを {a, b} であるとする (他の場合も同様)
▶
a, b, v を頂点とする K3 が G1 に含まれる
v
c v
v
b
a
岡本 吉央 (電通大)
数理解析 (14)
2013 年 1 月 29 日
16 / 53
グラフに対するラムゼー理論とは?
K6 に対するラムゼー理論:証明 (2) 場合分け
場合 1:a, b, c を結ぶ辺がすべて G2 に含まれるとき
▶
a, b, c を頂点集合とする K3 が G2 に含まれる
場合 2:そうではないとき
▶
a, b, c を結ぶ辺の 1 つは G1 に含まれる
▶
それを {a, b} であるとする (他の場合も同様)
▶
a, b, v を頂点とする K3 が G1 に含まれる
v
c v
v
b
a
岡本 吉央 (電通大)
数理解析 (14)
2013 年 1 月 29 日
16 / 53
グラフに対するラムゼー理論とは?
K6 に対するラムゼー理論:証明 (2) 場合分け
場合 1:a, b, c を結ぶ辺がすべて G2 に含まれるとき
▶
a, b, c を頂点集合とする K3 が G2 に含まれる
場合 2:そうではないとき
▶
a, b, c を結ぶ辺の 1 つは G1 に含まれる
▶
それを {a, b} であるとする (他の場合も同様)
▶
a, b, v を頂点とする K3 が G1 に含まれる
v
c v
v
b
a
岡本 吉央 (電通大)
数理解析 (14)
2013 年 1 月 29 日
16 / 53
グラフに対するラムゼー理論とは?
K6 に対するラムゼー理論:証明 (2) 場合分け
場合 1:a, b, c を結ぶ辺がすべて G2 に含まれるとき
▶
a, b, c を頂点集合とする K3 が G2 に含まれる
場合 2:そうではないとき
▶
a, b, c を結ぶ辺の 1 つは G1 に含まれる
▶
それを {a, b} であるとする (他の場合も同様)
▶
a, b, v を頂点とする K3 が G1 に含まれる
v
c v
v
b
a
岡本 吉央 (電通大)
数理解析 (14)
2013 年 1 月 29 日
16 / 53
グラフに対するラムゼー理論とは?
グラフに対するラムゼー理論とは?
▶
完全グラフの辺集合を分割して,グラフ G1 , . . . , Gr を得る
▶
このとき,その中のどれかがある大きさの完全グラフを含む
先ほどの例
▶
頂点数 6 の完全グラフの辺集合を 2 分割
▶
このとき,どちらかが頂点数 3 の完全グラフを含む
.
注意
.
頂点数 6 の完全グラフの辺集合 2 分割でこれが成り立つので,
頂点数 7, 8, 9,... の完全グラフの辺集合を 2 分割しても
どちらかは頂点数
3 の完全グラフを必ず含む
.
頂点数 5 だとどうか?
岡本 吉央 (電通大)
数理解析 (14)
2013 年 1 月 29 日
17 / 53
グラフに対するラムゼー理論とは?
K5 の辺集合を 2 分割しても K3 は含まれないかもしれない
この意味で,
「6」が極値になっている (第 9 回参照)
岡本 吉央 (電通大)
数理解析 (14)
2013 年 1 月 29 日
18 / 53
グラフに対するラムゼー数
目次
1.
ラムゼー理論とは?
2.
グラフに対するラムゼー理論とは?
3.
グラフに対するラムゼー数
4.
グラフに対する多色ラムゼー数
5.
ラムゼー理論の応用
6.
今日のまとめ
岡本 吉央 (電通大)
数理解析 (14)
2013 年 1 月 29 日
19 / 53
グラフに対するラムゼー数
ラムゼー数
自然数 k, ℓ
.
ラムゼー数 R(k, ℓ) とは?
.
Kn の辺集合を 2 つに分けてグラフ G1 , G2 を任意に作ったとき
G1 が Kk を含む または
G2 が Kℓ を含む
.が成り立つような最小の n
先ほどの場合に対応するのは:R(3, 3) = 6
▶
R(3, 3) ≤ 6:
K6 の辺集合を 2 つに分けて G1 , G2 を任意に作ると
「G1 が K3 を含む,または,G2 が K3 を含む」が成り立つ
▶
R(3, 3) ≥ 6:
K5 の辺集合を 2 つに分けて G1 , G2 をうまく作ると
「G1 が K3 を含まず,かつ,G2 が K3 を含まない」が成り立つ
岡本 吉央 (電通大)
数理解析 (14)
2013 年 1 月 29 日
20 / 53
グラフに対するラムゼー数
ラムゼー数の上界と下界
自然数 k, ℓ
.
ラムゼー数 R(k, ℓ) とは?
.
Kn の辺集合を 2 つに分けてグラフ G1 , G2 を任意に作ったとき
G1 が Kk を含む または
G2 が Kℓ を含む
.が成り立つような最小の n
R(k, ℓ) = N を証明するには…
▶
R(k, ℓ) ≤ N の証明:
KN の辺集合を 2 つに分けて G1 , G2 を任意に作ると
「G1 が Kk を含む,または,G2 が Kℓ を含む」が成り立つ
▶
R(k, ℓ) ≥ N :
KN−1 の辺集合を 2 つに分けて G1 , G2 をうまく作ると
「G1 が Kk を含まず,かつ,G2 が Kℓ を含まない」が成り立つ
岡本 吉央 (電通大)
数理解析 (14)
2013 年 1 月 29 日
21 / 53
グラフに対するラムゼー数
ラムゼー数に対する疑問
.
疑問
.
任意の自然数 k, ℓ に対して,十分に大きな N を考えると
KN の辺集合を 2 つに分けて G1 , G2 を任意に作ったとき
G1 が Kk を含む または
G2 が Kℓ を含む
.は成り立つのか?
.
疑問:別の言い方
.
任意の自然数
k, ℓ に対して,R(k, ℓ) は存在するのか?
.
岡本 吉央 (電通大)
数理解析 (14)
2013 年 1 月 29 日
22 / 53
グラフに対するラムゼー数
ラムゼー数の存在性
.
グラフに対するラムゼーの定理
.
任意の自然数 k, ℓ に対して,ある自然数 N が存在して
KN の辺集合を 2 分割して G1 , G2 を任意に作ると
G1 が Kk を含む または
G2 が Kℓ を含む
.が成り立つ
わざわざ難しく書くと
▶
∀ 自然数 k, ℓ
▶
∃ 自然数 N
▶
∀ KN の辺集合の 2 分割から作られる G1 , G2 :
▶
G1 が Kk を含む ∨ G2 が Kℓ を含む
岡本 吉央 (電通大)
数理解析 (14)
2013 年 1 月 29 日
23 / 53
グラフに対するラムゼー数
ラムゼー数の存在性:証明
証明は以下の再帰式に基づいた帰納法
.
ラムゼー数に対する再帰式
.
次の式が成立する
.
▶
任意の k ≥ 1 に対して,R(k, 1) = 1
▶
任意の ℓ ≥ 1 に対して,R(1, ℓ) = 1
▶
任意の k, ℓ > 1 に対して,R(k, ℓ) ≤ R(k − 1, ℓ) + R(k, ℓ − 1)
これが証明できれば,グラフに対するラムゼーの定理の証明になる
▶
R(k, 1) = 1 と R(1, ℓ) = 1 は簡単.主題は最後の不等式
岡本 吉央 (電通大)
数理解析 (14)
2013 年 1 月 29 日
24 / 53
グラフに対するラムゼー数
ラムゼー数に対する再帰式:証明 (1)
N = R(k, ℓ − 1) + R(k − 1, ℓ) とする
▶
KN の頂点を 1 つ任意に選んで,v とする
▶
v に接続する辺は N − 1 個存在
▶
その中の R(k − 1, ℓ) 個が G1 に存在するか,または,
その中の R(k, ℓ − 1) 個が G2 に存在
(補足:集合の 2 分割)
v
岡本 吉央 (電通大)
v
≥ R(k − 1, ℓ)
数理解析 (14)
v
2013 年 1 月 29 日
25 / 53
グラフに対するラムゼー数
ラムゼー数に対する再帰式:証明 (2)
v に接続する辺の中の R(k − 1, ℓ) 個が G1 に存在するとき
▶
それらの辺に接続する v 以外の頂点の集合を X とする
▶
|X | ≥ R(k − 1, ℓ)
帰納法の仮定から,X の頂点を見ると
▶
1
2
その中の k − 1 頂点を結ぶ辺がすべて G1 に含まれる,または
その中の ℓ 頂点を結ぶ辺がすべて G2 に含まれる
v
v
≥ R(k − 1, ℓ)
v
X
岡本 吉央 (電通大)
数理解析 (14)
2013 年 1 月 29 日
26 / 53
グラフに対するラムゼー数
ラムゼー数に対する再帰式:証明 (3)
場合 1:X の中の k − 1 頂点を結ぶ辺がすべて G1 に含まれる
▶
G1 において,それら k − 1 個の頂点と v が Kk を作る
場合 2:X の中の ℓ 頂点を結ぶ辺がすべて G2 に含まれる
▶
G2 において,それら ℓ 個の頂点が Kℓ を作る
v
v
≥ R(k − 1, ℓ)
v
X
岡本 吉央 (電通大)
数理解析 (14)
2013 年 1 月 29 日
27 / 53
グラフに対するラムゼー数
ラムゼー数に対する再帰式:証明 (4)
v に接続する辺の中の R(k, ℓ − 1) 個が G2 に存在するとき
▶
それらの辺に接続する v 以外の頂点の集合を X とする
▶
|X | ≥ R(k, ℓ − 1)
帰納法の仮定から,X の頂点を見ると
▶
1
2
その中の k 頂点を結ぶ辺がすべて G1 に含まれる,または
その中の ℓ − 1 頂点を結ぶ辺がすべて G2 に含まれる
v
v
≥ R(k, ℓ − 1)
v
X
岡本 吉央 (電通大)
数理解析 (14)
2013 年 1 月 29 日
28 / 53
グラフに対するラムゼー数
ラムゼー数に対する再帰式:証明 (5)
場合 1:X の中の k 頂点を結ぶ辺がすべて G1 に含まれる
▶
G1 において,それら k 個の頂点が Kk を作る
場合 2:X の中の ℓ − 1 頂点を結ぶ辺がすべて G2 に含まれる
▶
G2 において,それら ℓ − 1 個の頂点と v が Kℓ を作る
v
v
≥ R(k, ℓ − 1)
v
X
岡本 吉央 (電通大)
数理解析 (14)
2013 年 1 月 29 日
29 / 53
グラフに対するラムゼー数
ラムゼー数の上界
.
ラムゼー数に対する再帰式 (再掲)
.
次の式が成立する
.
▶
任意の k ≥ 1 に対して,R(k, 1) = 1
▶
任意の ℓ ≥ 1 に対して,R(1, ℓ) = 1
▶
任意の k, ℓ > 1 に対して,R(k, ℓ) ≤ R(k − 1, ℓ) + R(k, ℓ − 1)
この式から次の上界が得られる (演習問題)
(
)
k +ℓ−2
R(k, ℓ) ≤
k −1
( )
a
ただし,
とは二項係数 (組合せの総数,a Cb とも書く)
b
( )
a
a!
(ただし,a ≥ b)
=
b!(a − b)!
b
岡本 吉央 (電通大)
数理解析 (14)
2013 年 1 月 29 日
30 / 53
グラフに対するラムゼー数
ラムゼー数に対する上界の表
.(
)
k+ℓ−2
.
k−1
の表
k\ℓ
1
2
3
4
5
6
7
.
岡本 吉央 (電通大)
1
1
1
1
1
1
1
1
2
1
2
3
4
5
6
7
3
1
3
6
10
15
21
28
4
1
4
10
20
35
56
84
数理解析 (14)
5
1
5
15
35
70
126
210
6
1
6
21
56
126
252
462
7
1
7
28
84
210
462
924
2013 年 1 月 29 日
31 / 53
グラフに対するラムゼー数
小さなラムゼー数の表
.
小さなラムゼー数の表
.
k\ℓ 1 2
3
1 1 1
1
2 1 2
3
3 1 3
6
4 1 4
9
5 1 5 14
6 1 6 18
7 1 7 23
.
4
1
4
9
18
25
35–41
49–61
5
1
5
14
25
43–49
58–87
80–143
6
1
6
18
35–41
58–87
102–165
113–298
7
1
7
23
49–61
80–143
113–298
205–540
(Radziszowski ’11 によるまとめ)
.
未解決問題
.
この表にあるギャップを埋めよ
(R(5,
5) = 43 であると予想されている)
.
岡本 吉央 (電通大)
数理解析 (14)
2013 年 1 月 29 日
32 / 53
グラフに対する多色ラムゼー数
目次
1.
ラムゼー理論とは?
2.
グラフに対するラムゼー理論とは?
3.
グラフに対するラムゼー数
4.
グラフに対する多色ラムゼー数
5.
ラムゼー理論の応用
6.
今日のまとめ
岡本 吉央 (電通大)
数理解析 (14)
2013 年 1 月 29 日
33 / 53
グラフに対する多色ラムゼー数
2 分割から r 分割へ
.
ここまでの話
.
.KN の辺集合を 2 分割して G1 , G2 を作ったとき,...
.
ここからの話
.
K
. N の辺集合を r 分割して G1 , . . . , Gr を作ったとき,...
岡本 吉央 (電通大)
数理解析 (14)
2013 年 1 月 29 日
34 / 53
グラフに対する多色ラムゼー数
多色ラムゼー数
自然数 k1 , . . . , kr
.
r 色ラムゼー数 R(k1 , . . . , kr ) とは?
.
Kn の辺集合を r 個に分けてグラフ G1 , . . . , Gr を任意に作ったとき
G1 が Kk1 を含む または
···
または
Gr が Kkr を含む
.が成り立つような最小の n
岡本 吉央 (電通大)
数理解析 (14)
2013 年 1 月 29 日
35 / 53
グラフに対する多色ラムゼー数
多色ラムゼー数に対する上界
.
多色ラムゼー数に対する再帰式 (演習問題)
.
次の式が成立する
▶
k1 , . . . , kr の中のどれかが 1 のとき,R(k1 , . . . , kr ) = 1
▶
そうでないとき,
R(k1 , . . . , kr ) ≤ 2 − r +
.
r
∑
R(k1 , . . . , ki − 1, . . . , kr )
i=1
.
多色ラムゼー数に対する上界
.
1 以上の任意の自然数 k1 , . . . , kr に対して
R(k1 , . . . , kr ) ≤
.
岡本 吉央 (電通大)
(k1 + · · · + kr − r )!
(k1 − 1)! · · · · · (kr − 1)!
数理解析 (14)
2013 年 1 月 29 日
36 / 53
ラムゼー理論の応用
目次
1.
ラムゼー理論とは?
2.
グラフに対するラムゼー理論とは?
3.
グラフに対するラムゼー数
4.
グラフに対する多色ラムゼー数
5.
ラムゼー理論の応用
6.
今日のまとめ
岡本 吉央 (電通大)
数理解析 (14)
2013 年 1 月 29 日
37 / 53
ラムゼー理論の応用
ラムゼー理論の応用
ラムゼー理論は数学的現象を探究するだけではなく,
広い応用を持つ
.
格言
.
「応用」と言うときには,
常に学問の階層性,社会の階層性,自然の階層性を念頭に置き,
応用の範囲を明確にする
.
ここでは,ラムゼー理論を別の理論へ応用する,という意味
(学問の中での応用)
岡本 吉央 (電通大)
数理解析 (14)
2013 年 1 月 29 日
38 / 53
ラムゼー理論の応用
応用について
http://xkcd.com/435/
岡本 吉央 (電通大)
数理解析 (14)
2013 年 1 月 29 日
39 / 53
ラムゼー理論の応用
ゼロ誤り通信路容量 (1)
▶
アルファベット {a, b, c, d, e} を持つ通信路を考える
▶
このとき,以下のグラフが表す混同が起こり得ると考える
a
e
b
c
d
▶
混同がなければ,log2 5 ≈ 2.32 ビット/伝送
▶
混同があるので,これほど大きな容量は達成できない
岡本 吉央 (電通大)
数理解析 (14)
2013 年 1 月 29 日
40 / 53
ラムゼー理論の応用
ゼロ誤り通信路容量 (2):グラフの独立集合
▶
a, c を使って符号化:log2 2 = 1 ビット/伝送
▶
a, c は混同されない
a
e
b
c
d
.
グラフの独立集合とは?
.
無向グラフ G = (V , E ) の独立集合とは,頂点部分集合 I ⊆ V で,
.I の任意の 2 頂点間に G の辺が存在しないもの
グラフ G の独立数 α(G ) = G の独立集合の要素数の最大値
▶
{a, c} は混同グラフの独立集合
岡本 吉央 (電通大)
数理解析 (14)
2013 年 1 月 29 日
41 / 53
ラムゼー理論の応用
ゼロ誤り通信路容量 (3):符号語長を 2 にすると
▶
aa, bc, ce, db, ed で符号化:(log2 5)/2 ≈ 1.16 ビット/伝送
▶
これらは混同されない (なぜ?)
a
e
b
c
d
⇝ 符号語長が 2 の場合の混同グラフを描いてみる
岡本 吉央 (電通大)
数理解析 (14)
2013 年 1 月 29 日
42 / 53
ラムゼー理論の応用
ゼロ誤り通信路容量 (3):符号語長が 2 の場合の混同グラフ
aa
ba
bb
bc
ab
ae
be ac
ad eb
cc
ee
ec
bd
ca
cb
ea
ed
da
ce db
cd
dc
de
dd
{aa, bc, ce, db, ed} はこのグラフの独立集合
.
疑問
.
▶ もっと要素数の大きな独立集合はあるか?
.
▶
混同グラフが別の形をしている場合はどうか?
岡本 吉央 (電通大)
数理解析 (14)
2013 年 1 月 29 日
43 / 53
ラムゼー理論の応用
ゼロ誤り通信路容量 (3):符号語長が 2 の場合の混同グラフ
aa
ba
bb
bc
ab
ae
be ac
ad eb
cc
ee
ec
bd
ca
cb
ea
ed
da
ce db
cd
dc
de
dd
{aa, bc, ce, db, ed} はこのグラフの独立集合
.
疑問
.
▶ もっと要素数の大きな独立集合はあるか?
.
▶
混同グラフが別の形をしている場合はどうか?
岡本 吉央 (電通大)
数理解析 (14)
2013 年 1 月 29 日
43 / 53
ラムゼー理論の応用
グラフの積
無向グラフ G = (VG , EG ), H = (VH , EH )
.
グラフの積とは?
.
G と H の積 G ⊠ H とは次のグラフ
▶
▶
頂点集合は VG × VH (直積)
(u1 , v1 ) と (u2 , v2 ) の間に辺があるのは次のときのみ
▶
▶
.
▶
{u1 , u2 } ∈ EG かつ {v1 , v2 } ∈ EH
u1 = u2 かつ {v1 , v2 } ∈ EH
{u1 , u2 } ∈ EG かつ v1 = v2
aa
ab
ae
be ac
ad eb
a
ba
bb
ea
ee
e
b
bc
cb
c
ec
bd
ca
ed
da
ce db
de
d
cc
C5
岡本 吉央 (電通大)
数理解析 (14)
cd
dc
C5 ⊠ C5
dd
2013 年 1 月 29 日
44 / 53
ラムゼー理論の応用
グラフの積の独立数とラムゼー数の関係
.
今から証明すること
.
任意の無向グラフ G , H に対して
(Herdlin ’66)
α(G ⊠ H) ≤ R(α(G ) + 1, α(H) + 1) − 1
.
証明の前に,G = C5 , H = C5 のとき,α(C5 ) = 2 なので
α(C5 ⊠ C5 ) ≤ R(2 + 1, 2 + 1) − 1 = R(3, 3) − 1 = 6 − 1 = 5
つまり,先ほど見つけたものよりも大きな独立集合は存在しない
岡本 吉央 (電通大)
数理解析 (14)
2013 年 1 月 29 日
45 / 53
ラムゼー理論の応用
グラフの積の独立数とラムゼー数の関係:証明方針
.
今から証明すること
.
任意の無向グラフ G = (VG , EG ), H = (VH , EH ) に対して
(Herdlin ’66)
α(G ⊠ H) ≤ R(α(G ) + 1, α(H) + 1) − 1
.
証明方針:N = R(α(G ) + 1, α(H) + 1) とする
▶
α(G ⊠ H) ≥ N と仮定して,矛盾を導く
▶
I を G ⊠ N の独立集合で,|I | = N のものとする
▶
ここで,I を頂点集合とする完全グラフ KN を考える
▶
ラムゼーの定理をうまく適用して矛盾を導く
岡本 吉央 (電通大)
数理解析 (14)
2013 年 1 月 29 日
46 / 53
ラムゼー理論の応用
グラフの積の独立数とラムゼー数の関係:証明 (1)
▶
I の 2 頂点 (u1 , v1 ), (u2 , v2 ) に対して,以下のどちらかが成り立つ
u1 ̸= u2 かつ {u1 , u2 } ̸∈ EG
v1 ̸= v2 かつ {v1 , v2 } ̸∈ EH
1
2
aa
ba
bb
aa
ab
ae
be ac
ad eb
ea
ee
bc
bc
ec
bd
ca
cb
ed
ed
da
ce db
de
ce
cc
岡本 吉央 (電通大)
cd
dc
db
dd
数理解析 (14)
2013 年 1 月 29 日
47 / 53
ラムゼー理論の応用
グラフの積の独立数とラムゼー数の関係:証明 (2)
▶
▶
I を頂点集合とする完全グラフ KN を考える
辺 {(u1 , v1 ), (u2 , v2 )} を G1 , G2 のどちらに入れるか以下で決める
▶
▶
条件 1 を満たすとき,G1 に入れる
そうでないとき,G2 に入れる
aa
bc
ed
ce
岡本 吉央 (電通大)
db
数理解析 (14)
2013 年 1 月 29 日
48 / 53
ラムゼー理論の応用
グラフの積の独立数とラムゼー数の関係:証明 (3)
▶
▶
▶
▶
▶
ラムゼーの定理から次のどちらかが成り立つ
(A) G1 に Kα(G )+1 が含まれる
(B) G2 に Kα(H)+1 が含まれる
(A) が成り立つときを考える ((B) のときも同様)
この Kα(G )+1 の 2 頂点 (u1 , v1 ), (u2 , v2 ) を見てみると
「u1 ̸= u2 かつ {u1 , u2 } ̸∈ EG 」を満たす
つまり,G には頂点数 α(G ) + 1 の独立集合が存在することになる
これは,α(G ) の定義に矛盾
aa
bc
ed
ce
岡本 吉央 (電通大)
db
数理解析 (14)
2013 年 1 月 29 日
49 / 53
ラムゼー理論の応用
さらなる疑問
符号語長を 2 よりも長くしたらどうなるか?
▶
符号語長を 3 にしたとき考えるのは α(G ⊠ G ⊠ G )
▶
⇝ レートは (log2 α(G ⊠ G ⊠ G ))/3 = log2 α(G ⊠ G ⊠ G )1/3
▶
符号語長を k にしたときのレートは
log2 α(G
· · ⊠ G})1/k
| ⊠ ·{z
k個
次の値をグラフ G のシャノン容量と呼んでいる
sup α(G
· · ⊠ G})1/k
| ⊠ ·{z
k→∞
k個
シャノン容量の計算は難しい問題で,ほとんどの場合未解決
岡本 吉央 (電通大)
数理解析 (14)
2013 年 1 月 29 日
50 / 53
今日のまとめ
目次
1.
ラムゼー理論とは?
2.
グラフに対するラムゼー理論とは?
3.
グラフに対するラムゼー数
4.
グラフに対する多色ラムゼー数
5.
ラムゼー理論の応用
6.
今日のまとめ
岡本 吉央 (電通大)
数理解析 (14)
2013 年 1 月 29 日
51 / 53
今日のまとめ
概要
.
今日やったこと
.
ラムゼー理論の基礎概念を理解する
.
▶
ラムゼー理論とは何か?
▶
ラムゼー数
▶
ラムゼー理論の応用:ゼロ誤り通信路容量
岡本 吉央 (電通大)
数理解析 (14)
2013 年 1 月 29 日
52 / 53
今日のまとめ
目次
1.
ラムゼー理論とは?
2.
グラフに対するラムゼー理論とは?
3.
グラフに対するラムゼー数
4.
グラフに対する多色ラムゼー数
5.
ラムゼー理論の応用
6.
今日のまとめ
岡本 吉央 (電通大)
数理解析 (14)
2013 年 1 月 29 日
53 / 53
ダウンロード

数理解析 第 14回 ラムゼー理論 - 岡本研究室