拡大図で無限グラフの「融解」点が明らかに |クアンタマガジン

2008年、数学者のオデッド・シュラムはシアトルから約50マイル東にあるカスケード山脈でのハイキング中の事故で亡くなった。彼はまだ 46 歳でしたが、まったく新しい数学分野を構築しました。

「彼は素晴らしい数学者でした」と彼は言った イタイ・ベンジャミニ、ワイツマン科学研究所の数学者であり、シュラムの友人であり協力者です。 「極めてクリエイティブ、極めてエレガント、極めて独創的。」

彼が尋ねた質問は、今でも確率論と統計物理学の最前線を押し広げています。これらの質問の多くは、相転移、つまり氷が溶けて水になるような突然の巨視的な変化を伴う数学的構造に関するものです。材料が異なれば融点も異なるのと同様に、数学的構造の相転移も異なります。

シュラム氏は、パーコレーションと呼ばれるプロセスにおける相転移は、多くの重要な数学的構造について、システムのクローズアップ ビュー (ローカル パースペクティブと呼ばれる) のみを使用することによって推定できると推測しました。ズームアウトして全体を見ても、計算は大きく変わりません。過去 15 年間、数学者たちはこの予想の小さな部分を少しずつ削り取ってきましたが、今に至るまで完全に解決することはできませんでした。

で XNUMX月にプレプリントを掲載, トム・ハッチクロフト カリフォルニア工科大学の博士課程の学生と フィリップ・イーソ シュラムの局所予想を証明しました。彼らの証明は、確率論やその他の数学分野の主要なアイデアに基づいており、それらを賢い方法で組み合わせました。

「素晴らしい論文ですね。それは長い仕事の積み重ねです」とベンジャミニは語った。

無限のクラスター

「パーコレーション」という言葉はもともと、コーヒーかすの中を流れる水や岩の亀裂から浸透する油など、多孔質媒体を通る流体の動きを指しました。

1957 年、数学者のサイモン ラルフ ブロードベントとジョン マイケル ハマースリーは、この物理プロセスの数学モデルを開発しました。それ以来数十年にわたり、このモデルはそれ自体が研究の対象となってきました。数学者がパーコレーションを研究するのは、パーコレーションが重要なバランスをとるためです。設定は単純ですが、複雑で不可解な機能を示します。

「これは数学者にとっての標準モデルのようなものです」とハッチクロフト氏は言う。 「視覚的に物事を考えることができます。そのため、一緒に仕事をするのは本当に楽しいです。」

パーコレーションは、エッジ (線) で接続できる頂点 (点) の集合であるグラフから始まります。最も単純な例の XNUMX つは、正方形の角を形成するように頂点が並んでおり、その一部をエッジで接続している正方形のグリッドです。

シュラムは死の直前に、グリメットとマーストランドの定理は一般化できると推測しました。彼は、パーコレーションのしきい値は、推移グラフとして知られる大きなクラスのグラフに対するクローズアップ、つまり「顕微鏡的」視点によって完全に決定されると考えました。

2009年にベンジャミニは、 アサフ・ナクミアス および ユヴァル・ペレス 証明 現在知られているように、木に似た特定の種類の推移グラフに対するシュラムの局所性予想。しかし、シュラムは、これがすべての推移グラフ (XNUMX 次元グラフを除く) に当てはまると仮定していました。

推移グラフでは、すべての頂点が同様に見えます。 XNUMX 次元グリッドは一例です。任意の XNUMX つの頂点を選択すると、一方の頂点をもう一方の頂点に移動する対称性を常に見つけることができます。

この関係は、どの推移グラフにも当てはまります。これらの対称性のため、推移グラフの XNUMX つの同じサイズのパッチを拡大して見ると、それらは同じように見えます。このため、シュラムは、数学者がすべての推移グラフのパーコレーションしきい値を計算するには、クローズアップの視点で十分であると考えました。

推移グラフはさまざまな形や形式を取ることができます。正方形、三角形、六角形、またはその他の形状で構成される単純なグリッドにすることができます。あるいは、「3 レギュラー ツリー」のような、より複雑なオブジェクトを形成することもできます。このオブジェクトでは、XNUMX つの中心点が XNUMX つの頂点に接続され、各頂点が分岐して XNUMX つの新しい頂点が無限に作成されます。その最初のいくつかのステップを次に示します。

推移グラフの多様性が、シュラムの局所性予想の証明を困難にする一因となっていました。シュラムの予想からイーソとハッチクロフトの証明までの 15 年間に、数学者のさまざまなグループが特定の種類のグラフについての予想を証明しましたが、彼らのアイデアが一般的なケースに拡張されることはありませんでした。

「あらゆる可能な幾何学の空間は非常に広大で、常に奇妙なものが潜んでいます」とハッチクロフト氏は語った。

レンズを広げる

Easo と Hutchcroft は当初、無限グラフに適用されるシュラムの局所性予想の解決策を探していませんでした。彼らは代わりに、有限グラフ上のパーコレーションを研究していました。しかし、彼らは突然その推測に注意を移す考えを思いつきました。

「私たちはこの新しいツールを思いつき、これは地域性を攻撃するのに役立ちそうだと考えました」とイーソ氏は語った。

この推測を証明するには、顕微鏡の視点からパーコレーション閾値の正確なスナップショットが得られることを示す必要がありました。グラフの一部だけを表示し、接続された大きなクラスターを観察すると、そのグラフには無限のクラスターがあり、したがってパーコレーションのしきい値を超えていると考えるかもしれません。イーソとハッチクロフトはそれを証明しようと試みた。

彼らは「レンズを広げる」と考えられるテクニックに頼っていました。単一の頂点から開始します。次に、ズームアウトして、元のグラフ上で XNUMX つのエッジだけ離れたすべての頂点を表示します。正方形のグリッド上に合計 XNUMX つの頂点が表示されるようになります。再度レンズを広げると、XNUMX つのエッジの距離内にあるすべての頂点が表示され、次に XNUMX つのエッジ、XNUMX つのエッジなどの距離内にある頂点が表示されます。

イーソとハッチクロフトは、大規模なクラスターが発生した場所の近くにリンクがいくつあるかを決定するダイヤルを設定しました。それから彼らはレンズを広げて、その大きなクラスターにますます多くのエッジが集まるのを観察しました。その際、リンクが存在する確率を高める必要がありました。これにより、グラフに大きな連結成分があることを示しやすくなります。これは微妙なバランスをとる行為です。ダイヤルの位置を大幅に変更することなく、無限のグラフ全体を表示できるように、視野をすばやく広げ、ゆっくりとリンクを追加する必要がありました。

彼らは、大きなクラスターが小さなクラスターよりも速く成長することを示すことができました。そのため、イーソ氏が述べたように、「雪玉を転がすときと同じように、クラスターはますます大きくなるにつれて、ますます速く成長します」。

正方形グリッドの場合、頂点数は比較的ゆっくりと増加します。おおよそレンズの二乗に相当する幅です。 10 ステップ後には、約 100 個の頂点が見つかります。しかし、3 つの通常のツリーは指数関数的に速く成長します (およそ 2 をレンズの幅に乗じたもの)。 10 ステップ後には、約 1,024 個の頂点が表示されます。下の図は、最初は正方形のグリッドの頂点の数が多かったにもかかわらず、わずか 3 つのステップで XNUMX レギュラー ツリーが大幅に大きくなる様子を示しています。一般に、グラフはスケールが異なれば成長率も異なる可能性があり、最初は速く、その後は遅くなる可能性があります。

2018年に遡ると、ハッチクロフト 同様のアイデアを使用しました 3 規則ツリーのような急速に成長するグラフの局所性予想を証明します。しかし、正方形グリッドのようなゆっくりとした成長のグラフや、速い成長の数学的基準も遅い成長の数学的基準も満たさない、中程度の速度で成長するグラフでは機能しませんでした。

「ここXNUMX年ほど、物事が本当にフラストレーションを感じているところだ」とハッチクロフト氏は語った。

構造と拡張

さまざまなスケールの成長率を混合したグラフの場合は、さまざまなテクニックを使用する必要があります。

非常に役立つ事実の XNUMX つは、イーソ氏が説明したように、「グラフがある程度のスケールでゆっくりと成長しているように見える場合、そのグラフは行き詰まっている」ということです。今後もより大きな規模でゆっくりと成長していくでしょう。成長の遅いグラフには、群理論と呼ばれる数学の分野によって決定される追加の構造があるため、十分にズームアウトすると、成長の遅いグラフには数学的に飼い慣らされたジオメトリが表示されることも知られていました。

2021年、パリのソルボンヌ大学のセバスチャン・マルティノーはダニエル・コントレラスと協力し、 ヴィンセント・タッション チューリッヒ工科大学は、このプロパティを使用して次のことを行うことができました。 シュラムの局所予想を証明する 最終的にゆっくりと成長するグラフの場合。

この時点で、数学者の XNUMX つのグループは、急速な成長と遅い成長という異なる方向からこの予想に取り組むことに成功しました。しかし、これではかなりのギャップが残りました。まず、イーソとハッチクロフトの手法やコントレラス、マルティノー、タッションの証明ではカバーされていなかった中間成長カテゴリーがあります。もう XNUMX つの問題は、この議論が依然として成長率が変化するグラフには適用されず、速いまままたは遅いままのグラフにのみ適用されることです。コントレラス氏、マルティノー氏、タッション氏の議論を任意のグラフに適用するには、ズームアウトしたときに最終的にジオメトリが大人しく見えるだけでは十分ではなかったとイーソ氏は説明しました。「現在のスケールに近い時点で、ジオメトリが大人しく見えるようにする必要があります。」

辺境の真ん中

中間成長の推移グラフは非常に神秘的です。数学者は、成長がこの範囲に収まる推移グラフの例を見つけたことがありません。存在しない可能性すらあります。しかし、数学者はそれらが存在しないことを証明していないため、シュラムの局所性予想の完全な証明はそれらに対処する必要があります。課題に加えて、Easo と Hutchcroft は、ズームインまたはズームアウトすると成長が速くなったり遅くなったりする場合でも、特定の長さスケールで一時的にしか成長しない可能性があるグラフに対処する必要がありました。

Easo 氏と Hutchcroft 氏は、過去 XNUMX 年の大半を、以前の方法ではカバーされていなかったグラフに適用できるように結果を拡張することに費やしました。

まず、ハッチクロフトが急速に成長するグラフに適用した 2018 年の手法を修正して、さまざまなスケールで成長レベルを変化させるグラフを処理できるようにしました。その後、彼らは成長の遅い案件に取り組みました。 27ページの論文 彼らはXNUMX月にコントレラス、マルティノー、タシオンの取り組みを拡張する内容を共有した。最後に、彼らはXNUMX月のプレプリントで、中間成長のケースを扱うために、ランダムウォーク理論（空間内をランダムに小刻みに動く線）を使用した別の議論を考案しました。三分法が完了したことで、彼らはシュラムの局所予想を証明しました。

「私たちはこの問題に対して、自分たちが知っているすべてを投げかける必要がありました」とハッチクロフト氏は語った。

このソリューションにより、数学者は、パーコレーションしきい値を超えた場合 (無限クラスターの確率が 100% である場合) と、それ以下の場合 (確率 0% である場合) について、より適切な洞察を得ることができます。しかし、数学者たちは、XNUMX 次元グリッドを含むほとんどのグラフのしきい値で正確に何が起こるかに依然として困惑しています。 「これはおそらく、パーコレーション理論における最も有名で最も基本的な未解決の問題です」と彼は言いました。 ラッセル・ライオンズ インディアナ大学の。

3 次元グリッドは、数学者がしきい値で正確に何が起こるかを証明した数少ないケースの XNUMX つであり、無限のクラスターは形成されません。そして、グリメットとマーストランドが大きなスラブの局所性予想のバージョンを証明した後、グリメットと共同研究者は、XNUMXD グリッドを水平方向に半分にスライスして床を作成し、ダイヤルをパーコレーションのしきい値に正確に調整すると、無限クラスターは表示されないことを示しました。彼らの結果は、完全な XNUMX 次元グリッドは、XNUMX 次元の対応物と同様に、パーコレーション閾値で無限のクラスターを持たない可能性があることを示唆しています。

1996年、ベンジャミニとシュラム 推測された しきい値のすぐ近くで無限クラスターが見つかる確率は、すべての推移グラフでゼロです。これは、2D グリッドや半分にスライスされた 3D グリッドの場合と同様です。局所性の推測が解決されたので、移行点で何が起こるかの理解が少し近づいたかもしれません。

訂正： 2023 年 12 月 18 日
3 規則的なグラフ上の開始ノードの n リンク内のノードの数は、およそ 2 に増加します。ⁿ、3ではないⁿ この記事が最初に述べたように。記事は修正されました。

クアンタ では、視聴者により良いサービスを提供するために一連のアンケートを実施しています。 私たちのものを取ってください 数学読者アンケート そしてあなたは無料で当選するためにエントリーされます クアンタ マーチ。