数学者がグラフの構造を予測する新しい方法を発見 | クアンタマガジン

今年は、組み合わせ論の研究において刺激的な年でした。 2023 年初頭、数学者たちは次のような衝撃を受けました。 のXNUMX 　 最大の問題 現場の問題は数か月で解決されました。 さて、14番目の大きな問題は、「まったく正しいアイデアが含まれている」XNUMXページの証明で落ちた、と述べた。 メータブ・ソーニー マサチューセッツ工科大学の教授は、「まったく衝撃的だ」と付け加えた。

この質問は、いわゆるラムゼー数、つまり起こり得る無秩序の限界を反映する基本的な量を扱っています。 これらの数値は、グラフと呼ばれる頂点とエッジの集合がパターンや構造を必然的に生み出す前に達成できるサイズを測定します。

数学者たちは、特定が難しいことで知られるラムゼー数をほぼ XNUMX 世紀にわたって研究してきました。 そうすることで、彼らはグラフ理論を超えた、数理論や暗号学などのさまざまな分野の進歩につながる技術を開発してきました。

しかし新たな証拠は、 今月初めにオンラインで投稿された、これらのテクニックからの脱却を示します。 これは、40 年以上進歩を妨げられてきた問題を解決するだけでなく、数学者が今後どのようにラムゼー問題に取り組むかについての新しいロードマップも示します。

パーティープランニングとグラフ理論の融合

ラムジー数とは何かを理解するために、パーティーを主催していると想像してください。

全員がお互いを知っているグループ、または全員が知らないグループを確実に作成するには、何人を招待する必要がありますか? この質問はグラフの言語でエンコードできます。 各人に頂点を割り当てます。 ために n 皆さん、分かりますか n 頂点。 すべての頂点のペアをエッジで接続します。 問題の人々がお互いを知っている場合はエッジを赤に色付けし、見知らぬ人である場合は青に色付けします。

共通の知人または見知らぬ人のグループは、クリークと呼ばれる構造、つまり同じ色のエッジで接続された一連の頂点によって表されます。 ラムジー数 r(s, t) は、複数のグループが含まれることを避けるために招待する必要がある最小人数です。 s 知人や t 見知らぬ人 — グラフ理論の言葉で言えば、サイズの赤い集団 s または、ある程度のサイズの青いクリーク t.

たとえば、私たちはそれを知っています r(4, 5) = 25。つまり、24 人の共通の知人や XNUMX 人の見知らぬ人のグループを含めずに、お互いに知り合いもいる XNUMX 人でパーティーを主催することができます。 ただし、もう XNUMX 人追加すると、これらの構造の少なくとも XNUMX つを作成することは避けられません。

今年初期の組み合わせ論のブレークスルーの XNUMX つは、赤と青のクリークが同じサイズである「対称」ラムゼー数のより厳しい上限を与えました。 新しい結果の主題である非対称ラムゼー数を使って、数学者は赤いクリークのサイズを固定し、青いクリークのサイズが任意に大きくなると何が起こるかを尋ねます。

数学者が正確に計算できたのは、最も小さなラムゼー数のほんの一握りだけです。 彼らはそれを証明した r4 年では (5, 25) = 1995。しかし、その値は誰も知りません。 r(4、6)。 同様に、1980 年代初頭には、 彼らは示した それ r(3, 9) = 36 ですが、 r(3, 10) は未解決の問題のままです。 (対称の場合も同様に困難です。 r(4) = 18 ですが、次の値は r(5)は不明です。)

そこで数学者は代わりにラムゼー数を推定しようとし、その値の上限と下限を考え出します。

1990 年代に、彼らはグラフをランダムに生成する技術を使用して、赤いクリークが 3 に固定され、青のクリークがどんどん大きくなると、ラムゼー数のサイズは青のクリークのサイズの XNUMX 乗に応じて増大することを証明しました。 言い換えると、 r（3、 t) 約です t².

新しい証明は、赤いクリークのサイズが 4 ではなく 3 に設定された場合に何が起こるかを尋ねます。1930 年代には、次のことが確立されました。 r（4、 t) 成長速度は周囲より速くありません t³。 しかし、1970 年代に発見された最良の下限は、 t^5/2 — かなり小さい。

下限を上げたり、上限を下げたりしてギャップを埋めようとする試みは、二人の数学者が重要な要素を追加するまで、数十年にわたって失敗に終わりました。

平野に隠れて

2019年には、 サム・マテウス当時、ブリュッセル自由大学 (VUB) の大学院生がインスピレーションを求めていました。 彼の専門知識は有限幾何学、つまり特別に定義された空間における点、線、その他の構造の配置の研究でした。 しかし、彼はこの仕事が興味深いと感じたにもかかわらず、これらの幾何学的な構造がどれほど厳密で正確でなければならないかという制約を感じていました。

それから彼は見た 紙 二人の数学者によって、 ドゥルブ・ムバイ イリノイ大学シカゴ校の ジャック・フェルストレート カリフォルニア大学サンディエゴ校の博士。 彼らはラムジーの問題にどのようにアプローチするかを再考していました。 従来の手法では、ラムゼー数を適切に推定するためにグラフをランダムに生成する必要がありましたが、Mubayi と Verstraete は、ランダムに見えて実際はそうではない「疑似ランダム」構築から始めました。

マテウスの中で何かがピンと来た。 おそらく、彼の幾何学的な視点が役立つかもしれないと彼は考えました。 卒業研究を終えるまでの数年間、彼はこの考えを頭の片隅に置き続けました。 その後、彼はフルブライトのフェローシップに応募しました。これにより、米国でフェルストレート博士のもとでポスドクを目指すことが可能になります。

2022 年、マテウスがフルブライト賞を受賞した直後、 別の交わり）、彼は UCSD に移り、Verstraete と協力し始めました。 r（4、t）。 数学者たちは、既知の上限を満たすために下限を引き上げたいと考えました。 そのためには、ほぼ次のようなグラフを見つける必要があります。 t³ サイズ 4 の赤いクリークまたはサイズ XNUMX の青いクリークが存在しない頂点 t.

証明を機能させるために、彼らは問題を再定式化しました。 すべての青いエッジを単純に削除することを想像してください。 ここでの目標は、サイズ 4 の赤いクリークがなく、独立したサイズのセットもないグラフを見つけることになります。 t (つまり、次のセット t エッジのない頂点)。

Mubayi と Verstraete の 2019 年の研究は、サイズ 4 の赤いクリークなしで擬似ランダム グラフを構築できれば、そのランダムな部分を取り出して、大きな独立集合を持たずに小さなグラフを取得できることを示唆しています。 これはまさにマテウスとフェルストレーテが見つけたかったものでした。 さらに大きなグラフから始めることで、彼らはほぼ次のようなグラフを見つけることを望んでいました。 t³ 基準を満たす頂点。 「これらのグラフの中に、より優れたラムジーのグラフが隠されています」とフェルストレート氏は語った。

問題は、まず適切な擬似乱数の構築を見つけ出すことでした。

数学者たちは、いくぶん回りくどい方法でそこにたどり着く必要がありました。 彼らは擬似ランダムグラフから始まったわけではありません。 彼らはグラフから始まったわけではありません。

代わりに、マテウスはエルミート ユニタルと呼ばれる奇妙な物体を思い出しました。これは有限幾何学者にはよく知られているものですが、組み合わせ論を研究する数学者が遭遇する可能性は低いものです。

エルミート ユニタルは、曲線上の特別な点のセットと、特定の構成でそれらの点を通過する線です。 重要なのは、多くの大きな、しかしほとんど重なり合っていないクリークで構成されるグラフとしても表現できることです。

このグラフはよく知られており、その特性の多くが研究されています。 しかし、それはラムジー問題の文脈で考慮されたことはなかった。 「これはこの有限幾何学ビジネスに非常に特有のものです」とマテウス氏は言います。

このグラフには大きなクリークが多数含まれているため、一見すると役に立たないように見えるかもしれません。 しかし、エルミート ユニタルの重要な特徴は、頂点が異常な方法でクラスター化されたサイズ 4 のクリークのみを含むことです。 この性質のため、数学者はエッジをランダムに削除することで不要なクリークを破壊することが比較的簡単でした。

これらの削除により、サイズ 4 のクリークのない新しいグラフが得られましたが、それでも大きな独立したセットが含まれていました。 Mattheus と Verstraete は、このグラフが擬似ランダムであることを証明する必要がありました。 そうすることで、彼らはついに 2019 年のプルーフを希望通りに使用することができました。 彼らはランダムな部分グラフを取得しました t³ 頂点を定義し、それらのサブグラフに独立したサイズのセットがないことを保証できます。 t.

これで証明が完了しました。 「この構造は本当に美しいです」とソーニー氏は語った。

この研究は、ラムジー問題に対する数学者の考え方の変化を告げるものです。 「ランダム性を利用して物事を押し進め、可能な限り良好な境界を達成しようとするのは、非常に自然なことです。」と彼は言いました。 デビッドコンロン カリフォルニア工科大学の博士。 「しかし、これが実際に示しているのは、ランダムでは限界までしか到達できないということです。」