利用者:Flightbridge/sandbox/グラハム数
表示
< 利用者:Flightbridge | sandbox
背景
[編集]![](http://upload.wikimedia.org/wikipedia/commons/thumb/6/60/GrahamCube.svg/220px-GrahamCube.svg.png)
グラハム数は、ラムゼー理論における次の問題と繋がっている。
「 |
n 次元超立方体の 2n 個の頂点を互いに辺で結ぶ。次に2つの色を用いて全ての辺をいずれかの色に塗り分ける。 |
」 |
1971年にロナルド・グラハムとブルース・リー・ロスチャイルドはこの問題が解を持つことを証明し、その解 N* の上限と下限をそれぞれ 6 ≤ N* ≤ N であるとした。ここで は関数 F (x) = 2 ↑x 3 (クヌースの矢印表記を参照)の 7 回反復合成によって
と表される巨大な数(小グラハム数)である。グラハムとロスチャイルドはこの上限 N が
- (コンウェイのチェーン表記を参照)
の間にあると見積もった[1]。後に上限値は2014年にヘールズ・ジューエットの定理により N' = 2 ↑3 6 (ペンテーションを参照)まで改善され[2]、下限値は2003年に Geoffrey Exoo により 11 まで[3]、2008年にジェローム・バークレーにより 13 まで改善された[4]。即ち現時点での解 N* の最良の見積もりは 13 ≤ N* ≤ N' である。
グラハム数 G は上の N よりも遥かに巨大な数であり、関数 f (x) = 3 ↑x 3 の 64 回反復合成によって
と表される。ただしグラハムらはこの値を発表しておらず、後の1977年9月にマーティン・ガードナーがサイエンティフィック・アメリカンにおいて「グラハム数」の名で発表した[5]。
- ^ “Graham's number records”. Iteror.org. 2014年4月9日閲覧。
- ^ Lavrov, Mikhail; Lee, Mitchell; Mackey, John (2014). “Improved upper and lower bounds on a geometric Ramsey problem”. European Journal of Combinatorics 42: 135-144. doi:10.1016/j.ejc.2014.06.003.
- ^ Exoo, Geoffrey (2003). “A Euclidean Ramsey Problem”. Discrete & Computational Geometry 29 (2): 223–227. doi:10.1007/s00454-002-0780-5. ここでの「グラハム数」はグラハムとロスチャイルドによる上限値 N のことであり、マーティン・ガードナーによる G ではない。
- ^ Barkley, Jerome (2008). "Improved lower bound on an Euclidean Ramsey problem". arXiv:0811.1055 [math.CO]。
- ^ Martin Gardner (1977) "In which joining sets of points leads into diverse (and diverting) paths". Scientific American, November 1977