【１】グラハムの問題

すべての頂点同士を２種類の異なる色のついた線で結んだｎ次元超立方体（頂点数２^n）を考える

この時、ｎがある数Ｎ以上であれば、同一2次元平面上にすべての辺の色が同じである完全グラフK4が存在するか？

すなわち、対角線を持つ平面４角形が同じ色の線になっている

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

ｎ次元の超立方体を考える。

頂点数２^n

辺数２^n-1(２^n-１）

すべての辺を赤か白で彩色する

同一平面上の正方形を考える。

ｎ＝２のとき塗分け可能

ｎ＝３のとき塗分け可能

十分大きなｎではどのように塗り分けてもある正方形は一色になってしまう。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

ラムゼー理論の問題に登場した大きい数の世界チャンピオンである。

しかし、この話にはオチがあり、グラハム数はスキューズ数のように上限だということを思い出してほしい。

ラムゼー理論のエキスパートたちは、その答えは6だとうすうす感じているのだそうだ。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

　ｎ次元超立方体の頂点数は２^n，ファセット数は２ｎあります．ｋ次元面数は

　　（ｎ，ｋ）２^n-k

となります．

　すなわち，

　　辺数はｎ・２^n-1

　　正方形面数はｎ（ｎ−１）・２^n-3

［Ｑ］この図形のすべての辺を赤線か青線で結ぶとき，この図形には４点をつなぐ線がすべて赤か，すべて青の正方形ができるようにするためには，ｎはいくつ以上であればよいか？

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

［Ａ］ｎ＝６　　（グラハム）

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝