くろょろぐ

はてダからはてブロに移行済み

辺3彩色雑多メモ

だらだらメモです。
いままでの考え方の過ちに気付き、考え方を少し修正したら大幅に進展したので、そのメモです。
日本語がおかしいです。
前回、逆行列を使って直接彩色を求めようとしたが、これは最近の考察であまりうまく行かない事がわかった。
少し前提条件をきちんとまとめようと考えたところで、今まで成分が0にならない事にこだわり過ぎていたために代数的構造に目が向いていなかった事に気付いたので、直交補空間についてもっと真面目に考える事にした。
そのうえで、帰納法の前提となるグラフの直交補空間に含まれていて、一部条件を付け加えたグラフの直交補空間には含まれないベクトルが、証明に必要なベクトルで、これの存在をきちんと示す事ができれば、証明は終わりである。直交補空間を求めるので、逆行列ではなく転置行列が鍵となる。
問題は、どの基底を使って直交補空間を求めるかだが、ここで、前回も前々回もこの部分をきちんと条件付けできていなかった。

まず前回同様、証明したいグラフから、辺を1つとその両端の頂点を取り除いたグラフ(頂点が2つ、面が1つ減る)を考え、ここで帰納法の前提を使う事を考える。辺が取り除かれてできる新しい面を最外周とし、頂点が取り除かれた面の頂点に関連付けられた係数の合計が、前提となる彩色ではともに0となるが、これがともに非0となるような彩色ができれば、帰納法が成立する。

ここで、単純に3正則グラフに於ける辺3彩色の原理から、一方が0ならもう一方は必ず0に、一方が非0ならもう一方も非0というになる事がわかっている。実はここをまだ良く理解できていなかった。

二つ同時に0や非0にする事ばかり考えていたので、変数が固定できなかったのだ。

そこで、この関係を、もう少し理解しやすい形に書き換える事にした。すなわち、二つの和が0なら差は非0、差が0なら和は非0、言い換えると自乗の差は0、と言い換えた。

これにより、変数の一方は必ず0になるので、これを基底に組み込む事で、前提となるグラフはきれいに正方行列となり、残ったもう一方はそれらの一次結合で表される事になった。

これを得た瞬間、当初考えていた、非0の多項式の積の形になっている事に気付いた。具体的な数値を全く当てはめる事なく、解の存在がこれで示された。

…はい、これで本当に四色定理をエレガントに証明できるはずです。

(追記)
質問にも描きましたが、xy(x-y)(x+y)の形の他に多項式の積を0にする因数が無数にあるとすれば、それがおそらく不可避集合の多項式環上の表現となるのではないかという気がします。もしそうなら、結局エレガントには証明できないという事になってしまうのですが…。もしそうなら、数もおそらく3の4乗くらいはあると思われるので、あながちその予想は間違っていないのかもしれません。

(追記)
結論から言うと、このやり方は証明には全く不向きで、そもそも不要でした:代わりに、サイクル頂点行列の性質だけで証明が完結できる事が理解できました。具体的な話は追って記事にします。

(追記)
辺3彩色できるという事だけから、サイクル頂点行列の正則性を示さなければならなくなりました。どうやら帰納法で示すのは現実的ではありません。ここで、4正則化と何らかの関連があるらしい事が見えてきましたが、具体的にどう関連するのか、それは果たして有用なのか、は、わかりません。