まずは定義から確認していきましょう。

定義

かなり文字量の多い定義で面食らう人もいると思いますが，具体例を考えてみるとイメージしやすいです。

次節や次々節で具体例を取り扱っていますので，分かりにくい方は先にそちらをご覧ください。

この定義には「どんな\(\,k,a_1,\ldots,a_k\,\)に対しても性質\(\,(\ast)\,\)を持つ自然数が本当に存在するのか？」という問題があります。

この存在性が言えないと，ラムゼー数の存在性も保証されません。

そこで，この存在性を保証してくれるのがラムゼーの定理(の一部)です。

ラムゼーの定理については別の記事で解説しようと思っていますので，そちらをお待ちください。

またこのラムゼー数の定義を一般化した広義ラムゼー数もあります。

広義ラムゼー数についてはこの記事では解説しませんので，気になる方は参考図書\([1]\)をご覧ください(もしくは要望が多かった場合，別の記事として解説したいと思います)。

定義を理解したところで，次節からは具体例について一緒に考えていきましょう。

\(R_2(3,3)=6\,\)の証明

具体例として\(\,R_2(3,3)=6\,\)であることを証明していきましょう。

定義にそのまま当てはめて考えれば，次のことを証明することになります。

この問題は下のように，ラフに書き換えられることが多いです。

グラフの点を人として考え，知り合いであるか，知り合いでないかを基準にその間の辺を塗り分けるものとして問題を捉え直したわけですね。

さて問題を確認できたところで，証明を行っていきましょう。

まずは前半部分
「位数\(\,6\,\)の完全グラフ\(\,K_6\,\)の辺を\(\,2\,\)つの色でどのように彩色しても，
全ての辺がどちらか一方の色のみを使って彩色されている位数\(\,3\,\)の完全部分グラフ\(\,K_3\,\)を含む」ことを示していきましょう。

これは\(\,R_2(3,3) \leq 6\,\)であることを示すということです。

色は\(\,2\,\)色なので，ここからはその\(\,2\,\)色を赤・青として考えていきましょう。

辺彩色された\(\,K_6\,\)の適当な点\(\,v\,\)について考えましょう。

このとき\(\,v\,\)から延びる辺は下図のように\(\,5\,\)本あります。

塗る色は赤と青の\(\,2\,\)色しかないので，その\(\,5\,\)本の辺のうち，少なくとも\(\,3\,\)本はどちらかの色で塗られています。

どちらの色でも一般性を失いませんので，とりあえず赤としましょう(例えば下図のようになります)。

この\(\,3\,\)本の先にある点の間のどれかの辺が赤で塗られていた場合，
赤の\(\,K_3\,\)ができますので，この場合については示されました。

反対に\(\,3\,\)本の先にある点の間のどの辺も赤で塗られていない場合，
青の\(\,K_3\,\)ができてしまいますので，この場合についても示されました。

したがって前半部分\(\,R_2(3,3) \leq 6\,\)は示されました。

続いて後半部分
「位数\(\,5\,\)の完全グラフ\(\,K_5\,\)は，辺を\(\,2\,\)つの色でうまく彩色すれば，
全ての辺がどちらか一方の色のみを使って彩色されている位数\(\,3\,\)の完全部分グラフ\(\,K_3\,\)を含まないようにできる」ことを示していきましょう。

こちらは\(\,R_2(3,3)\gt 5\,\)を示すということです。

このことは条件を満たす彩色例を天下り的に与えれば証明は完了しますが，
分かりやすいように自然な発想の流れで彩色例を作成していきたいと思います。

前半部分の証明を見れば，\(\,K_6\,\)が赤か青の\(\,K_3\,\)を持ってしまった要因は
一つの点が赤か青の辺を\(\,3\,\)本以上持ってしまったことですね。

そのため，\(\,K_5\,\)の\(\,1\,\)つの点から延びる辺の数は\(\,4\,\)本なので，
彩色例を作るには\(\,K_5\,\)のどの点も，赤の辺を\(\,2\,\)本，青の辺を\(\,2\,\)本持たせる必要があります。

そのような彩色を考えれば\(\,K_5\,\)の辺を下のように彩色すればよいですね^※。

この塗り方は確かに条件を満たす彩色例になっていますね。

したがって以上より\(\,R_2(3,3)=6\,\)であることは示されました。

※「結局天下り的では？」と思った方向けに補足をすると，ここまでの情報から\(\,K_5\,\)から赤の辺のみを取り出した部分グラフは\(\,2\text{-}\)正則連結グラフ，つまり全ての点を通る閉路になる必要があることが言えます。青の辺のみを取り出した部分グラフについても同様です。

そのため\(\,K_5\,\)の辺集合を互いに素な\(\,2\,\)つの閉路の辺集合(赤と青のグループ)に分けられる必要があります。とりあえず赤の閉路が必要なので，上の図のように赤の閉路を正五角形として描くと，青の閉路も自然に決まってしまいます。

この補足から分かるように\(\,K_5\,\)での反例は上図の辺彩色されたグラフを変形したものに限る(ちゃんとした言葉で言えば同型を除いて一意)であることが分かります。

\(R_3(3,3,3)=17\,\)の証明

もう一つの具体例として\(R_3(3,3,3)=17\,\)であることを証明していきましょう。

これも定義に従って書けば，次のことを示すことになります。

この問題も下のようにラフに書き換えられることが多いです。

どの話題をおしゃべりしているかを，辺をどの色で塗るのかに対応させたということですね。

前節と同様に，
まずは前半部分\(\,R_3(3,3,3)\leq 17\,\)について証明していきましょう。

色は\(\,3\,\)色なので赤・青・緑として考えていきましょう。

辺彩色された\(\,K_{17}\,\)の適当な点\(\,v\,\)について考えます。

点\(\,v\,\)に接続する\(\,16\,\)本の辺のうち，少なくとも\(\,6\,\)本は赤・青・緑のどれかの一つの色で塗られています。

一般性を失わないので，この色を赤とします。

この\(\,6\,\)本の先にある点の間のどれかの辺が赤で塗られていた場合，
赤の\(\,K_3\,\)ができますので，この場合については示されました。

次に\(\,6\,\)本の先にある\(\,6\,\)個の点の間のどの辺も赤で塗られていない場合について考えましょう。

その\(\,6\,\)個の点の間の辺は赤で塗られていないので，青・緑の\(\,2\,\)色で彩色されていると考えられます。

よって前節で示した\(\,R_2(3,3)=6\,\)より，

その\(\,6\,\)点からなる完全グラフの中に，青の\(\,K_3\,\)か緑の\(\,K_3\,\)が含まれることが分かり，この場合についても示されました。

以上より前半部分\(\,R_3(3,3,3)\leq 17\,\)は証明されました。

続いて後半部分\(\,R_3(3,3,3)\gt 16\,\)を証明しましょう。

前節の※と同様に考えれば

\(\,K_{16}\,\)の辺集合を互いに素な\(\,3\,\)つの\(\,5\text{-}\)正則連結グラフの辺集合に分ければ良さそうだと分かります。

※前節の場合と異なり，(特に連結性について)本当に必要条件となるのかは私自身知りません。もし知っている方がいらっしゃったら私に教えてください。

そこで\(\,16\,\)点からなる\(\,5\text{-}\)正則連結グラフであるクレープシュグラフを赤・青・緑のそれぞれの色で彩色したものを考えましょう(下図)。

そしてこれらを重ね合わせることで，下図のように条件を満たす彩色例を作ることができます。

したがって以上より\(\,R_3(3,3,3)=17\,\)であることが示されました。

後半部分\(\,R_3(3,3,3)\gt 16\,\)で作った彩色例とは異なる彩色例がもう一つ存在することが知られています^{参考図書\([3]\)wiki}。

※ここで述べた\(\,2\,\)つの彩色例に限るかは，私自身知りません。参考図書\([4]\)あたりに詳しく書かれていそうなので，暇があれば読んで加筆したいと思います。もしくは誰か教えていただけると幸いです。

また初めて\(\,R(3,3,3)=17\,\)を証明したとされる参考図書\([5]\)では，位数\(\,16\,\)の有限体から立方剰余により彩色例を構成しています。

多少代数学の知識が読めますので，気になる方は読んでみてください(要望が多ければ加筆します)。

今回の記事ではラムゼー数を解説いたしました。

ラムゼー数の有名問題を通して，ラムゼー数の面白さを少しでも感じ取っていただけたら幸いです。

ラムゼーの定理やラムゼー数の応用に関しては，別の記事で解説するつもりなので楽しみに待っていただけると嬉しいです。
\(\to\,\)ラムゼー数の応用についてはこちらの記事ができました。

もし「説明がわかりにくい」などご要望・ご感想がありましたら，
X（旧:Twitter）で#トイカラでつぶやいていただけると，できる限り対応します。

ここまで読んでいただき，ありがとうございました。

• \([1]\) Peter Frankl,秋山仁.”現代組み合わせ論”.初版.共立出版.1987出版.p35-86.
• \([2]\) “Clebsch graph”.Wikipedia.2023-12-13更新.https://en.wikipedia.org/wiki/Clebsch_graph#:~:text=In%20the%20mathematical%20field%20of%20graph%20theory,%20the%20Clebsch%20graph.2024-10-06参照
• \([3]\) “Ramsey’s theorem”.Wikipedia.2024-08-02更新.https://en.wikipedia.org/wiki/Ramsey%27s_theorem.2024-10-06参照
• \([4]\) C. Laywine,J.P. Mayberry.”A Simple Construction Giving the Two Non-isomorphic Triangle-Free 3-Colored \(K_{16}\)’s”.Journal of Combinatorial Theory, Series B, Volume 45, Issue 1,1988出版.p.120-124
• \([5]\) R. E. Greenwood,A. M. Gleason.”Combinatorial relations and chromatic graphs”.Canadian Journal of Mathematics, Volume 7,1955出版.p.1-7