グラハム・ロスチャイルドの定理

数学において、グラハム・ロスチャイルドの定理は、ラムゼー理論を単語と組み合わせ立方体の組み合わせ論に適用する定理です。これは、1971年にその証明を発表したロナルド・グラハムとブルース・リー・ロスチャイルドにちなんで名付けられました。 ^{[ 1 ]} 1972年にグラハム、ロスチャイルド、クラウス・リープの研究により、構造ラムゼー理論の基礎の一部となりました。^{[ 2 ]}グラハム・ロスチャイルドの定理の特殊なケースは、グラハム数の定義を促します。この数は、サイエンティフィック・アメリカン誌でマーティン・ガードナーによって広められ^{[ 3 ]} 、数学的証明に登場した最大の数としてギネス世界記録に掲載されています。^{[ 4 ]}

この定理は、すべて同じ長さの文字列の集合に関するものである。${\displaystyle n}$組み合わせキューブは、文字列の一部の位置にアルファベットの固定文字が含まれるように制約し、他の位置のペアが互いに等しいか、グループ作用によって互いに関連付けられるように制約することによって決定される文字列の部分集合です。この決定は、ラベル付きパラメータワード、固定文字が含まれるように制約されていない位置にワイルドカード文字を持つ文字列、およびどのワイルドカード文字が等しいか、グループ作用によって関連付けられる必要があるかを記述する追加のラベルによって、より形式的に指定できます。組み合わせキューブの次元は、これらのワイルドカード文字に対して行うことができる自由な選択の数です。次元が 1 の組み合わせキューブは、組み合わせ線と呼ばれます。^{[ 4 ]}

例えば、三目並べのゲームでは、三目並べ盤の9つのマスは、3つの記号からなるアルファベット{1,2,3}（マスのデカルト座標）上の長さ2の文字列で指定でき、3つのマスからなる勝利ラインは組み合わせラインを形成します。水平ラインは、${\displaystyle y}$-座標（長さ2の文字列の2番目の位置）と${\displaystyle x}$座標は自由に選択でき、垂直線は固定することで得られます。${\displaystyle x}$-調整して${\displaystyle y}$-座標は自由に選択できます。三目並べ盤の2つの対角線は、2つのワイルドカード文字を含むパラメータワードで指定できます。これらのワイルドカード文字は、等しいように制約されるか（主対角線の場合）、1と3の文字を交換するグループアクションによって関連付けられるように制約されます（反対対角線の場合）。^{[ 5 ]}

次元のすべての組み合わせ立方体の集合${\displaystyle d}$長さの文字列の場合${\displaystyle n}$アルファベット以上${\displaystyle A}$グループ活動と共に${\displaystyle G}$、は、${\displaystyle [A,G]{\tbinom {n}{d}}}$組み合わせキューブのサブキューブは、より大きな組み合わせキューブの文字列セットの部分集合を形成する、より小さな次元の別の組み合わせキューブです。組み合わせキューブのサブキューブは、あるパラメータワードの記号を別のパラメータワードのワイルドカードに置き換えることによって得られる、パラメータワードに対する自然な合成アクションによっても記述できます。^{[ 4 ]}

上記の表記法では、グラハム・ロスチャイルドの定理はアルファベットをパラメータとして取ります。${\displaystyle A}$集団行動${\displaystyle G}$色数有限${\displaystyle r}$、そして組み合わせキューブの2次元${\displaystyle m}$そして${\displaystyle k}$と${\displaystyle m>k}$。それは、あらゆる組み合わせについて、${\displaystyle A}$、 ${\displaystyle G}$、${\displaystyle r}$、${\displaystyle m}$、 そして${\displaystyle k}$文字列の長さが存在する${\displaystyle n\geq m}$つまり、各組み合わせキューブが${\displaystyle [A,G]{\tbinom {n}{k}}}$1つが割り当てられる${\displaystyle r}$色の場合、組み合わせキューブが存在します${\displaystyle [A,G]{\tbinom {n}{m}}}$そのすべて${\displaystyle k}$次元サブキューブには同じ色が割り当てられます。^{[ 5 ]}

グラハム・ロスチャイルド定理の無限版も知られている。^{[ 6 ]}

グラハム・ロスチャイルド定理の特殊なケース${\displaystyle m=1}$、${\displaystyle k=0}$、自明な群作用はヘイルズ・ジュエットの定理であり、与えられたアルファベット上の十分長いすべての文字列が着色されている場合、単色の組み合わせ線が存在すると述べている。^{[ 5 ]}

グラハム数は、グラハム・ロスチャイルド定理の上限であり、${\displaystyle |A|=2}$、${\displaystyle r=2}$、${\displaystyle m=2}$、${\displaystyle k=1}$、そして非自明な群作用。これらのパラメータの場合、長さの文字列の集合は${\displaystyle n}$バイナリアルファベット上で頂点を記述する${\displaystyle n}$次元超立方体であり、その任意の2つが組み合わせ線を形成する。すべての組み合わせ線の集合は、頂点上の完全グラフの辺として記述できる。定理は、十分高い次元に対して、${\displaystyle n}$完全グラフのこの辺の集合に2色が割り当てられる場合、単色組み合わせ平面が存在する。これは、共通の幾何学的平面に属し、6つの辺すべてに同じ色が割り当てられている4つの超立方体の頂点の集合である。グラハム数はこの数の上限である。${\displaystyle n}$繰り返し指数計算を用いて計算したもので、最小値よりもかなり大きいと考えられている。${\displaystyle n}$グラハム・ロスチャイルド定理の記述が真となる場合。^{[ 4 ]}