おぼえがき
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色必要なグラフは完全グラフ Ks の細分を含むというもので、一般的には否定されています。代数的な扱いが容易なHadwiger予想とは違って、完全グラフの細分を扱うというのは難しいことです。それで、Erdős と Fajtlowicz は確率・統計の考え方を取り入れて、ほぼすべてのグラフでHajós予想が成立しないことを証明したそうなのです。そして、完全グラフの細分を完全グラフ Ks に縮約可能な部分グラフ（マイナー）に置き換えると、ほぼすべてのグラフで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『現代思想・入門』の小阪修平（哲学者）によると形而上学とは
- アリストテレスの『形而上学』がそうであったように実体（真に存在するもの）を探求しようとする学であり、
- アリストテレスの『形而上学』の名前が『自然学』のあとにおかれたことからつけられたように、自然をこえたもの（つまりこの見かけの世界の背後にある真理、あるいは真の存在）についての学を意味した。
- 形而上学とはこの日常的世界の背後に、あるいは日常生活とは隔絶した場所に真の存在や真理をもとめようとする思想である。
- 形而上学とは、ことば（ロゴス）によってこの世界の真理をのべつたえようとする、あるいはこの世界の真理はことば（ロゴス）のうちにある、という思想としてもとらえられる。
- 形而上学はたんなるロゴスへの確信としてではなく、現実を説明しつくそうとする知の体系として完成される。そのような哲学としての哲学こそ、ヘーゲルの哲学にほかならない。
かなりおおげさな感じがしますが、おおげさに言ってくれたほうが面白いです。数学の場合は証明しなければなりませんが、正しい証明があるとすればロゴスのうちにあると考えるしかありません。それを探すのですから形而上学的になってしまうのはしょうがありません。
2025年３月１日
勉強してみると ソクラテス、プラトン、アリストテレス など古代ギリシャの大哲学者の数学に対する影響というのはかなり大きいようです。真理はロゴスで表現できて、それら真理は互いに矛盾しないように理解することができるという思想があったわけです。
しかし証明を正確に表現するのは難しいことです。その難しさの程度が表現手法の選択によって大きく変わることも珍しくありません。その場合、証明する定理の本質をおさえた表現手法ならわかりやすいものになることが期待できます。ガロア第１論文の場合は体の自己同型写像（に相当するもの）を基礎とする方法でした。Hadwiger予想の場合はディリクレの鳩巣原理とド・モルガンの法則です。
極値グラフ理論は鳩巣原理の拡張とみなせますが、彩色と縮約の関係を表現するのが難しく、Hadwiger予想を証明することができていないのではないかと思います。どうしてそうなったかというと、初等的な方法にこだわりすぎたからではないでしょうか。
2025年４月１日
Hadwiger予想のブール代数による証明 では伝統的な最小反例を仮定する方法、つまり数学的帰納法＋背理法になってますが、単純な数学的帰納法による証明にすることも可能です。
tautology { g∧(Kn∧R) } → Σ(k∧Kn∧R)
という帰納法の仮定から（記号の意味は Hadwiger予想のブール代数による証明 と同じです）
tautology (Kn∧R) → Σ(k∧Kn∧R)
を、同じ方法で導けばいいだけです。このほうがすっきりしてます。ありもしない反例の性質を考えなくてすみます。気が向けばこのように書き換えるかもしれません。難しいグラフ理論の定理は使う必要がないことから、Hadwiger予想はグラフ理論の基礎的な定理であることがわかります。それで初等的に証明されるべきと考えられたきたのでしょうか。
2025年６月１日
7 Extremal graph theory（2025年第６版になってました） の225ページに Wagner が1935年の博士論文で四色問題を 'detopologize' しようとした、と書いてあります。これは '脱平面' という意味と思われます。平面ということよりも K5 マイナーを含まないグラフという条件のほうが本質的と考えたのだと思います。しかし後のアペルとハーケンによる証明は平面という条件にたよった証明です。あまり本質的ではない、見かけの性質を場合分けしたために膨大な場合分けになったともいえそうです。
平面という性質を取り除いて残っているものは、有限集合の性質と考えれば、その個数が重要で極値グラフ理論へという流れだったと想像できます。しかし Hajós の構成（1961）という代数構造が発見されたのですから、抽象代数で研究するというのも自然なことに思われます。どうしてこの方向に進まなかったのか？グラフ理論の研究者というのは、反形而上学、反構造主義の人が多いのかもしれません。「この見かけの世界こそが現実の世界である。現実の世界を研究するべきである」という主張も一理あるとは思いますが。
2025年７月１日
Vašek Chvátal[著] ポール・エルデス：離散数学の魅力 の 139ページにしたがって， Hadwiger 予想は，Hajós 予想よりも弱い．それにも関わらず，Hadwiger 予想さえ四色定理を包含するほど強い．
とあります。専門の数学者が書いたものだけに論理的な感覚が鋭いです。四色定理の証明がなぜ難しいかというと、平面という条件があまりにも弱いからです。こういう理由で４色で彩色できる、と考えてもその理由を平面という条件から導くことがなかなかできません。Klaus Wagner が登場して平面という条件をさらに弱くした K5 マイナーを含まないという条件に置き換えても同値であることを証明しました。よけいに難しくなったようにも見えますが、そうではありません。K5 マイナーを含まないという条件を余計な仮定を置かずにそのまま分析していけば解決できる可能性が浮上してきたことになります。
ガロアというのは、構造の急所をつくことで簡単に理解できるようにするのが大好きな数学者であると思えてきました。その傑作が、「有理関係を変えない変換」を体に対して定義されたものとみなす、いわゆるガロア対応の原型です。体という概念もまだなく（ただしアーベルには体に相当する有理領域とよぶ概念があったそうです）理解してもらうのは大変だったろうと思います。
2025年８月１日
Vašek Chvátal[著] ポール・エルデス：離散数学の魅力 117ページの 7.5 極値グラフ理論前史 によるとErdősはある数論の問題を解くために極値グラフ理論的な性質を研究してたそうです。極値グラフ理論には数論への応用があったということを知りました。それで極値グラフ理論を別の見方ができることに気が付きました。四色問題が一見簡単にみえるのに証明が複雑になってしまうのは、内部に数論的な性質がかくされているからではないか、と考えた可能性です。これなら辺の個数とか、平均次数などにこだわる理由もわかりそうな気がします。Hadwiger 予想は一般の n では成立せず、成立しなくなる n には数論的な意味があると期待したかもしれません。しかし、Hadwiger's Conjecture is True for Almost Every Graph - B. Bollobás, P. A. Catlin and P. Erdős にあるようにすべての n で成立しそうだとなると、簡潔な証明があったほうが自然だと思います。
2025年９月１日
Birkhoff とブール代数による方法を比較してみると、Birkhoff の方法は加法的に展開する方法で、乗法的に展開する方法がありません。普通の代数方程式も加法的に表現されたものを乗法的な形に変形することで解かれることを見ても大きな欠点です。ブール代数による表現ではある範囲の着色全てが抽象化されて表現されているので、ケンプ鎖による塗り替えがたいして意味を持ちません。乗法的に展開することによる成果は、平面グラフにおいては全ての配置（頂点）が多少拡張された C-reducible であることが証明できることです。
Appel and Haken、Robertson らの四色定理の証明は美しくないと批判される事が多いようです。証明の論理的な構造としてはやむを得ないと思います。全体に場当たり的な証明になってるし、全ての配置が reducible であるべきなのにそれが直接は証明できずに放電法に頼っています。しかし、reducible の判定には工夫されたアルゴリズムが使われ工学的な美しさがあります。放電法にしてもルールを重ね合わせると夜空に輝く星座のごとく特定の配置が浮かび上がるという美しいものです。すると、数理哲学としての形而上学よりも一般的な美しさを優先させた結果、支持されているのかもしれません。
2025年10月１日
Erdős はRamsey理論の研究もしていたので極値グラフ理論の方向に進んだのは自然なことだったのかもしれません。そうすると、Wagner が四色問題を 'detopologize' したあとに残っていいるのは「集合の性質」と考えたということでしょうか。極値グラフ理論でHadwiger予想を証明するにはどうすればいいのか？ 例えば、各頂点の次数の分布を表現する方法があっていい性質があればそれで証明できる可能性がありそうです。もし反例があるならかなりたくさんあって、頂点の数を増やした時に反例である確率が 0 に向かわない、なので矛盾して反例は存在しない、というのもありえるかもしれません。どちらもかなり難しそうです。やはり、最初はなるべく簡単な方法で証明することを考えるべきですね。
プラトンは幾何学は永遠の知識と考えたらいしです。このうつろいやすい世の中で、永遠の真理を求めたということですね。老子には「道のいうべきは常の道にあらず」とあるように永遠の真理を言葉で表すことは無理としたのと正反対です。それで「学を絶たば憂いなし」となるわけですね。背後に数学があるかないかの違いなんでしょうか。
2025年11月１日
プラトンが徹頭徹尾矛盾のない世界としたのはイデアの世界であって、我々の生活している世界は不完全な世界と考えていたのなら、老子が述べているのは人間の世界であるから両者は矛盾しないのかもしれません。人間の世界は嘘、間違い、矛盾だらけの世界であって、一般にいわれてることと正反対のことが正しい場合がある。だから学問なんてしない方がいいと。
自然というものは、なるに任せてるだけという意味でなにもしてないけど、するべきことはすべてやっている。人間もみならって、なにもなさないことでなすべきことすべてをなす、というのが「無為自然」ですね。本当になにもしないのは難しいですが、無為自然に近づけることは可能です。もともと持っていた力とか構造を生かして証明するのがいいという考え方です。そうすると深い分析とそれを表現する方法を見つけることができれば、おのずと証明できるという思想になりそうです。
2025年12月１日
極値グラフ理論というのはディリクレの鳩巣原理を拡張しようとする試みととらえるべきなのかもしれません。鳩巣原理なら鳩の数と巣の数を数えなければなりませんし、グラフの彩色問題と関わりがあります。ただ、Hajós の構成法も鳩巣原理の拡張です。彩色に５色必要なグラフを構成してもとても（直感的に）平面的グラフになるとは思えません。グラフが平面的かどうかを判定する方法はあるそうなので、こうした方法で四色定理が証明できてもよさそうです。Hajós が彩色に n色以上必要なグラフであることの必要十分条件を確立したのは大きな成果ですから、これに個数を数える手法をかけ合わせれば極値グラフ理論での証明の可能性も否定できないと思われます。いずれにせよかなり難しそうなので、簡単に証明できるブール代数による方法を見つけてしまって申し訳ないという気持にもなります。
老子が述べてるのは世間の言説への不信感であって、ロゴスに対する不信感とは違うという解釈もできそうです。老子の思想は禅や仏教思想としても日本の文化に影響してますから重要なところですね。
2026年１月１日
ホモロジー理論＋Hajós の構成法で四色定理の証明可能というのはありえそうです。ただ、幾何学的に理解しようとするのは本質的ではないだろうと思います。彩色することと縮約するという反対のことの論理的関係が本質的です。それは Birkhoff がうまく扱えずに取りこぼした部分でもあります。とはいえ、人間は楽な方向へ流されやすいですから、コンピューターを使って証明できたのだからそれでいいだろうとか、他に方法はないんだとか信じたくなる気持ちもわかります。それにグラフ理論は歴史の浅い分野ですから、数論のように何千年も研究されてきた分野とは違います。基礎的な部分でも間違った方向に進んでしまってなかなか修正できないという事があっても仕方がありません。
組合せ理論のような数学だと場合分けが多くなるのはしょうがないと思われます。“場合分けの美学”を追求するあまり場合分け職人となってしまうのかもしれません。「ブール代数を使ってみてはどうか」ともちかけると「そんなもん使ってられるか」と頑固な職人に怒鳴られるという感じだったのでは。
2026年２月１日
老子が述べているのは学者への不信感からくる王とか皇帝とかいった権力者へのアドバイスと解釈するのがいいのかもしれません。いいかげんなが学説をつくっては権力者に取り入ろうとする学者がいて民衆を困らせるので、それなら何もしないほうがまだまし、ということですね。「学を絶たば憂いなし」「知恵いでて大偽あり」ですから。
Birkhoff の考え方が説得力があって、かつこれで証明できたから、ということなんですかね。「次数の大きい頂点があればその分次数の小さい頂点がなければならず、それが弱点になってしまう」という考え方です。これなら平均次数にこだわる気持ちもわかるような気がします。それで彩色に n 色以上必要なグラフの全体にブール代数で表される代数的構造が存在することから、任意次数の頂点の可約性が直接証明できるという可能性を考えることができなくなってしまった、ということなのではないかと思います。