Hadwiger予想は正しい
タイトルを変えました。変えましたが、まとまっていないです。Hadwiger予想の証明を近いうちに書きたいと思います。
たぶん正多面体上のグラフマイナーで砂時計みたいに半分でわって頂点でくっつけたもの
なんで？
層を移動する推進力を得るため。
ポエムみたいになってきた。
追記:
正多面体の頂点と辺のグラフはプラトン・グラフ（Platonic graph）っていうのか。
操作として掛け算をリンクと定義するとNn,Nm(n<=m)上にa,bがあるとする、a,bをN1層まで展開する。その中の各層で共通した点が接続点になるみたいな感じかな。
a * b = a + b - (a ∩ b)
a ∩ b部分が重複したグラフで最小カットのもとになる。これが2部グラフになってる気もする。
(a ∩ b)がaに一致するとき、aはbに含まれてるね。
足し算はNn層に限定された処理で、Nn層にあるn+1点がKn+1を構成するとNn+1層に点を作ろうとする。なのでN0層なら任意
辺上にもう一点を作るのはN0,N2層の点の直線状にあるN1層に波及して起こる操作。
N0上の点OとN4上の任意の点をp ∈ Pとして開区間(O,N4)を満たす操作(開区間なので森)行い続けるのが4色問題だな。
マイナーていうのをNn上の開点(でいいのかな?直接は接続不可能な点でこれを構成する下層ではリンク可能)とおもうとHadwiger予想は正しい。
彩色数をもとにしたグラフの性質(1)のイメージ
なんでこんなことをおもいついたのかわからないけど、吐き出してみる
彩色数を基にした層Nnがあるとする。
点を作る -> N1層に点を作成する(K1)。
辺を作る -> N1層の2点を接続し、N2層に点(K2)を作成し、N1層の点は消す
面を作る -> N2層の3点がK3を構成したら、N3に点を作成し、N2層の3点は消す。
立体を作る -> N3層の4点がK4を構成したら、N4層に点を作成し、N3層の4点を消す。
K4とK3の点連結 -> N1層の点を作ってN3層とN4層の点にリンクをつくる。K1_2でK1側をN1層に置く
K4とK3の辺連結 -> N2層の点を作ってN3層とN4層の点にリンクをつくる。K1_2でK1側をN2層に置く
こんな感じで考えると4色定理はN4上の複数の点がN4上でのリンクはなく、N3層以下で蠢く感じに思えてくる。
彩色数を性質とするとマイナーに閉じた操作もイメージしやすい。
K3,3が平面グラフの禁止マイナーな理由の想像
平面に落ちないからってことなんだけど
一旦マイナーとか平面はおいておくとして
彩色数で分割した多層ネットワークを考える
1層にはK1、2層にはK2、3層にはK3を頂点として配置することとする。
1層目に辺ができると2層目に頂点を作って接続する(上層にジャンプするイメージ)。同様に2層目が3連結になると3層目に頂点を作成し、接続するという感じで行うとき、K2_3グラフは作れるけど、K3_3グラフはねじれが起きてるんじゃないかとおもう。(イメージとしては3層から下層に向かって穴が開く、もしくはK6に突き抜けようとして5層にぶち当たるイメージ)
同じようにK3_4は作れるけどK4_4は禁止マイナーみないなものがあるかもしれない。
まあ想像で全然現実味がない。
K3_3は結局K4になるかK2_2になるしかないからだ。平面はK4マイナーなのでK4にはなれないし、K2_2になると自己ループで消えてしまう。ちなみに単独のK3を2つつなぐと一つになる。
追記:
基数層は面がせりあがって、偶数層は点がせりあがる立体のイメージ。
むしろ2部グラフはKn,mとするとmin(n,m) * 2 = sとして、P(Ks)のサブグラフに含まれるとかがありそう。
むしろ2部グラフはKn,mとするとKnとK_n+mの1点をつなぐサブグラフに含まれるとかありそう。
追記2:
K3_3は結局K4になるかK2_2になるしかないからだ。平面はK4マイナーなのでK4にはなれない。K2_2の点は自己ループで消えてしまう。
彩色数、グラフマイナーとは
イメージ的には電子部品のようなもので3次以上の完全グラフをマイナーとして持つネットワークが内部回路、内部回路も同様に入れ子にできる。その内部ネットワークを十分に機能させるために彩色数分のソケットが必要。
色を示す頂点を用意し、一つの部品のソケットには色の重複がないように割り当てるように、全てのソケットと繋ぐときの最小頂点数をみつけるのが彩色問題。
追記:
まとめるとグラフGの彩色数をP(G)とするとGを二つのグラフGa,Gbに分割したとき、P(G) = max(P(Ga), P(Gb))P(G) ≧ max(P(Ga), P(Gb))にたぶんなる(これはそんな定理もあった気がする)。
P(G) > max(P(Ga), P(Gb))の時は多分、P(G)=nとすると彩色数を決めるKnのグラフマイナーをぶった切ってる。
Ga, Gbはさらに分割可能なので、上記の式を帰納法で解いた結果はHadwiger予想とおそらく同じ。
min側の意味もGa,Gbの連結度的なものになりそう。
彩色組み合わせの数もKnから任意の辺に頂点を追加する操作を行う操作回数をoとすると彩色組み合わせはP(Kn)*(P(G)-2)^oになる筈だし、マイナーに閉じた操作での彩色組み合わせの数の変化はおそらく示せそう。
Hadwiger予想
Hadwiger予想近づいた気がしてきた。
その他のグラフの彩色数に関する未解決問題としては、Hadwiger予想(en)がある。これは、彩色数 k のグラフはマイナーとして頂点 k 個の完全グラフを含む、という予想である。
平面グラフの彩色においては任意の面が3彩色可能なときとしたけど、平面じゃなければ、接続可能な点は頂点数分あるから、そうなりそう。
彩色数nのグラフGnに対し、頂点を1つ追加してGn+1にするには、Knグラフマイナーのn色にn本辺を引くのが、手順になるよな。
追記:
グラフを特徴づけるHadwiger予想と今回の面の彩色数の関係が理解できてきた気がした。
K3のグラフマイナーが面に相当し、これを頂点として4彩色のグラフを構成しているのが平面グラフだ。たぶん。
グラフ全体に処理を施していくことで面がつくれる。
縮退数kのグラフがのマイナーを持ってないかなー
彩色問題
四色定理のことをたまに考えるんだけど、平面グラフにおいて、任意の1面に対し、その面を構成する閉路の頂点を3彩色し、且つ、グラフ全体を4彩色する塗り方があるってことに気付いた。
多分、正しい。
平面グラフGにより構成される面Fの内、任意の面fを構成する閉路をCfとする。
このCfを3彩色し、Gを4彩色する方法が必ず存在する。
Gに点uを加えて、G'を作るとき、uは必ずある面f内に配置される(グラフの外も面と考える)。
この時fを構成する閉路Cfが必ず4色必要とされる場合、uからCf上の4色の点に辺を作成したG'は必ず5色必要となり、四色定理に反する。
追記:
帰納法でもできそう。GにK4が含まれる場合には成立する。
たぶんGには、K4グラフマイナーが含まれる場合に成立する。かな? グラフマイナーよくわかってない。
そしてK4グラフマイナーを含まない場合に、CfおよびGが3彩色可能になりそう。なのかな? まだわからない。
追記2:
Gnが3彩色できる場合、3色の閉路で2色の頂点のみに接続する場合か、2色の閉路内に1頂点を加えた場合なので、3彩色のグラフの列挙とか、判定式もできそう。。
