利用者:Flightbridge/sandbox/グラハム数

背景

同一平面上の四頂点で各辺の色がすべて等しい完全部分グラフ（下）をもつ二色の立方体（上）の例。 Example of a 2-colored 3-dimensional cube containing one single-coloured 4-vertex coplanar complete subgraph. The subgraph is shown below the cube. Note that this cube would contain no such subgraph if, for example, the bottom edge in the present subgraph were replaced by a blue edge – thus proving by counterexample that N* > 3.

グラハム数は、ラムゼー理論における次の問題と繋がっている。

「

n 次元超立方体の 2n 個の頂点を互いに辺で結ぶ。次に2つの色を用いて全ての辺をいずれかの色に塗り分ける。 このとき、同一平面上にある四頂点でそれらを結ぶ辺が全て同一の色であるものが、どんな塗り方をしても存在する最小の n はいくらか。

」

1971年にロナルド・グラハムとブルース・リー・ロスチャイルドはこの問題が解を持つことを証明し、その解 N* の上限と下限をそれぞれ 6 ≤ N* ≤ N であるとした。ここで $N$ は関数 F (x) = 2 ￪^x 3 （クヌースの矢印表記を参照）の 7 回反復合成によって

$N=F^{7}(12)=F(F(F(F(F(F(F(12)))))))$

と表される巨大な数（小グラハム数）である。グラハムとロスチャイルドはこの上限 N が

$4\rightarrow 2\rightarrow 8\rightarrow 2<N<2\rightarrow 3\rightarrow 9\rightarrow 2$　（コンウェイのチェーン表記を参照）

の間にあると見積もった。後に上限値は2014年にヘールズ・ジューエットの定理により N' = 2 ￪³ 6 （ペンテーションを参照）まで改善され、下限値は2003年に Geoffrey Exoo により 11 まで、2008年にジェローム・バークレーにより 13 まで改善された。即ち現時点での解 N* の最良の見積もりは 13 ≤ N* ≤ N' である。

グラハム数 G は上の N よりも遥かに巨大な数であり、関数 f (x) = 3 ￪^x 3 の 64 回反復合成によって

$G=f^{64}(4)=\underbrace {f(f(\cdots f(} _{64}~4~\underbrace {)\cdots ))} _{64}$

と表される。ただしグラハムらはこの値を発表しておらず、後の1977年9月にマーティン・ガードナーがサイエンティフィック・アメリカンにおいて「グラハム数」の名で発表した。