解説１

頂点の集合を V として、m個の頂点が含まれているものとします。V = {1, 2, 3, 4, …, m}

V の中から異なる３つの頂点を選び出し、i, j, k とします。次の３つのグラフに対応する論理式をつくります。

　( e_i,j ∨ ¬e_i,k ∨ ¬e_j,k)　∧　 (¬e_i,j ∨  e_i,k ∨ ¬e_j,k)　∧　 (¬e_i,j ∨ ¬e_i,k ∨  e_j,k)

これを、V から異なる３頂点を選ぶすべての組合せで行い、それらすべての論理積を R とします。

R は、m(m-1)(m-2)/3! * 3 個の項の論理積として定義されたことになります。

V の異なる２頂点 x, y を結ぶ辺 e_x,y に真理値 1 を代入してみます。

V から選ぶ３頂点の組を４種に分類します。

1. x と y の両方を含んでいる
2. x を含み y を含んでいない
3. x を含まず y を含んでいる
4. x と y の両方を含んでいない

1の組からつくられるのを R^xy とし、2の組からつくられるのを R^x 、3の組からつくられるのを R^y 、4の組からつくられるのを R' とします。次の恒真式が成立します。

　tautology　R　⇔　R^xy∧R^x∧R^y∧R'

R^xy の中の３頂点の組 {x, y, z} を取り出します。

　( e_x,y ∨ ¬e_x,z ∨ ¬e_y,z)　∧　 (¬e_x,y ∨  e_x,z ∨ ¬e_y,z)　∧　 (¬e_x,y ∨ ¬e_x,z ∨  e_y,z)

e_x,y に真理値 1 を代入します。

　(e_x,z ∨ ¬e_y,z) ∧ (¬e_x,z ∨ e_y,z)

　(e_x,z ∧ e_y,z) ∨ (¬e_x,z ∧ ¬e_y,z)

さらに次のように書いても同値です。

　e_x,z ⇔ e_y,z

例えば x = m-1, y = m と仮定すると、R^xy の e_x,y に真理値 1 を代入したものは次のようになります。

　(e_x,1 ⇔ e_y,1)∧(e_x,2 ⇔ e_y,2)∧(e_x,3 ⇔ e_y,3)∧…∧(e_x,m-2 ⇔ e_y,m-2)

ゆえに e_x,y∧R を次のように表すことができます。

　e_x,y∧(e_x,1 ⇔ e_y,1)∧(e_x,2 ⇔ e_y,2)∧(e_x,3 ⇔ e_y,3)∧…∧(e_x,m-2 ⇔ e_y,m-2)∧R^x∧R^y∧R'

R^x か R^y のどちらか片方はなくても同値になることがわかります。

　e_x,y∧(e_x,1 ⇔ e_y,1)∧(e_x,2 ⇔ e_y,2)∧(e_x,3 ⇔ e_y,3)∧…∧(e_x,m-2 ⇔ e_y,m-2)∧R^x∧R'

e_x,y の真理値が 1 である場合は、e_x,z と e_y,z は同じ真理値をとるようになり、したがって同じ辺とみなしてよいことがわかります。

すなわち e_x,y を 1 にすることと、辺e_x,y を縮約することが同じ効果になります。これは R^xy の作用によるものです。

５頂点の完全グラフを論理式にします。

　( e_1,2 ∨ e_1,3 ∨ e_2,3 ∨ e_1,4 ∨ e_2,4 ∨ e_3,4 ∨ e_1,5 ∨ e_2,5 ∨ e_3,5 ∨ e_4,5 )

これを、V から異なる５頂点を選ぶすべての組合せで行い、それらすべての論理積を K とします。

K は、m(m-1)(m-2)(m-3)(m-4)/5! 個の項の論理積として定義されたことになります。

V の異なる２頂点 x, y を結ぶ辺 e_x,y に真理値 1 を代入してみます。

V から選ぶ５頂点の組を４種に分類します。

1. x と y の両方を含んでいる
2. x を含み y を含んでいない
3. x を含まず y を含んでいる
4. x と y の両方を含んでいない

1の組からつくられるのを K^xy とし、2の組からつくられるのを K^x 、3の組からつくられるのを K^y 、4の組からつくられるのを K' とします。次の恒真式が成立します。

　tautology　K　⇔　K^xy∧K^x∧K^y∧K'

　tautology　K∧R　⇔　(K^xy∧K^x∧K^y∧K')∧(R^xy∧R^x∧R^y∧R')

x = m-1, y = m と仮定すると、e_x,y∧K∧R は次のようになります（K^xy は e_x,y に吸収されます）。

　e_x,y∧(e_x,1 ⇔ e_y,1)∧(e_x,2 ⇔ e_y,2)∧(e_x,3 ⇔ e_y,3)∧…∧(e_x,m-2 ⇔ e_y,m-2)∧(K^x∧K^y∧K')∧(R^x∧R^y∧R')

K^y と R^y を取り除いても同値になることがわかります。

　e_x,y∧(e_x,1 ⇔ e_y,1)∧(e_x,2 ⇔ e_y,2)∧(e_x,3 ⇔ e_y,3)∧…∧(e_x,m-2 ⇔ e_y,m-2)∧(K^x∧K')∧(R^x∧R')

e_x,y の真理値が 1 である場合は、e_x,z と e_y,z は同じ真理値をとるようになり、同じ辺とみなしてよいことがわかります。

e_x,y を 1 にすることと、辺e_x,y を縮約することが同じ効果になります。

(K^x∧K')∧(R^x∧R') は、V から y を取り除いた集合 V-y から、K, R を構成し、掛け合わせたものになります。これは辺を縮約する方が、彩色するより再帰的で都合の良い性質を持つことを意味します。

Hadwiger予想には、四色問題の「なぜ四色で十分なのか？」という疑問に対する洞察が含まれており、その分問題を簡単にしています。Hadwiger予想は四色問題の一般化であると同時に簡略化でもあります。

平面グラフのような５点の完全グラフに縮約できないグラフG を用意します。G のすべての頂点に４色から色を割り当て、G の各辺のとる値を調べます。辺の値は次のように定義します。

• x と y が同じ色の場合は e_x,y は 1 です。
• x と y が違う色の場合は e_x,y は 0 です。

４色を割り当てるすべての方法で、各辺の値を調べて表にすることが出来ます。同様に５色から各頂点に色を割り当てるすべての方法からの表もつくり、両者を比較します。

表といっても、正確には G の各辺の真理値 0 または 1 が決められた順序で並んだベクトル（タプルのほうがいいかもしれません）の集合と思ってください。

グラフG は４色では彩色不可能なグラフでかつ頂点の個数が最小のもの、Hadwiger予想の n = 5 の場合（あるいは四色定理）に対する最小反例であったとします。

• ４色からの表には、G のすべての辺を 0 にするものはありません。（４色では彩色不可能と仮定されているからです）
• ５色からの表には、G のすべての辺を 0 にするものがあります。（最小性からの帰結です）

G の辺を任意に１つ選び e_x,y とします。表から e_x,y = 1 になっている部分を抜き出し比較します。これは頂点 x と y が同じ色に限定されるので、実質 x と y は同じ頂点とすることと同じで、e_x,y を縮約することと同じ意味を持ちます。e_x,y を縮約してしまえば頂点の個数が少なくなるので４色でも５色でも彩色可能です。

• ４色からの表の e_x,y = 1 になっている部分には、G の e_x,y 以外のすべての辺が 0 になっているものがあります。
• ５色からの表の e_x,y = 1 になっている部分には、G の e_x,y 以外のすべての辺が 0 になっているものがあります。

この方法を繰り返していけば、G のすべての辺が 0 になっているもの以外は、４色からの表と５色からの表とでは違いがないことがわかります。

ただし、複数の辺を縮約したときはループ（辺の両端の頂点が同じ頂点である辺）になる場合があります。その場合はその辺も 1 と仮定します。あるいは、５色からの表からすべての辺が 0 ではないものを１つ取り出し、そこで 1 になっている辺すべてを縮約することで４色からの表にも含まれていることを確認するという方法もあります。

こうして、最小反例は簡単で顕著な性質を持つことが分かります。縮約してできるグラフすべてをまとめて扱うことで、最小反例の性質の特異性が際立っています。

グラフG は連結かつ完全グラフではなく、４色で彩色不可能だけど５色では彩色可能だと仮定し、Hadwiger予想の n = 5 の場合が成立していると仮定してみます。

• ４色からの表には、G のすべての辺を 0 にするものはありません。（４色では彩色不可能と仮定されているからです）
• ５色からの表には、G のすべての辺を 0 にするものがあります。（５色で彩色可能と仮定されているからです）

他にも５色からの表に含まれていて４色からの表には含まれていないものがあるはずです。Hadwiger予想が成立するなら、グラフG は５点の完全グラフに縮約可能なはずです。５点の完全グラフに縮約するのに縮約する必要のある辺が 1 で他の辺は 0 になっているものは、５色からの表に含まれていて４色からの表には含まれていません。５点の完全グラフは５色で彩色可能ですが４色では彩色不可能だからです。

もっと他に５色からの表に含まれていて４色からの表には含まれていないものがあれば、1 になっている辺を縮約することにより、５色で彩色可能で４色で彩色不可能なグラフになります。

Hadwiger予想の n = 5 の場合が成立しているとすると、４色からの表と５色からの表に違いがなければ、５点の完全グラフに縮約することは不可能と判断できることになります。

逆にHadwiger予想の n = 5 の場合を証明するには、グラフが５点の完全グラフである場合を除いて、両者の違いがグラフのすべての辺を 0 にするもののみという状況が決して生じないことを明らかにすればよいことになります。ブール代数を使うのが最も自然な方法と思われます。

「なぜ四色で十分なのか？」などと書いてますが、多くの人が気がつくように「５点の完全グラフが交差することなしには平面に描けないから」です。本当に求められているのは、「５点の完全グラフが平面には描けないから４色以内で彩色できる」ということを数学的に正しく表現することです。

ブール代数を使う表現では辺の論理和がよく使われます。

　e_1,2 ∨ e_1,3 ∨ e_1,4 ∨ …

集合の演算で表現すると次のようになります。

　{e_1,2} ∪ {e_1,3} ∪ {e_1,4} ∪ …

辺の論理積もよく使います。

　e_1,2 ∧ e_1,3

これを上記のように形式的に集合演算に対応させると、空集合∅になってしまいます。

　{e_1,2} ∩ {e_1,3} = ∅

つまり、ブール代数を使う方法というのは、単純に辺の集合などを扱う方法と比較してみると、空集合を分析する方法になっています。

頂点すべての色を指定するベクトルを定義しておき、辺を真にする色のベクトルの集合へ対応させる写像をφとします。すると

　φ(e_1,2) ∩ φ(e_1,3)

も集合の演算として意味を持ち、ブール代数による表現を避けることができます。ただしブール代数を使った方が簡潔で見通しがよくなります。グラフを彩色するというのは辺の両端の頂点に異なる色を割り当てることですから、辺から色への写像を考察するのは当然のことです。したがってブール代数を使うのも極めて自然なことです。

それで、写像という概念について調べてみると ガロア理論の推移史について 中村幸四郎 というのがありました。「集合」+「写像」という概念を基礎に理論を展開するという方法はデデキント（Richard Dedekind 1831‐1916）が始めたようです。ガロア論文を整理して整数論に応用するという目的があったようです。それに「一次従属・独立の理論」「ベクトル空間」がこの デデキント体論 から始まったというのも驚かされます。

「写像」という概念には天才ガロア（Évariste Galois 1811‐1832）の大きな影響があるということでしょう。ただ、類似の概念として「関数」があります。関数を工夫して問題を解くということはあります。写像を工夫してある集合の性質を分析するというのは、当たり前の方法です。ブール代数が使われることに抵抗を感じる必要はまったくありません。

おぼえがき

2024年８月１日

Hadwiger予想は現在は極値グラフ理論に分類するのが普通のようです。どうしてでしょうか？ Hadwiger's Conjecture is True for Almost Every Graph - B. Bollobás, P. A. Catlin and P. Erdős というのがあります。Europ. J. Combinatorics (1980) 1, 195-199 だそうです。難しそうな論文ではありますが短いので読んでみました。Erdős には伝記本のようなものがあって読んだことがあります。

Hajós予想というのがあって、彩色に s色必要なグラフは完全グラフ K_s の細分を含むというもので、一般的には否定されています。代数的な扱いが容易なHadwiger予想とは違って、完全グラフの細分を扱うというのは難しいことです。それで、Erdős と Fajtlowicz は確率・統計の考え方を取り入れて、ほぼすべてのグラフでHajós予想が成立しないことを証明したそうなのです。そして、完全グラフの細分を完全グラフ K_s に縮約可能な部分グラフ（マイナー）に置き換えると、ほぼすべてのグラフでHadwiger予想が成立することが証明できたということのようです。

ほぼすべてのグラフというのは頂点の数が大きなグラフでのことらしく、辺を確立２分の１であるなしを決めてグラフを作れば、辺の数がそれなりに多いグラフが多く作られ、彩色に必要な色の数はそれなりに大きく、辺の数が多いのでそれなりの大きさのマイナーを含む確率が高くなる、ということのようです。

この辺の数に関係した考え方が、Hadwiger予想の本質とする数学者が多くて、Hadwiger予想が極値グラフ理論に分類されたのではないかと推測できます。

しかしです、これではほぼすべてのグラフは平面グラフではない、ということになって Almost Every から漏れてしまいます。Erdős も予備的研究と考えていたのではないかと思います。

Erdős には申し訳ありませんが、Hadwiger予想はド・モルガン則の亜種とみるのが正解のようです。

2024年９月１日

ブール代数の論理式ですが、これは代数学的にはほぼイデアルと考えるのがよさそうです。それで意外に深く分解することができて、初等的な方法では大量の場合分けになってしまうことを簡潔にすますことができるということだと思います。

初等的な方法といのは、それ自体が面白かったり、理解しやすい場合もあります。ですが、場合分けが多くなる傾向があり、かえって難しくなることも多いようです。その極端な例が四色定理です。

グラフ理論でも、初等的方法では、まず頂点の集合、辺の集合がり、その上に様々な数学的な概念を作ってゆくだけななのですが、ブール代数による方法では頂点や辺の集合をもっと細かく砕いてから理論を作っていることになります。

でもどうして Erdős はそこまで初等的方法にこだわったのでしょうか？　数学では方法はどうあれ証明ができれば研究は楽になるのですから、証明してしまった方がいいと思うのですが。初等的方法が心のよりどころになっているのかもしれません。それに有名な数学者でも簡単な性質を見逃していたという事例は探せば意外とあるのかもしれません。

2024年10月１日

Appel and Haken の四色定理の証明には放電法が使われ、オイラーの公式が応用されています。Hadwiger予想を四色定理の一般化とする立場では、四色定理の証明を一般化してHadwiger予想の証明しようと考えたのかもしれません。それで平面の場合の頂点と辺の数の関係を表すオイラーの公式のかわりに極値グラフ理論が使われるということでしょうか。

Appel and Haken の "EVERY PLANAR MAP IS FOUR COLORABLE PART I: DISCHARGING" を読んでみると（といっても Introduction だけなのですが）可約と判定困難な配置を避けるために放電法が工夫されたことがわかります。そして四色定理は証明され、結局すべての配置が（平面内に限ると）可約であることがわかりました。なので、もっと直接的に可約であることを証明する方法があったとしても何の不思議もありません。（数学研究のかなりの部分は証明方法の探求ですから、やれそうなことは、やってみるべきです。そう考えると先により困難なことやってくれたことに感謝するべきですね。）

ブール代数を使った証明が最も簡単なタイプの証明だと思われますが、リングの外側の Kempe鎖 をもっと詳しく分析することで初等的に証明できる可能性も残っていると思います。初等的な方法では本当に場合を尽くしているかの確認が難しく、結局コンピューターを使うことになりそうですが。

2024年11月１日

Extremal graph theory によると In essence, extremal graph theory studies how global properties of a graph influence local substructure. （本質的には、極値グラフ理論はグラフの大域的な性質がどのように小域的な部分構造に影響するかを研究する。）ということだそうです。これは Reinhard Diestel が Graph Theory の 7. Extremal graph theory の冒頭で述べていることの引用です。

Appel and Haken の四色定理の証明の、放電法、可約配置という方法も極値グラフ理論として解釈することができそうです。しかし、彩色に５色必要なグラフでも辺を１つでも取り除けば４色で彩色可能というグラフは無数に存在します。真の部分グラフの性質を見つけるのはかなり難しそうです。なにかすごい性質が発見されなければ、極値グラフ理論として解釈するのは苦肉の策に思えます。やはりグラフ全体を表現、分析する手段を探すべきです。その手段の１つがブール代数を使う方法です。

とはいえ、とてもできないように思えることができてしまう、というようなことも数学の面白さですから、極値グラフ理論による Hadwiger予想の証明もぜひ完成させてほしいです。

2024年12月１日

ブール代数によるHadwiger予想の証明は抽象代数学的証明ですから、ガロア第一論文と比較したくなります。ガロア第一論文は代数方程式の代数的可解性に関するものです。

ガロアは代数方程式の根から後にガロア分解式と呼ばれる多項式を作り、その既約成分の根から根の順列を作り、それから置換群を作ります。置換群の部分群による剰余類分割という考えを基本に群論が展開され、それに体の代数拡大が対応します。

ガロアの発想のすごいところは、本来多項式は数を数に対応させるものとして理解するのが普通ですが、群に対応させてしまうことです。数に対応させるだけでは証明に必要な性質が分かりやすく表現できないので、数のかわりに抽象的につくられた数のようなものに対応させるわけです。数学なので抽象的になったりするのは当然ですが、ガロアの場合は“突き抜けた”感じがします。高い数学的あるいは論理的能力と過激な性格ゆえにできたことだと思います。

ガロア第一論文から得られる教訓はなんでしょうか。それは、普通の数に対応させて証明するのが困難ならば、抽象的に構成され証明に必要な構造を反映させることができる、数のようなものに対応させることを検討するべきだということです。つまり辺の数を数えることで証明するのが困難ならば、ブール代数のような抽象的なものを使うことを検討するべきだということです。

人工的につくられた数のようなものに、対応させる、あるいは翻訳することで本質的な性質を抽出する、というのがガロアが使った手法で、これにより証明で使える表現方法が大きく広がったということですね。ただ、論理的な枠組みを作ったという意味合いが大きく、それがガロアの評価を難しくしているようです。

群論の性質に正確に翻訳する手法も見事ですから、ガロア第一論文は抽象代数入門の手本として最も優れた論文といえそうです。現代のガロア理論は体の自己同型写像という概念が天下り的に与えられる形になっていて、体の理論に特化してるので、他の問題への応用が難しくなってるような気がします。

2025年１月１日

集合の定義の仕方に内包的な方法と外延的な方法があります。外延ではある程度具体的に列挙する方法です。内包では性質で定義する抽象的な方法です。論理でも同様な内包と外延があります。外延は内側から広げるイメージで内包は外側から絞り込むイメージです。あるいは外延は下から積み上げる方法で内包は上から降りていく方法ともいえます。数学では両方使うわけですが、どちらかの方法が目立つ場合もあります。代数方程式論ではアーベルは根の代数的関係で可解になるものをすべて求めようとしたそうで、外延的という印象です。ガロアは係数体を分解体まで拡大するということを実質的におこなうので内包的という印象です。逆方向からのアプローチになっています。つまり、数学では少なくとも研究方法としては２とおりあると思ったほうがいいらしいのです。

Appel and Haken の四色定理の証明では、不可避集合として可約配置を具体的に列挙するという方法なので外延的方法です。それに対してブール代数による証明は定理をブール代数の言葉に翻訳するという方法で内包的なものです。

それに構造主義という考え方がわかりやすいです。「なぜそういう性質を持つのか？」という問いに対して「そういう性質を持つ構造があるから」と答えることができるわけですから。構造の中に構造を見つけだし抽出することで証明する、という方法です。副次的に生じる構造に支配されてしまう、とうのが数学的にみた形而上学＋構造主義による世界観といえそうです。

2025年２月１日

難しくなるとより深く分析してはっきりさせたくなるわけですが、複雑になってしまいます。しかし抽象化がうまく行く場合は、簡潔に証明できたりする場合があるということですね。逆にみると抽象化ができないと、深くしていくのが難しくなってしまいます。それにしっかりと表現して計算できる基礎となるものがあることも大事です。そうしたものがないと抽象化しても、本当に計算できるのかどうかわからなくなってしまいます。と考えると、ブール代数を使う方法は合理的であったと思います。

別冊宝島44『現代思想・入門』の小阪修平（哲学者）によると形而上学とは

1. アリストテレスの『形而上学』がそうであったように実体（真に存在するもの）を探求しようとする学であり、
2. アリストテレスの『形而上学』の名前が『自然学』のあとにおかれたことからつけられたように、自然をこえたもの（つまりこの見かけの世界の背後にある真理、あるいは真の存在）についての学を意味した。
3. 形而上学とはこの日常的世界の背後に、あるいは日常生活とは隔絶した場所に真の存在や真理をもとめようとする思想である。
4. 形而上学とは、ことば（ロゴス）によってこの世界の真理をのべつたえようとする、あるいはこの世界の真理はことば（ロゴス）のうちにある、という思想としてもとらえられる。
5. 形而上学はたんなるロゴスへの確信としてではなく、現実を説明しつくそうとする知の体系として完成される。そのような哲学としての哲学こそ、ヘーゲルの哲学にほかならない。

かなりおおげさな感じがしますが、おおげさに言ってくれたほうが面白いです。数学の場合は証明しなければなりませんが、正しい証明があるとすればロゴスのうちにあると考えるしかありません。それを探すのですから形而上学的になってしまうのはしょうがありません。

2025年３月１日

勉強してみると ソクラテス、プラトン、アリストテレス など古代ギリシャの大哲学者の数学に対する影響というのはかなり大きいようです。真理はロゴスで表現できて、それら真理は互いに矛盾しないように理解することができるという思想があったわけです。

しかし証明を正確に表現するのは難しいことです。その難しさの程度が表現手法の選択によって大きく変わることも珍しくありません。その場合、証明する定理の本質をおさえた表現手法ならわかりやすいものになることが期待できます。ガロア第１論文の場合は体の自己同型写像（に相当するもの）を基礎とする方法でした。Hadwiger予想の場合はディレクレの鳩巣原理とド・モルガンの法則です。

極値グラフ理論は鳩巣原理の拡張とみなせますが、彩色と縮約の関係を表現するのが難しく、Hadwiger予想を証明することができていないのではないかと思います。どうしてそうなったかというと、初等的な方法にこだわりすぎたからではないでしょうか。

2025年４月１日

Hadwiger予想のブール代数による証明 では伝統的な最小反例を仮定する方法、つまり数学的帰納法＋背理法になってますが、単純な数学的帰納法による証明にすることも可能です。

　tautology　{ g∧(K_n∧R) }　→　Σ(k∧K_n∧R)

という帰納法の仮定から（記号の意味は Hadwiger予想のブール代数による証明 と同じです）

　tautology　(K_n∧R)　→　Σ(k∧K_n∧R)

を、同じ方法で導けばいいだけです。このほうがすっきりしてます。ありもしない反例の性質を考えなくてすみます。気が向けばこのように書き換えるかもしれません。難しいグラフ理論の定理は使う必要がないことから、Hadwiger予想はグラフ理論の基礎的な定理であることがわかります。それで初等的に証明されるべきと考えられたきたのでしょうか。

Home