数学の「サンドイッチ」：複雑なグラフを解く革新的アプローチ

2004 年、二人の数学者が、多岐にわたる現象を表現する**「グラフ」（頂点と辺からなる集合）について、強力な「サンドイッチ」**の概念を提唱しました。 彼らの目的は、数学およびコンピューターサイエンスにおいて普遍的だが解析が難しいグラフの性質を理解することでした。具体的には、以下のアプローチをとりました。

• 手法: 数式的に厳密な方法で、対象となるグラフを二つのより単純なグラフの間にサンドイッチのように挟み込む。
• 意義: サンドイッチとして存在する事を証明できれば、中間にあるグラフが多種多様な重要な性質を備えていることを示せます。
• 発見: 長年研究されてきた二つの異なる確率過程（ランダムプロセス）が、想像を超えたほど深くかつエレガントな結びつきを持っていることを実証します。

カナダ・ウオターロー大学の数学者プ・ガォ氏はこのアイデアについて：

「そのアイデア自体があまりにも美しいものです。私が最も惹かれるのは、まさにその美しさなのです」と語っています。

過去 20 年の間、研究者たちは「サンドイッチ予想」（グラフがいかに大きくなっても必要なサンドイッチを作れるという仮説）の進展を遂げましたが、完全な証明には至りませんでした。2025 年、三人の数学者が分野全体の手法を引き出し、ついにこの探求を完了しました。

---

様々な種類のグラフとその関係性

ランダムグラフの進化

1950 年代末、ベル研究所のエドガー・ギルバーツ氏らは、電話ネットワークを理解しやすくするために**「ランダムグラフ」**のモデルを提案しました（ポール・エルデシュ氏やアルフレード・レーニィ氏も同時期に独立して類似モデルを開発）。

1. ランダム二項分布グラフ

• 構造: 任意の二つの頂点を選び出し、コイン投げで表が出れば辺を引く方式。
  頂点ペア選び -> コイン投げ -> 表なら辺を引く / 裏ならなし (全ペアに繰り返し適用)

• 特徴:
  • 解析が比較的容易で、多くの興味深い事柄（例：ハミルトン閉路を含む条件）が 1970 年代までに解明されました。
  • しかし、完璧なネットワークモデルとしては不十分でした。

2. ランダム正則グラフ

• 構造: 全ての頂点が同じ数の辺を持つグラフ。
• 特徴:
  • ランダム性: 二項分布グラフよりも現実のネットワークに近い「良い理解」を提供します。
  • 解析難易度: 辺が相互依存しているため、解析ははるかに困難です。ハミルトン閉路の問題についてさらに 20 年の研究が必要となり、ようやく解明されました。

サンドイッチのアイデア（近似理論）

ここで重要なのは、**「ランダム正則グラフをランダム二項分布グラフで近似できるかどうか」**という問いでした。

• 成功すれば: 解析が容易な二項分布グラフについて証明された結果から、難問扱いだった正則グラフの性質も自動的に（無料で）得られます。
• 実証者: 2000 年代初頭、マイクロソフトリサーチのジェヨン・ハン・キム氏と、カリフォルニア大学サンディエゴ校のファン・ハ・ヴー氏がこの手法によって実証しました。

具体的な仕組み

両者を同時に生成する**一つの確率過程（レシピ）**を見つけます。このプロセスでは：

1. 単にグラフを生成するだけでなく、生成された二つのグラフが互いに正しい方法で適合し合っていることが必要です。
2. 喩え: 「パンの一枚（容易な側）について証明した結果が、中に入っているチーズ（難しい側）についても成り立つ」状態を作ります。

サンドイッチの構造：下層部分

• 目標: 正則グラフを二項分布グラフで囲む（サンドイッチにする）。
• 方法: 二項分布グラフの辺が、正則グラフの構成する辺の部分集合となるように設計します。
  二項分布グラフの性質 (例：辺を加えると性質が現れやすい) ↓ その性質も自動的に正則グラフに伝播する

• これにより、二項分布グラフで示された「辺を加えることでより現れやすくなる」などの性質が、正則グラフについても保持されます。