ｎ次元の４色定理について

お世話になります。どなたかご存知の方がいらっしゃいましたら、あるいは、ヒントになるものはこうじゃないか？　ココが間違っている、と提案して下さる方がいらっしゃいましたらご教授下さい。

４色定理というものがこの世の中にありますが、これは飽くまで二次元平面、あるいは球面上の二次元のお話しになると思います。
ここで少し考えたのですが、
・０次元→１色
・１次元→２色
・１次元円環（円周）→３色
・２次元→４色
・トーラス平面（１穴）→７色
・トーラス平面（ｈ穴）→[1/2(7(1+48h)^-2)]色（ヘイウッド予想より）
・３次元→無限（仮に平面に並べた40色の色鉛筆の束に対し、垂直に40色の色鉛筆を載せると1600色の塗り分けができた事になる。これを応用すると無限の色分けが必要となる。）

となるのですが、
１．何故３次元の色分けが無限になるのでしょうか？　
　　上記の色鉛筆の例では実証で行いましたが、理論的にどうだから無限なんだ、というのを導き出したいのです。
２．次元と色分けに相関する式を導き出したいのですが、そのような公式は存在するでしょうか？　

宜しくお願い致します。

No.1 ベストアンサー 回答者： Tacosan 回答日時： 2009/08/16 23:41

確か任意のグラフが 3次元に埋め込めるんじゃなかったかな. つまり, 「任意のグラフを塗るために何色必要か」という問題と等価で,

これは自明に無限である, と.

この回答への補足

少し考えたのですが、
・１次元の開いた直線では白黒の縞模様（２色）で良い。
・１次元の閉じた曲線（円周）では３色が必要。
・１次元円周にさらに棒線を中心に引いた形形（θのような形）には、４色が必要
になってきますね。これをグラフで表した場合、どれだけノードを伸ばせるかという制約がキーになるのかと思います。
同じようにトーラスは穴を空ければ空けた数の分だけノードが伸ばせるので、制約としてのノードを伸ばせる数が多くなっていく。ここら辺にヒントがありそうですが、ちょっとまだよくわかりません。
そして３次元では制約が無い、という形になるでしょうか。
何故３次元では伸ばせるノード数に縛り（制約）が無いのか。
ノードが１次元の場合だから２次元空間に縛りができて３次元には縛りが無い。
同様に、ノードが２次元の場合に３次元空間には縛りができて４次元には縛りが無い。
ノードがｎ次元の場合にはｎ＋１次元空間には縛りができて、ｎ＋２次元には縛りが無い、という事になるのでしょうか。

そもそもノードが２次元という仮定自体が、具体的なイメージとして上手く描けないのですが、ここからちょっと探って行っています。

補足日時：2009/08/17 16:51

この回答へのお礼

回答ありがとうございます。

グラフのノードの拡張が無制約である事をイメージすれば良いのですね。

ちょっと訂正させて頂きますが、
×：
>・３次元→無限（仮に平面に並べた40色の色鉛筆の束に対し、垂直に40色の色鉛筆を載せると1600色の塗り分けができた事になる。これを応用すると無限の色分けが必要となる。）

○：
・３次元→無限（仮に平面に並べた40色の色鉛筆の束に対し、垂直に40色の色鉛筆を載せると「40色」の塗り分けとなる。これを応用すると無限の色分けが必要となる。）

でした・・・。

お礼日時：2009/08/17 00:57

No.2 回答者： Tacosan 回答日時： 2009/08/17 19:32

「１次元円周にさらに棒線を中心に引いた形（θのような形）には、４色が必要」

ってのは本当でしょうか? どのようなグラフを想定しているのかわかりませんが, 「閉路+その上の 2点の間の (辺素な) パス 1本」なら 3色でいけるはずです. これはつまり「2点の間に 3本の辺素なパスがある」グラフと同じですが, 一方の点を取り除くと木になり, 従って 2色で塗れます. 最後に取り除いた 1点を追加するわけですが, これに隣接する 3点はたかだか 2色しかありませんから, 全体が 3色で塗れてしまいます.
あと, 3次元で考えるときには「辺が 1次元であり, 閉路によっても 3次元空間を 2つに分割することは不可能である」ということが効くかもしれません.

この回答への補足

回答への御礼が遅れてしまいました。申し訳ありません。

>「１次元円周にさらに棒線を中心に引いた形（θのような形）には、４色が必要」
θには奇数の交点が二つありますが、一つをＡ、もう一つをＢとすると、点Ａから伸びた三叉の線分（∈みたいなものを想像して頂ければ）で一色塗り、それぞれ三叉の先端から点Ｂへ向かうそれぞれの線に一色ずつ塗り分けると三本の線が同時に点Ｂへ到達したとして、点Ｂを境に三色必要、という考えでいたのです。が、２次元の定理に戻ると、点で接触する国境は塗り分けない、という前提に基づけばTacosanさんの言う通り・・・ってあれ？　どうすればいいのか分からなくなりました。

もうちょっと考えて見ます。

補足日時：2009/09/06 12:05