数学者らがエルデシュ彩色予想を解決

1972年の秋、ヴァンス・フェイバーはコロラド大学に新しく教授として着任しました。二人の著名な数学者、ポール・エルデシュとラースロー・ロヴァースが訪ねてきた際、フェイバーはティーパーティーを主催することにしました。特にエルデシュは、風変わりで精力的な研究者として国際的に知られており、フェイバーの同僚たちは彼との出会いを心待ちにしていました。

「私たちがそこにいる間、よくあるお茶会と同じように、エルデシュはファンに囲まれて隅に座っていました」とファーバーは言った。「彼は同時に、しばしば複数の言語で、様々なことについて議論を続けていました。」

エルデシュ、ファーバー、そしてロヴァースは、当時グラフ理論における有望な新概念であったハイパーグラフについて議論を交わしました。議論を重ねた結果、彼らは一つの疑問に辿り着きました。これは後にエルデシュ＝ファーバー＝ロヴァース予想として知られるようになりました。これは、ある制約の下でハイパーグラフの辺を彩色するために必要な最小の色数に関するものです。

「あれは私たちが思いつく限りの最もシンプルなものでした」と、現在防衛分析研究所計算科学センターの数学者であるファーバー氏は語る。「パーティー中に少し作業して、『まあ、明日仕上げよう』と言ったんです。結局、明日は完成しませんでした」

この問題は予想をはるかに上回る難問であることが判明した。エルデシュはこれを自身のお気に入りの3つの予想の一つとして頻繁に宣伝し、解読に対する懸賞金を提示した。数学者たちがその難しさに気付くにつれて、懸賞金は500ドルにまで増額された。この問題はグラフ理論界ではよく知られており、多くの試みがなされたが、どれも成功しなかった。

しかし今、約50年を経て、5人の数学者からなるチームがついにこのティーパーティーの思索が正しいことを証明しました。1月に投稿されたプレプリント論文では、特定のハイパーグラフの辺をシェーディングするために必要な色の数に制限を設け、重なり合う辺が同じ色にならないようにしています。色の数がハイパーグラフの頂点の数を超えることは決してないことを証明しています。

このアプローチは、グラフの一部の辺を注意深く残し、他の辺をランダムに色付けするというもので、近年、研究者たちが長年の未解決問題の数々を解決するために用いてきたアイデアを組み合わせたものだ。エルデシュ、ファーバー、そしてロヴァースがこの問題を思いついた当時、このアプローチは彼らには考えられなかった。しかし今、その解決策を見つめながら、最初の3人組のうち生き残った2人の数学者は、自分たちの好奇心が引き起こした数学的革新を心から楽しむことができるのだ。

「素晴らしい作品です」とエトヴェシュ・ロラーンド大学のロヴァース氏は語った。「この進歩を見て本当に嬉しく思いました。」

ちょうどいい色

エルデシュ、ファーバー、ロヴァースがお茶をすすりながら数学について語り合う中で、彼らの頭の中にはグラフのような新しい構造が浮かんでいた。通常のグラフは、頂点と呼ばれる点と、辺と呼ばれる線で結ばれた構造で構成されている。それぞれの辺はちょうど2つの頂点を繋いでいる。しかし、エルデシュ、ファーバー、ロヴァースが考えたハイパーグラフはそれほど制約が厳しくなく、辺は任意の数の頂点を囲むことができる。

エッジというより拡張的な概念により、ハイパーグラフはハブアンドスポーク型のグラフよりも汎用性が高くなっています。標準的なグラフは、ソーシャルネットワークにおける2人の友人（各人物は頂点で表現されます）のような、2つの物体間の関係しか表現できません。しかし、2人以上の関係（例えば、グループへの所属を共有するなど）を表現するには、各エッジが2人以上の人物を包含する必要がありますが、ハイパーグラフではこれが可能です。

ただし、この汎用性には代償が伴います。通常のグラフよりもハイパーグラフの普遍的な特性を証明するのは困難です。

「ハイパーグラフに移行すると、グラフ理論の多くの奇跡は消えてしまうか、物事がはるかに困難になる」とヘルツリーヤIDCとエルサレム・ヘブライ大学のギル・カライ氏は語った。

例えば、辺彩色問題はハイパーグラフではより困難になります。このようなシナリオでは、グラフ（またはハイパーグラフ）のすべての辺を、頂点で交わる2つの辺が同じ色にならないように彩色することが目標となります。このために必要な最小色の数は、グラフの彩度指数と呼ばれます。

エルデシュ＝ファーバー＝ロヴァース予想は、辺の重なりが最小限である特定の種類のハイパーグラフに関する彩色問題です。線型ハイパーグラフと呼ばれるこれらの構造では、2つの辺が複数の頂点で重なることは許されません。この予想は、線型ハイパーグラフの彩色指数は頂点の数を超えることはないと予測しています。言い換えれば、線型ハイパーグラフに9つの頂点がある場合、その辺は、どのように描画したかに関わらず、最大9色で彩色できるということです。

エルデシュ＝ファーバー＝ロヴァース予想の極めて一般的な性質は、証明を困難にしています。頂点数の多いハイパーグラフに移行すると、ループする辺の配置方法も倍増します。こうした可能性を考慮すると、頂点数よりも多くの色数を必要とする辺の構成が存在する可能性が高く見えるかもしれません。

「ハイパーグラフには実に様々な種類があり、それぞれ全く異なる特徴を持っています」と、新たな証明の著者の一人であるアビシェク・メトゥク氏（バーミンガム大学のドン・イェップ・カン氏、トム・ケリー氏、ダニエラ・キューン氏、デリック・オスタス氏と共に）は述べた。「これが真実だというのは驚きです。」

この驚くべき予測を証明するには、色付けが特に難しい数種類のハイパーグラフに取り組む必要があり、さらに難しい例は他にないことを確立する必要がありました。

3つの極端なハイパーグラフ

紙に落書きをして線形ハイパーグラフを描くとしたら、その彩度指数は頂点数よりもはるかに小さくなるでしょう。しかし、その限界を押し広げる極端なハイパーグラフが3種類あります。

最初のグラフでは、各辺は2つの頂点のみを繋いでいます。すべての頂点ペアが辺で繋がっているため、通常、完全グラフと呼ばれます。奇数個の頂点を持つ完全グラフは、エルデシュ＝ファーバー＝ロヴァース予想で許容される最大の彩色指数を持ちます。

2つ目の極端な例は、ある意味では完全グラフの逆です。完全グラフでは辺が繋ぐ頂点の数は少ない（2つ）のに対し、このタイプのグラフではすべての辺が繋ぐ頂点の数が多くなります（頂点の総数が増えると、各辺が囲む頂点の数も増えます）。これは有限射影平面と呼ばれ、完全グラフと同様に彩色指数が最大になります。

3番目の極端な例はスペクトルの中間に位置し、2つの頂点だけを結ぶ小さな辺と、多数の頂点を結ぶ大きな辺があります。このタイプのグラフでは、多くの場合、1つの特別な頂点が他のすべての頂点と孤立した辺で接続され、その後に1つの大きな辺が他のすべての頂点を包み込みます。

3つの極端なハイパーグラフのいずれかをわずかに修正すると、結果は通常、彩色指数も最大になります。つまり、これら3つの例はそれぞれ、長年にわたり数学者によるエルデシュ＝ファーバー＝ロヴァース予想の証明を阻んできた、より広範な難解なハイパーグラフ群を表しています。

数学者がこの予想に初めて遭遇したとき、彼らは各辺に割り当てる色を指定する単純なアルゴリズムや簡単な手順を生成して、それを証明しようとするかもしれません。そのようなアルゴリズムは、すべてのハイパーグラフに適用でき、頂点の数と同じ数の色しか使用しない必要があります。

しかし、3つの極限ハイパーグラフ族は形が大きく異なります。そのため、ある族のハイパーグラフを彩色可能であることを証明する手法は、他の2つの族のハイパーグラフでは通常は適用できません。

「すべての極端なケースを組み込む共通の定理を持つことは非常に難しい」とカン氏は語った。

エルデシュ、ファーバー、ロヴァースはこれら3つの極端なハイパーグラフについては知っていましたが、彩度指数が最大となる他のハイパーグラフが存在するかどうかは知りませんでした。新たな証明は、この次のステップを踏み出します。この証明は、これら3つの例と大きく異なるハイパーグラフは、頂点数よりも少ない色数で表せることを示しています。言い換えれば、これら3つに類似するハイパーグラフは、最も証明が難しいことを証明しています。

「この3つの系統を除外すれば、悪い例はそれほど多くないということがわかるでしょう」とオスタス氏は述べた。「これらのどれにも近すぎなければ、使用する色を大幅に減らすことができます。」

エッジのソート

新たな証明は、1992年にエルデシュ・ファーバー・ロヴァース予想の近似バージョンを証明したラトガース大学のジェフ・カーンによる進歩に基づいている。昨年11月、キューンとオストサス（ともに上級数学者）と3人の博士研究員（カン、ケリー、メトゥク）からなるチームは、予想を完全には解決しなかったものの、カーンの結果を改善しようと試みた。

しかし、彼らのアイデアは予想以上に強力でした。研究を進めるうちに、彼らはその予想を正確に証明できるかもしれないと気づき始めました。

「まるで魔法のようでした」とオスタスは言った。「どういうわけか、私たちのチームがまさにぴったりだったのは本当に幸運でした。」

彼らはまず、与えられたハイパーグラフのエッジを、エッジのサイズ (エッジが接続する頂点の数) に基づいていくつかの異なるカテゴリに分類することから始めました。

このソートの後、彼らはまず最も着色が難しい辺、つまり頂点数の多い辺に着目しました。大きな辺を着色する戦略は、単純化に基づいています。彼らはこれらの辺を通常のグラフ（各辺が2つの頂点のみを繋ぐグラフ）の頂点として再構成し、標準的なグラフ理論から得られた結果を用いて着色し、その着色結果を元のハイパーグラフに戻しました。

「彼らは、自分たちや他の人々が何十年にもわたって開発してきたあらゆる種類のものを取り入れている」とカーン氏は語った。

最も大きな辺を着色した後、彼らは下に向かって作業を進め、グラフの最も小さな辺を最後に残しました。小さな辺は接する頂点が少ないため、着色が容易です。しかし、最後に残しておくことで、ある意味で着色が難しくなります。著者らが小さな辺に辿り着く頃には、利用可能な色の多くが既に他の隣接する辺で使用されていたのです。

これに対処するため、著者らは吸収と呼ばれる組み合わせ論の新しい手法を活用し、最近他の研究者らがさまざまな疑問を解決するためにこの手法を用いている。

「ダニエラとデリックは、この手法を用いて他の有名な問題を検証し、多くの成果を上げています。そして今、彼らのグループはこの手法を用いて[エルデシュ＝ファーバー＝ロヴァース]定理を証明することに成功しました」とカライ氏は述べた。

吸収する色

著者らは、吸収を、彩色に徐々に辺を追加しながら、彩色が常に適切な特性を維持する方法として用いています。これは、多くの小さな辺が単一の頂点に収束する箇所、例えば3番目の極値ハイパーグラフにおいて他のすべての頂点と繋がっている特別な頂点のような箇所を彩色する際に特に有効です。このようなクラスターは利用可能な色のほぼすべてを使用するため、慎重に彩色する必要があります。

そのために、著者らはこれらの扱いにくいクラスターから小さなエッジを集めた貯留層を作りました。そして、残った小さなエッジの多くにランダムな色付け手順（基本的にはサイコロを振って特定のエッジにどの色を適用するかを決める手順）を適用しました。色付けが進むにつれて、著者らは未使用の色を戦略的に選び、それを慎重に選択された方法で確保されたエッジに適用し、色付けに「吸収」していきました。

吸収はランダム着色の効率性を向上させます。エッジをランダムに着色することは、非常に一般的な手順の優れた基盤となりますが、同時に無駄も生じます。すべてのエッジに適用すると、最適な色の組み合わせが得られない可能性が高くなります。しかし、最近の証明では、より正確な方法である吸収をランダム着色に組み込むことで、ランダム着色の柔軟性が緩和されています。

最終的に、グラフの最も大きな辺をある手法で彩色し、次に吸収法などの手法を用いて小さな辺を彩色することで、著者らは、任意の線形ハイパーグラフの辺を彩色するために必要な色の数が頂点の数を超えることはないことを証明することができました。これは、エルデシュ＝ファーバー＝ロヴァース予想が正しいことを証明しています。

確率的要素のため、彼らの証明は十分に大きなハイパーグラフ、つまり特定の数以上の頂点を持つハイパーグラフに対してのみ有効です。このアプローチは組合せ論において一般的であり、数学者は有限個のハイパーグラフのみを省略するため、ほぼ完全な証明であると考えています。

「論文にはノード数が非常に多くなければならないという仮定が残っていますが、それはおそらく追加作業に過ぎないでしょう」とロヴァース氏は述べた。「実質的に、この予想は証明されました。」

エルデシュ＝ファーバー＝ロヴァース予想は、まるでたった一つのグループで議論し、答えを出せるかのような疑問から始まりました。その後数年を経て、数学者たちはこの予想が思ったほど単純ではないことに気づきました。おそらく、3人の数学者もそれを望んでいたのでしょう。お茶を飲みながら数学の問題を解くことよりも素晴らしいことの一つは、最終的な解決に至るまでの過程で、数十年にわたる数学の革新を刺激するような問題を思いつくことです。

「それを証明しようとする努力は、より汎用的な応用が可能な手法の発見を促しました」とカーンは述べた。「これはエルデシュが数学にたどり着いた方法と似ています。」

オリジナルストーリーは、数学、物理科学、生命科学の研究の進展や動向を取り上げることで科学に対する一般の理解を深めることを使命とする、 シモンズ財団の編集上独立した出版物であるQuanta Magazineから許可を得て転載されました。

WIREDのその他の素晴らしい記事