構造の数理
年月 日 第回目の講義
渕野 昌
神戸大学大学院 システム情報学研究科
の定理
神戸大学 年度後期の講義
パーティーの客 構造の数理 定理． パーティーの人の客
パーティーに人以上 の客が招かれたとき，必ず，このう ちの人で全員互に知合いであるような人がいるか，このう ちの人で，全員互に知合いでないような人がいるか，少なく ともどちらかが必ず成り立つ．
年月にアメリカ，アイダホ州 のボイジー州立大学で開かれた学会 でのランチ・パーティー
パーティーの客 構造の数理 定理． パーティーの人の客
パーティーに人以上 の客が招かれたとき，必ず，このう ちの人で全員互に知合いであるような人がいるか，このう ちの人で，全員互に知合いでないような人がいるか，少なく ともどちらかが必ず成り立つ．
証明．
パーティーの客のうちの 互いに異なる 人を
と して， に着目する．
場合 が
のうちの人以上を知っている場合．
たとえば， が と知合いだとする．
もし， のどの人も互いに知合いでないとすると，
この人は の例となっているから，定理が成り立つ．
そうでないなら，たとえば と がお互いに知合いなら，
は の例となっているから，再び定理が成り立つ．
場合 場合 が成り立たない場合．
パーティーの客 証明の続き 構造の数理
証明．
パーティーの客のうちの 互いに異なる 人を
と して， に着目する．
場合 が
のうちの人以上を知っている場合．
たとえば， が と知合いだとする．
もし， のどの人も互いに知合いでないとすると，
この人は の例となっているから，定理が成り立つ．
そうでないなら，たとえば と がお互いに知合いなら，
は の例となっているから，再び定理が成り立つ．
場合 場合 が成り立たない場合．
この場合には， と知合いでないような客が， のうちに
人以上いる．このような客の人について，場合 でと同様の 議論をすると，この場合にも定理が成り立つことが示せる 演習．
グラフ理論による言い換え 構造の数理 パーティーの各々の客を頂点として!互いに知合いである"とい う関係を辺としてグラフを考えることで，上の「定理」はグラ フの理論での命題に翻訳できる．
で 個の頂点を持つグラフですべてのつの異る頂点が辺 でつながっているようなもの 完全グラフ をあらわすのだった．
で 個の頂点を持つグラフで，辺をつも持たないような もの 空くう グラフ #$をあらわすことにする．
グラフ がグラフ から誘導された部分グラフ %%
#$ とは， の頂点の全体は の頂点の全体の部分集合 で， の任意のつの頂点が辺でつながっていることと，これら の頂点が で辺でつながっている
ことが同値になることである．
誘導された部分グラフ
ではない部分グラフ 誘導された部分グラフ
グラフ理論による言い換え 構造の数理 パーティーの各々の客を頂点として!互いに知合いである"とい う関係を辺としてグラフを考えることで，上の「定理」はグラ フの理論での命題に翻訳できる．
で 個の頂点を持つグラフですべてのつの異る頂点が辺 でつながっているようなもの 完全グラフ をあらわすのだった．
で 個の頂点を持つグラフで，辺をつも持たないような もの 空くう グラフ #$をあらわすことにする．
グラフ がグラフ から誘導された部分グラフ %%
#$ とは， の頂点の全体は の頂点の全体の部分集合 で， の任意のつの頂点が辺でつながっていることと，これら の頂点が で辺でつながっている
ことが同値になることである．
定理．個以上の頂点を持つすべてのグラフ に， か の 少なくともつを誘導された部分グラフとして埋め込むことが できる．
グラフ理論による言い換え 構造の数理 定理．個以上の頂点を持つすべてのグラフ に， か の 少なくともつを誘導された部分グラフとして埋め込むことが できる．
上で，「 に を誘導された部分グラフとして埋め込むことが できる」とは， の３つの頂点で互いに の 辺で繋がってい ないものが存在する，ということである．
上で，「 に を（誘導された）部分グラフとして埋め込むこ とができる」とは， の３つの頂点で互いに の 辺で繋がっ ているものが存在する，ということである．
問題． 任意の自然数 に対して，
個以上の頂点を持つすべてのグラフ に， か の 少なくともつを誘導された部分グラフとして埋め込むこ とができる
が成り立つような数 が存在するか？
の定理 の特殊な形 構造の数理
問題． 任意の自然数 に対して，
個以上の頂点を持つすべてのグラフ に， か の 少なくともつを誘導された部分グラフとして埋め込むこ とができる
が成り立つような数 が存在するか？
& 年昭和年
' これよりもっと一般的な存在定理を証明している．
(%) * +,-年昭和年
' & の結果とは独立に得られている． の値の評価を 与えている．
の定理 構造の数理 定理． 任意の自然数 に対して，
個以上の頂点を持つすべてのグラフ に， か の 少なくともつを誘導された部分グラフとして埋め込むこ とができる
が成り立つような数 が存在する．
帰納法で証明する．
証明を帰納法に乗せるために，もとの主張ではなく，それより さらに一般的でより強い主張を証明する，という前にも何度か出 てきたパターンを用いる.
定理 ．とを正の自然数とする．頂 点の数が !
以上の任意のグラフには， か の少 なくともつを誘導された部分グラフとして埋め込むことがで きる．
の定理 構造の数理 定理 ．とを正の自然数とする．頂 点の数が !
以上の任意のグラフには， か の少 なくともつを誘導された部分グラフとして埋め込むことがで きる．
は，
と書くこともある． 個のものから 個選び出 す選び方の総数をあらわす．
/ 0
0 0
だから， !
/
1 0
0 0
で ある．
(%23+, の定理で，/ と置くと，
系．頂点の数が
以上の任意のグラフには，か
の少なくともつを誘導された部分グラフとして埋め込むこと ができる．
ラムズィー 現象の下限 構造の数理
(%)3+, の定理の証明は次回見ることにする．
上の系から，すべての整数 に対して
頂点の数が 以上の任意のグラフには， か の少なくと もつを誘導された部分グラフとして埋め込むことができる．
となるような が存在することがわかる．そのような のうちの 最小数 これはラムズィー数とよばれている は， が大きくな ると爆発的に増えることが知られている.
定理 昭和 として，任意の
に対し， 個の頂点を持つグラフで も も誘導された部 分グラフとして埋め込めないものが存在する．
ラムズィー 現象の下限 構造の数理 定理 昭和 として，任意の に対し， 個の頂点を持つグラフで も も誘導された部 分グラフとして埋め込めないものが存在する．
証明のスケッチ． 個の頂点を持つグラフは 同型なものも重 複して数えると
個ある． 一方， 個の頂点から 個を 選んで，これらの 個の頂点は全部互いに結ばれている つまり
と同型になっている ものは，
個ある． 個の頂点 から 個を選ぶ選び方は，
個あるから， を含む頂点が
個のグラフの総数は
以下である． 同様に，
を誘導された部分グラフとして含むものも高々同じ個数しか ない． ところが，
が示せるの で，少なくともこの数だけ も も誘導された部分グラフと して埋め込めないものが存在することがわかる．
ラムズィー 構造の数理
明治年
昭和年
!
"
#
$%
&'% !( )の項目から
演習問題 構造の数理
演習問題 初級問題
任意の 個以上の頂点を持つグラフには， か の少なく ともつを誘導された部分グラフとして埋め込むことができる．
が成り立つことが知られています．この主張を，!パーティーの 客" の文脈に翻訳してみてください．
演習問題 中級問題 !パーティーの人の客" の定理で!人"
を !-人" に置き換えた主張は正しくないことを示してください．
参考文献．
45 ピーター・フランクル，代数の閃き，数学セミナー，6-
-7-
