構造の数理
年月 日 第 回目の講義
渕野 昌
神戸大学大学院 システム情報学研究科
の定理
神戸大学 年度後期の講義
!
定理． 昭和 昭和 年 任意の自然数 に対して，
個以上の頂点を持つすべてのグラフ に， か の 少なくともつを誘導された部分グラフとして埋め込むこ とができる
が成り立つような数 が存在する．
上のような のうち最小のものを， と書いて， に対す る 数呼ぶことにしたのだった．
この定理は次のように言い換えることもできる
前回の講義で，次が成り立つことが証明できた
定理． 昭和 ! "#$%&' ( 昭和年 任意の自然数 に対して，
個以上の頂点を持つすべてのグラフ に， か の 少なくともつを誘導された部分グラフとして埋め込むこ とができる
が成り立つような数 が存在する．
この定理は次のように言い換えることもできる 定理． !"#)*&' の定理の言い換え 任意の自然数 に対して，
任意の と の辺の二色の色分け に対し， の 個の頂点を持つ完全部分グラフで，すべての辺が で の色分けで 一色で塗られているようなものが存在する が成り立つような数 が存在する．
任意の と の辺の二色の色分け に対し， の 個の頂点を持つ完全部分グラフで，すべての辺が で の色分けで 一色で塗られているようなものが存在する が成り立つような数 が存在する．
たとえば， + のときは， +,として
定理． !"#)*&' の定理の言い換え 任意の自然数 に対して，
任意の と の辺の二色の色分け に対し， の 個の頂点を持つ完全部分グラフで，すべての辺が で の色分けで 一色で塗られているようなものが存在する が成り立つような数 が存在する．
たとえば， + のときは， +,として
任意の と の辺の二色の色分け に対し， の 個の頂点を持つ完全部分グラフで，すべての辺が で の色分けで 一色で塗られているようなものが存在する が成り立つような数 が存在する．
たとえば， + のときは， +,として
定理． !"#)*&' の定理の言い換え 任意の自然数 に対して，
任意の と の辺の色の色分け に対し， の 個の頂点を持つ完全部分グラフで，すべての辺が で の色分けで 一色で塗られているようなものが存在する が成り立つような数 が存在する．
上の定理が !"#)*&' の定理の言い換えになって いることを見るには， の辺の色の色分け たとえば赤と青 のうちのつの色 たとえば青 の辺だけを持つようなグラフを考 えることにして，このグラフに !"#)*&' の定理を 応用することを考えればよい．たとえば
上の形の言い換えをすると，-色.を
- 色. で置き換えた形の一般 化が自然に考えられるようになる．
任意の と の辺の色の色分け に対し， の 個の頂点を持つ完全部分グラフで，すべての辺が で の色分けで 一色で塗られているようなものが存在する が成り立つような数 が存在する．
上の定理が !"#)*&' の定理の言い換えになって いることを見るには， の辺の色の色分け たとえば赤と青 のうちのつの色 たとえば青 の辺だけを持つようなグラフを考 えることにして，このグラフに !"#)*&' の定理を 応用することを考えればよい．たとえば
上の形の言い換えをすると，-色.を
- 色. で置き換えた形の一般 化が自然に考えられるようになる．
定理． の定理! 昭和 任意の正の自然数 ! に対して，
/ 任意の と の辺の 色の色分け に対し， の 個の頂点を持つ完全部分グラフで，すべての辺が で の色分けで 一色で塗られているようなものが存在する が成り立つような数 が存在する．
証明． 正の自然数 に関する帰納法で，
// 「すべての正の自然数 に対して，/ が成りつような が存在する」
ことを示す．
// が成り立つときには，そこでの数 のうち最小なものが とれるが，これを， とあらわすことにする．
帰納法の初め +のときには，
+ とすればよい．
「すべての正の自然数 に対して， が成りつような が存在する」
ことを示す．
// が成り立つときには，そこでの数 のうち最小なものが とれるが，これを， とあらわすことにする．
帰納法の初め +のときには， + とすればよい．
+ のときには，
+ とすればよい．
は 数
帰納法のステップ として，すべての ¼ に対して，
// が成り立つとき，正の自然数 に対し，「 +
と すると， は， と に対する / を満たす」 ことを示せば よい．
これにより，
が成り立つことも，示せたこと になる．
帰納法のステップ として，すべての ¼ に対して，
// が成り立つとき，正の自然数 に対し，「 + とすると， は， と に対する を満たす」 ことを示せば よい．
これにより，
が成り立つことも，示せた ことになる．
+
個以上の頂点を持つ完全グラフ の辺の任意の 色の色分け を考える．
で使った色を
!
!!
として，
!!
をすべて同じ色
だと思ったときの， の二色への色分け ¼ だと思うと， のと りかたから， のサイズが の完全部分グラフ ¼ で，辺が 一色で塗られたものがとれる．¼ が で塗られていれば，これ は，色分け で一色で塗られた完全部分グラフでもあるからよい．
もし ¼ が 一色で塗られていれば，色分け に関して ¼ は
色で色分けされた
個の頂点を持つグラフだから，
サイズが の部分グラフで，辺の色が一色のものがとれるから，
この場合にもよい．
大正
! 平成"#$
"#$ は，いくつもの重要な数学の研究結果を残したが，多く の共著者を持っていたことでも知られている 0生涯に 少なくと も (人の数学者と共著論文を書いている．"#$ は，天才的な 数学者が個人プレーで行なうことが多かったこれまでの数学の研 究スタイルに加えて，国際的な共同研究での研究，という新しい 研究スタイルを確立することにも大きな貢献をした，とも言える だろう．
