グラハム問題

ウィキペディア小見出し辞書

グラハム問題

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/08/04 13:50 UTC 版)

「グラハム数」の記事における「グラハム問題」の解説

この数は1970年のロナルド・グラハムとブルース・リー・ロスチャイルドによる「グラハムの定理」 「 n 次元超立方体の 2n 個の頂点のそれぞれを互いに全て線で結ぶ。次に2つの色を用いて連結した線をいずれかの色に塗り分ける。このとき n が十分大きければ、どんな塗り方をしても、同一平面上にある四点でそれらを結ぶ線が全て同一の色であるものが存在する。 」 に関係する。つまり、n が十分大きければというが、 「 n がいくらより大きければ、この関係は常に成立するか 」 ということである。これがグラハム問題である。グラハムの定理より、解の存在は確かだが、具体的な値は現在にいたるまで得られていない。 しかし、この関係がグラハム数以上の n について成り立つことがグラハム自身によって証明された。つまり、解はグラハム数以下である。 ただし、グラハムらは実際にはこの数を論文では発表しておらず、翌1971年にグラハム数より小さなグラハム問題の解の上限として、小グラハム数という数を発表した。その後、マーティン・ガードナーが1977年にサイエンティフィック・アメリカンでグラハム数を紹介したことによってこの数は広く知られるようになった。 解の上限はのち2014年にミハイル・ラブロフらによってさらに小さい数が示された。 一方、この問題の解の下限（つまりこの数より小さい数では成り立たないことを示した数）としては、グラハムとロスチャイルドは1971年の小グラハム数を示したものと同じ論文中で 6 を与えた。ガードナーは1989年に著書の中でラムゼー理論の専門家はこの問題の解を 6 と考えていると紹介し、これが広く信じられてきたが、2003年にジェフ・エクスーがより良い下限として 11 を、2008年にはジェローム・バークレーが 13 を与えた。