数学者、長年待ち望まれたグラフサンドイッチを構築

ホーム 数学者、長年待ち望まれたグラフサンドイッチを構築 コメント 記事を保存 後で読む シェア Facebook コピー済み！ リンクをコピー メール ポケット Reddit Ycombinator コメント コメント 記事を保存 後で読む 後で読む グラフ理論 数学者、長年待ち望まれたグラフサンドイッチを構築 By Paulina Rowińska 2026年9月18日 数十年前からの予想の証明により、研究者は複雑なネットワークを理解するための新しい方法を得ました。 コメント 記事を保存 後で読む Kristina Armitage/Quanta Magazine はじめに 2004年、2人の数学者が強力な種類のサンドイッチを仮説しました。彼らは、点（頂点と呼ばれる）と線（辺と呼ばれる）の集まりであるグラフを研究していました。 グラフは、ソーシャルグループからインターネット、脳のニューロンまで、あらゆるものを表す可能性があります。 数学者たちは、数学とコンピュータサイエンスで遍在しているが分析が難しい一種のグラフの性質を理解することを望んでいました。それを、数学的に厳密な方法で、2つのより単純なグラフの間に「サンドイッチ」することによってです。 もし研究者がそのようなサンドイッチの存在を証明できれば、それは単に興味深い1つの性質を持つ中間グラフを示しているだけでなく、あらゆる種類の重要な性質を持つことを示していることになります。 そうすることで、彼らはまた、数学者が研究するのが好きな2つの非常に異なるランダムプロセスが、想像していたよりも深くエレガントな方法で接続されていることを実証することになります。 「その概念は非常に美しい」と、この問題に取り組んできたカナダのウォータールー大学の数学者、Pu Gaoは述べています。「私を最も惹きつけるのは、その美しさです。」 過去20年間、数学者は「サンドイッチ予想」を進歩させてきました。これは、関心のあるグラフが十分に大きければ、常に必要なサンドイッチを作成できると述べています。 しかし、誰もそれを完全に証明することはできませんでした。 そして2025年、3人の数学者が、分野の技術を限界まで押し上げる方法を見つけ、この探求を完了しました。 異なる種類のグラフ 1950年代後半、アメリカの数学者Edgar Gilbertは、ベル研究所で電話ネットワークを研究していました。 それらのネットワークをよりよく理解するために、彼は「ランダム」グラフの単純なモデルを考案しました。そこでは、頂点がランダムに他の頂点に接続されます。（数学者のPaul ErdősとAlfréd Rényiは、ほぼ同時期に独立して同様のモデルを考案しました。） これらのグラフの1つを作成するには、頂点のセットから始めます。 セット内の任意の2つの頂点のペアを選択し、(おそらく偏りのある)コインを投げます。 表が出たら、それらの間に辺を描きます。そうでなければ、先に進みます。 グラフ内のすべての頂点のペアに対してこのステップを繰り返します。 これらのランダム二項グラフとして知られるグラフは、有用ではあるが不完全なネットワーク表現方法であることが判明しました。 それらは比較的分析が容易であり、数学者はそれらについて多くの興味深いことを証明しました。 例えば、1970年代までに、ランダム二項グラフがハミルトンサイクル（各頂点を1回だけ訪れるパス）を含む条件を発見していました。 しかし、これはランダムグラフの唯一の種類ではありません。 数学者は、すべての頂点が同じ数の辺を持つランダムグラフにも興味を持っていました。 これらのいわゆる正則グラフは、二項グラフよりもランダム構造の理解を深めます。 そして、それらはしばしば現実世界のネットワークをより正確にモデル化します。 しかし、その辺はより制約された、相互依存的なパターンを形成するため、分析ははるかに困難です。 二項グラフのハミルトンサイクルに関する質問が解決されてからさらに20年かかって、数学者は正則グラフについても同様のことをできるようになりました。 しかし、ランダム正則グラフをランダム二項グラフで近似できるとしたらどうでしょうか？ それが可能であれば、数学者は、対応する二項グラフから正則グラフの証明が難しい多くの性質を「無料」で得ることができます。 2000年代初頭、当時Microsoft ResearchにいたJeong Han Kimと、当時カリフォルニア大学サンディエゴ校にいたVan Ha Vuは、グラフサンドイッチを作成する方法を示しました。 その考えは、大まかに言うと、二項グラフと正則グラフを同時に構築するための単一のレシピ — ランダムプロセス — を見つけることでした。 このレシピは正しい種類のグラフを生成するだけでなく、それらのグラフがちょうど正しい方法で組み合わさる必要があります。 これができれば、分析が比較的容易な二項グラフについて結果を証明すると、それらの結果は正則グラフにも適用されます。 サンドイッチの例えでは、パンのスライスについて証明し、それが真ん中のチーズにも当てはまることを知るようなものです。 しかし、それらのグラフは正確にどのように組み合わさる必要があるのでしょうか？ 各パンのスライスにチーズを重ねるためのレシピを考案する必要があります。 まず、二項グラフを含む正則グラフを提供するレシピが必要です。 つまり、二項グラフの辺は、正則グラフを構成する辺の部分集合を形成します。 もしその二項グラフが辺を追加すると出現しやすくなる性質を持っているなら、あなたの正則グラフもその性質を持つことになります。 これがKimとVuのサンドイッチの下半分です。 Mark Belan/Quanta Magazine 同様に、二項グラフに含まれる正則グラフを提供するレシピが必要です。 もしこのより大きな二項グラフが、辺を削除すると出現しやすくなる性質を持っているなら、あなたの正則グラフもこれらの性質を持たなければなりません。 これがあなたのサンドイッチの上半分です。 KimとVuは、あなたの正則グラフに合理的な数の辺がある限り、このサンドイッチをほぼ常に構築できると予想しました。 あなたのレシピが二項グラフと正則グラフを同時に作成する必要があることを考えると、それは簡単な作業ではありません。なぜなら、それらは通常、まったく異なるランダムプロセスを使用して構築されるからです。 長年にわたり、数学者はKimとVuのサンドイッチの下半分が存在することを証明し、いくつかの設定で上半分を証明しました。 「それはアイデアが互いに積み重なる一連のものだった」と、この問題に取り組んできたテルアビブ大学の数学者、Michael Krivelevichは述べています。 各ステップは「非常に良い技術を必要とします。それは創意工夫を必要とします。」 しかし、サンドイッチはまだ完成していませんでした。 完璧なレシピ 予想の証明には、サンドイッチのパンとチーズを密接に接続する方法が必要でした。 特に、レイヤーは同時に構築され、常に一致することが保証されます。 2023年、3人の数学者 — ウォーリック大学のRichard Montgomery、当時彼のポスドク研究員だったNatalie Behague、そして彼の博士課程の学生だったDaniel Iľkovič — は、ランダム正則グラフとランダム二項グラフを辺ごとに構築する方法を考え始めました。これにより、各ステップで正則グラフが二項グラフを含むことが保証されます。 それは、一度にスライス全体を載せるのではなく、細かく刻んだチーズの小さなビットからサンドイッチを作るようなものです。 Richard Montgomeryは、強力だが作るのが難しい数学的サンドイッチのレシピを作成するのに役立ちました。 Lisa Sauermann 彼らのレシピ（数学者たちは、Gaoと2人の同僚による2019年の結果を大幅に改変したものだと述べています）に従うには、辺のない2つの頂点のセットから始めます。 一方のセットは最終的にあなたの二項グラフになり、もう一方は正則グラフになります。 次に、通常の通りに二項グラフを構築します。 つまり、頂点のペアを選択し、重み付きコインを投げます。 コインが表になったら、二項グラフに辺を追加します。 正則グラフにも1つ追加します。 コインが裏になったら、二項グラフに辺を追加しません。 しかし、正則グラフに辺を追加する必要がある場合も、そうでない場合もあります。 結局のところ、正則グラフは、すべての頂点が同じ数の辺を持つという性質によって定義されます。 すべての必要な辺が存在することを確認する必要があります。 したがって、コインが裏になったら、二項グラフを無視し、2番目の重み付きコインを投げて、正則グラフに辺を追加するかどうかを決定します。 この2番目のコインの重みは変更されます