くろょろぐ

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

構成メモ

論文というか読み物の構成をどうしようか、と考えている。
できる事なら、小学校高学年くらいの子供にも理解できるような内容にしたい。
ちゃんと書こうと思うと、いろいろ下調べする必要がでてきちゃうけど、僕自身がそれほど詳しく調べた事がないテーマを、付け焼き刃で調べて書いても、参考文献程度の情報量にしかならないと思うので、そういうのはむしろ思いきって省いてしまった方がいいのかもしれない。
書く順序についても、下敷きになる部分からだんだんと突っ込んだ内容にする書き方と、逆に最初から面倒くさい内容から入って行って、予備知識的なものを後ろにまとめてしまうという書き方もあると思う。いわば、ボトムアップ方式とトップダウン方式、とでもいうだろうか。何か特定の理論の話をするなら、ボトムアップの方がいいかもしれないけど、そうじゃないならトップダウンでもいいかな、なんて思っている。

続きを読む

つーわけで、四色定理の証明のまとめ

今度こそ、四色定理をエレガントに証明する。
(追記:すんごい自信持って書き直したのに、間違ってる気がしてきました。ていうか間違ってる。なんか(頭が)おかしいなぁ…)
(追記2024-03-26:間違いついでにせっかくだから、今日わかった事書く)
辺3彩色可能な3正則グラフのサイクル頂点行列は、各行の成分の和が0になるように列の符号を変更したあと全行対角化したあとに、何と行の符号をうまく選べば、列の成分の和を全て非0にできる:別の言い方をすれば、対角化されてない部分の下の単位行列を配置して、行の符号をうまく選べば列の成分の和を全て0にできるって事。
なら当然、対角化部分の下、つまり付け加えた単位行列の横に、対角化されなかった部分の逆行列配置できんじゃね?って思うよね。はい。できます。
そうすると、それらを束ねた行列の各行各列ごとに成分の総和を求めて、0でない列と行を全て符号反転すると、なんと、列の和も行の和も全部0にできるっぽいんだよね…。
なぜなのかはわからないけど。ひゃぁ!
(註2024-03-22:全面改稿します)
すでに述べたように、平面グラフの面4彩色は境界線の辺3彩色と等価ですので、辺3彩色の証明をします。
連結で任意の2頂点間に単一のサイクルが存在する3正則グラフ(全ての頂点の次数が3、つまり一つの頂点には丁度3つの辺があるグラフ)が辺3彩色できる事を示します。
なお、グラフは平面でなくてもかまいません。平面でないグラフは、平面状に投影した形で考えます。
また、辺の彩色とは一つの頂点上で同一の色の辺がない事ですから、ループ(辺の両端が同一の頂点)は当然除外しますが、多重辺(同一の2頂点をつなぐ2以上の辺)は許容します。と言っても3正則ですので、頂点数が4以上のグラフでは多重辺はたかだか2本までです。頂点数が2の時のみ、多重辺は3本存在します。
証明は数学的帰納法により、ある辺3彩色可能な3正則グラフが与えられた時に、そのグラフに頂点を2個とその頂点をつなぐ辺が付け加えられたグラフもまた辺3彩色可能である事を示します。

  • サイクル頂点行列
    • サイクル頂点行列の性質
    • サイクル頂点行列を係数行列とする方程式と辺3彩色との関係
    • 係数行列と多変数多項式
  • 3正則グラフに次数2の頂点を付け加える事
    • 次数2の頂点を付け加えた3正則グラフのサイクル頂点行列と辺3彩色
    • 次数2の頂点での辺の色の組み合わせ
  • 辺3彩色可能な3正則グラフに、次数2の頂点を丁度2個付け加えたグラフがやはり辺3彩色可能である事
    • サイクル頂点行列は、各行の成分の和が0になるように調整する。
    • サイクル頂点行列の、頂点を付け加えるサイクルに対応する2行の中から、正則な正方行列をみつける
    • 上で見つけた正方行列を含まない行について、正方行列を含む列の成分を全て0にする
    • 次数2の頂点の列を付け加えます。
  • 補足
続きを読む

サイクル頂点行列による四色定理の証明可能性

結論から言えば、「与えられた連結な3正則グラフが辺3彩色可能、すなわち、次数3の頂点のみからなる連結なグラフが辺3彩色可能ならば、そのグラフにさら次数2の頂点を丁度2個付け加えた連結なグラフもまた辺3彩色可能である」事と、四色定理は同値である。

続きを読む

方針転換

四色問題を考えるにあたって、頂点辺行列がそれなりに使える事を以前書いた。しかし頂点辺行列は位数2の体上で考える事ができるというメリットがある反面、問題を解くのに三つの連立方程式を同時に解かなければならないというデメリットがある。
四色問題を考える際には辺3彩色問題を解けばいいのだが、それを位数2の体の元で表すのはもともと無理があるわけで、一時、位数3や位数4の体を使う事も一応考えた。が、例外の扱いが面倒で、一番面倒のない位数2を選んだというのが実情である。

続きを読む

四色問題はエレガントに証明できるか(または、なぜエレガントに証明できないのか)?

ここ一年くらい、そんな事ばかり考えてるわけだけども。
3正則グラフからのアプローチは一旦少し諦めて、ケンプの証明にここまでの知見を活かしてみる事を考える。

続きを読む

多面体定理

凸多面体に於いて、頂点の数をV、辺の数をE、面の数をF、とすると、
V-E+F=2
という関係が成り立つ。
この関係をオイラーの多面体公式、またはオイラーの多面体定理というんだそう。平面グラフに於いても、グラフ全体を取り囲んでいる外側の領域も面の一つと考えれば、同じ関係が成り立つ。
今、頂点の数がV、辺の数がEのグラフGに対し、位数2の体上のV行E列の行列Mを、各頂点を行に、各辺を列に対応させ、頂点が辺の端点となっている時、その頂点と辺に対応する成分を1(但し、ループの辺の端点になっている場合は例外的に0とする)とし、それ以外は0である時、行列MをグラフGの頂点辺行列と呼ぶ事にする。
Mは、ともに位数2の体上の、E次元ベクトル空間からV次元ベクトル空間への準同型写像であり、したがって核ker(M)が定義される。ker(M)の元は、G上の全てのサイクルとそれら全ての組み合わせからなる、E次元ベクトル空間の部分空間となる。
Gが球面グラフ(多面体)であれば、ker(M)の次元dim(ker(M))は、Gの面の数をFとすると、(F-1)に一致する。なぜならば、面はGのサイクルであり、一つの面は残りの全ての面の和で表されるが、その場合を除けば他の面の和で表す事ができず、その一方でG上の任意のサイクルの組は、これら(F-1)個の面の和でいかようにも表す事ができる。
これを、球面グラフに限らず、一般のグラフに拡張できる事に気付いた。すなわち、一般のグラフGに於いて、コンポーネントの数をC、頂点の数をV、辺の数をE、頂点辺行列をM、とするとき、
dim(ker(M))=C-V+E
が成り立つ。
証明は、新しいサイクルができる場合に核の次元が一つ増え、決して減らない事に注意すれば、グラフから辺を一つずつ取り除いて頂点のみとし、今度はその逆順に辺を付け加えていって、コンポーネントの数と次元の変化を比較すれば良い。これはGに多重辺やループがあっても成立する。