■n次元超立方体と同色の正方形(その4)

【1】グラハムの問題

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

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

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

===================================

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

頂点数2^n

辺数2^n-1(2^n-1)

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

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

n=2のとき塗分け可能

n=3のとき塗分け可能

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

===================================

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

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

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

===================================

 n次元超立方体の頂点数は2^n,ファセット数は2nあります.k次元面数は

  (n,k)2^n-k

となります.

 すなわち,

  辺数はn・2^n-1

  正方形面数はn(n−1)・2^n-3

[Q]この図形のすべての辺を赤線か青線で結ぶとき,この図形には4点をつなぐ線がすべて赤か,すべて青の正方形ができるようにするためには,nはいくつ以上であればよいか?

===================================

[A]n=6  (グラハム)

===================================