四色定理に珍しい新しい証明が登場

ホーム 四色定理に珍しい新しい証明が登場 コメント 記事を保存 後で読む シェア Facebook コピー済み！ リンクをコピー メール ポケット レディット Ycombinator コメント コメント 記事を保存 後で読む 後で読む グラフ理論 四色定理に珍しい新しい証明が登場 Gregory Barber 著 2026年9月10日 1970年代にコンピューターの助けを借りて論争的に解決された有名な問題を見直すことで、数学者はグラフの性質について重要な新しい洞察を得ました。コメント 記事を保存 後で読む 四色定理は単純に述べることができます。連続した地図が与えられたとき、隣接する領域が色を共有しないように、各領域を4色で塗り分けることは可能でしょうか？ Vico Santos for Quanta Magazine 導入 解決された後も、一部の数学の問題は研究者を悩ませ続けます。証明が現れ、称賛されても、不満が残ることがあります。議論が複雑すぎるため、あるいはそれがなぜ真実なのかについての深い理論的洞察を与えないためかもしれません。理由が何であれ、数学者は閉鎖されたと見なされているケースに繰り返し戻ります。そのような最も有名なケースの1つが、数学者が主題について考える方法を変えた問題である四色定理です。問題は述べるのが簡単で、見るのはさらに簡単です。連続した地図が与えられたとき、隣接する領域が色を共有しないように、各領域を4色で塗り分けることは可能でしょうか？ 19世紀半ば、この問題は地図製作者にとって取るに足らない関心事でした。彼らは4色以上の色を持っており、パレットを制限する特別な理由を見出せませんでした。しかし、アマチュアとプロの両方の数学者にとって、この頭の体操はすぐに執着に変わりました。最初の証明とされるものは1879年に発表されましたが、誤りであることが証明されるまで11年間続きました。弁護士、医師、そして有名なグラフ理論家からも、さらに多くの誤った答えが出ました。「子供でも理解できる問題です」と、デンマーク工科大学のグラフ理論家であるCarsten Thomassenは言いました。「それがこれほど大きな挑戦であった理由だと思います。」この定理は、当時論争の的となったコンピューター手法によって、ほぼ1世紀後に最終的に証明されましたが、それは証明とは何かということを数学者に問い直させました。問題のステータスは、コンピューターの使用がより一般的になり、より単純なコンピューター支援証明が見つかった1997年まで議論の源であり続けました。しかし今日でも、コペンハーゲン大学のコンピューター科学者であるMikkel Thorupが言うように、「四色病」は依然として広まっています。彼とThomassenは、罹患した者の中に自分たちを数えています。これほど単純な命題であるならば、それが真実であるには、より単純な理由があるはずです。少なくとも、それを証明するためのより効率的な方法があるはずです。約10年間の作業を経て、Thorup、Thomassen、そしてデンマーク、カナダ、日本の4人の同僚は、この定理を再び証明するコンピューター証明を作成しました。左から：Carsten Thomassen、Ken-ichi Kawarabayashi、Mikkel Thorup、Bojan Moharは、最近四色定理を再証明し、その過程で地図やグラフをより効率的に色付けする方法を明らかにしたチームの一員です。Mikkel Thorup提供 この証明は、2026年3月にオンラインで公開され、11月に年次コンピュータ科学基礎会議で発表される予定ですが、ある意味では先行する証明よりもさらに複雑です。「彼らは証明を実行するために、電力を使っているようです」と、パリのInriaのコンピューター科学者であるGeorges Gonthierは述べています。しかし、彼らの議論を練る過程で、研究者たちは地図を色付けする、はるかに効率的な方法を提供しました。そしてそうすることで、平面グラフと呼ばれる重要な数学的オブジェクトの構造的特性に関する新しい洞察を発見し、グラフ理論における他の多くの頑固な問題の進歩の可能性を開きました。問題の歴史的な誤った開始と希望の喪失を考えると、Gonthierは「今回は本当の結果を見ることができて本当にクールだ」と述べました。コンピューター化された論争 1852年、数学者のFrancis Guthrieはイングランドの郡の地図を色付けしているときに、4色しか必要ないことに気づきました。彼は、これは常に真実だろうかと思いましたか？彼は数学者である弟のFrederickに尋ねました。その指導教官であるAugustus De Morganは、この問題に関心を持ち、より広い聴衆に宣伝することにしました。1879年、Alfred Bray Kempeという名前の数学者が解決策を主張したとき、プレスリリースがNatureでその成果を発表しました。Kempeは、証明したいことの反対を仮定することから始めました。つまり、4色で色付けできない地図が存在するという仮定です。彼は、この仮定が最終的に矛盾につながることを示そうとしました。つまり、そのような地図は存在しないということです。その場合、すべての地図は4色で色付け可能でなければなりません。まず、彼の仮定から得られた4色で色付けできない地図は、可能な限り「最小」であると想像してください。もしその地図から任意の国を削除すれば、残りの地図は4色で色付け可能になります。次に、地理やその他の無関係な詳細を無視して、地図を平面グラフと呼ばれるものに描き直します。各国を点（または頂点）として表し、2つの国が国境を共有している場合は、それらの点間に線（または辺）を描きます。あなたの地図の色付け問題は、グラフ理論のツールに開かれたグラフの色付け問題になりました。Mark Belan/Quanta Magazine 特に、18世紀にスイスの数学者Leonhard Eulerは、平面グラフには多くの有用な特性があることを発見しました。それらのうちの1つは、任意の平面グラフが5つ以下の隣接頂点を持つ頂点を少なくとも1つ含むという保証です。それは、あなたのグラフがこれらの6つの構成のいずれか、Kempeが「避けられないセット」と呼んだものを含まなければならないことを意味します。そして、あなたのグラフは最小なので、これらの構成のいずれかを削除すると、4色で再色付けできるグラフが残ります。Kempeの天才的な動きは、これらの構成のいずれかを削除しても、グラフの色を入れ替える方法を見つけることができ、欠けている頂点を再度追加したときに、5色を必要とせずにすべての頂点を色付けできることを示すことでした。Mark Belan/QuantaMagazine このようにして、避けられない構成のそれぞれが「還元可能」であることを示すことで、最小グラフは結局4色で色付け可能であることを証明しました。つまり、元の仮定は間違っていました。四色定理は真実でなければなりません。残念ながら、Kempeが証明を発表してから11年後、数学者のPercy John Heawoodは、彼の色交換手順に微妙な欠陥を発見しました。削除する頂点が5つの隣接頂点を持つ場合、Kempeの方法は同じ色が隣接してしまう可能性があります。Heawoodは、Kempeのアプローチが非常にエレガントであったため、部分的には、エラーを報告することに当初はためらいました。実際、Kempeの誤りにもかかわらず、彼の交換手順（今日ではKempeチェーンとして知られています）は、問題に対する将来の解決策の中心であり続けました。「あなたは自分の名前で呼ばれるほど興味深い間違いを犯すというのは興味深いと思いませんか？」とThomassenは言いました。結局、Kempeの避けられないセットの最後の構成が還元可能であることを示すことができませんでした。正しい証明は、代わりに、はるかに大きく、より複雑な8,900の構成のセットを特定し、それらすべてが還元可能であることを示すことを必要とすることが判明しました。そのタスクは手作業では処理不可能でした。コンピューターが必要でした。1976年、数学者のKenneth AppelとWolfgang Hakenは、可能性のある数をまず1,936の構成に、次に1,482に減らす巧妙な方法を見つけました。そして、イリノイ大学のスーパーコンピューターを使用して、それぞれを適切に還元しました。ついに、彼らは四色定理が解決されたと言いました。イギリスの数学者Augustus De Morganは、四色問題へのより広範な関心をかき立てようとしました。「私の学生の一人が今日、私に事実の理由を尋ねてきましたw