構造の数理

(1)

構造の数理

年月日第回目の講義

渕野昌

神戸大学大学院システム情報学研究科

の定理

神戸大学年度後期の講義

!

(2)

の定理の特殊な形 ^{構造の数理}

問題．任意の自然数に対して，

個以上の頂点を持つすべてのグラフに，かの少なくともつを誘導された部分グラフとして埋め込むことができる

が成り立つような数が存在するか？

年昭和年

これよりもっと一般的な存在定理を証明している．

!"# $ %&'年昭和年

の結果とは独立．の値の評価を与えている．

(3)

の定理 ^{構造の数理} 定理．任意の自然数に対して，

個以上の頂点を持つすべてのグラフに，かの少なくともつを誘導された部分グラフとして埋め込むことができる

が成り立つような数が存在する．

帰納法で証明する．

証明を帰納法に乗せるために，もとの主張ではなく，それよりさらに一般的でより強い主張を証明する，という前にも何度か出てきたパターンを用いる⁽

定理．とを正の自然数とする．頂点の数が ^"

以上の任意のグラフには，かの少なくともつを誘導された部分グラフとして埋め込むことができる．

(4)

の定理 ^{構造の数理} 定理．とを正の自然数とする．頂点の数が ^"

は，

と書くこともある．

は，個のものから個選び出す選び方の総数である．

) *

* *

である．

*) は，個のものを一列にならべる並べ方の総数である．

したがって， ^*

*

は個のものから個のものを選んで一列に並べる並べ方の総数となる．

よって， ^*

* *

は個のものから個のものを選ぶ選び方の総数になる．

(5)

は，

) *

* *

である．

*) は，個のものを一列にならべる並べ方の総数である．

したがって， ^*

*

は個のものから個のものを選んで一列に並べる並べ方の総数となる．

よって， ^*

* *

は個のものから個のものを選ぶ選び方の総数になる．

(6)

は，

) *

* *

だから， ^"

)

+ *

* *

である．

!",-%& の定理で，⁾ と置くと，

系．頂点の数が

(7)

の定理の証明 ^{構造の数理} 定理．とを正の自然数とする．頂点の数が ^"

証明． ⁾ または ⁾ の場合 ^½ も^½ も点からなるグラフだから，任意のグラフに誘導された部分グラフとして埋め込める．したがって特に ^"

以上の頂点を持つグラフに対し，この主張が成り立つ．

) または ⁾ の場合 ⁾ とする．^¾ は辺で繋がっていない頂点だから，もし ¾ がグラフに埋め込めないなら，は完全グラフである．したがって， ^"

) 個以上の頂点を持つグラフに対して，¾ かのどちらかが誘導された部分グラフとして埋め込める． ⁾ のときも同様⁽ このときには ¾ がに埋め込めないなら，の頂点の数をとすると， ⁾ である．

(8)

の定理の証明 ^{構造の数理}

+ に関する帰納法で，定理を証明する．⁺ ^'なら，

かのどちらかはとなるから，前ページで示したことから，

定理は成り立つ．

したがって， ^' で，⁺ となる ^. に対しては定理が成り立つと仮定して， ⁺ ⁾ となるような ^. に対しても定理が成り立つことを示せばよい．次の公式を使う⁽

)

+

ただし，^. とする．

/ 個のものから個選ぶ選び方は，個のもののうちのつ^£ を固定して，^£ 以外の個の中から個選ぶか，^£ を選び，

残りの個の中から個選ぶかのどちらかである．⁰ この式のとに⁺ とを代入すると⁽

"

)

" #

+

" #

(9)

""

)

" #

+

" #

この式を少し変形して

""

"

+

"

ここで，頂点の数が， ^"

以上のグラフを考える．

の頂点のつ^£ を固定して，から ^£ を除いて得られるグラフを ^¼ とする．このとき，上の不等式から，

£ は，

"

個以上の頂点のどれとも繋がっていないか，

"

個の以上の頂点のどれとも繋がっているかのどちらかが成り立つ．

(10)

£ は，

"

個以上の頂点のどれとも繋がっていないか，

"

個の以上の頂点のどれとも繋がっているかのどちらかが成り立つ．

の場合には，^¼ の ^£ と繋がっていない頂点の全体から誘導されたの部分グラフを ^¼¼ とすると，帰納法の仮定から，

¼¼ に

α

か

β

½ を誘導された部分グラフとして埋め込める．

α

の場合には，はにも埋め込めるからよい．

β

の場合には， ^½ 埋めこんだ先を^¼ ^¼¼ とすると，^¼ に^£ を加えたものは，のへの誘導された部分グラフとしての埋め込みになっている．したがって両方の場合について定理が成り立つ．

の場合にも同様である演習

(11)

ラムズィー数 ^{構造の数理}

上の定理から次が得られた⁽ 系．頂点の数が

自然数に対し，

頂点の数が以上の任意のグラフにかの少なくともつを誘導された部分グラフとして埋め込むことができる．

を満たすような数のうち最小のものをと書く．はに対応するラムズィー数と呼ばれている．

前回に示した ^!"# の定理と，^!"#^-%& の定理の系により

である．

(12)

ラムズィー数 ^{構造の数理} 上の証明と，前回に示したことから ⁾⁾ ⁾¹ である．¹ は演習問題とした．

2)である 34"-35. ''．

'から先は値が判っていない．

2'2.11' などが知られている．

)'1'1'222.

).

)6.

$

)' なので，上の ^'と ¹の評価は，^!"# の定理と ^!"#^-%& の定理による下限と上限の評価よりずっとシャープな精度の高いものになっていることがわかる．

上限と下限が判っているので，原理的には有限個の場合についてしらみつぶしに計算すれば値が求まるはずだが，場合の数が多すぎて，そのような計算では宇宙の始まりから今までの時間より長い時間がかかってしまう可能性もある！

(13)

ラムズィー数 ^{構造の数理} 次は ^!"# が，生前，彼の講演でよく話していたジョークである⁽

7 宇宙人が地球を侵略しに来て^'の値を一年の間に求められなければ地球を滅ぼす，と言ったとしたら，世界の最高の知性とコンピュータをかきあつめればなんとかなるだろう．しかし，

もし ¹の値を一年の間に求められなければ地球を滅ぼす，と言ったのだったら，覚悟をきめて宇宙人に反撃する決断を下すべきである．⁸

演習問題． ^'や ¹の値をすべての場合をしらみつぶしに調べるやり方で求めるとすると，最悪どのくらいの時間が必要になるかを評価してみてください．

(14)

エルデシュ ^! ^" ^{構造の数理}

大正 ^! 平成^"^#$