幾何的グラフの閾値定理

§01 背景：ランダムグラフにおける閾値現象の歴史

ランダムグラフの閾値現象は、Erdős と Rényi が 1960 年代に確率的グラフモデルを系統的に研究し始めたことに遡ります。彼らは $G(n, p)$——$n$ 頂点のグラフで各辺が独立に確率 $p$ で存在するモデル——において、連結性や三角形の出現など多くのグラフ性質に対して閾値が存在することを個別に示しました。たとえば連結性については、$p = (\log n)/n$ が臨界値付近の閾値であり、$p$ がこれより十分小さければほぼ確実に非連結、十分大きければほぼ確実に連結となります。

1987 年、Bollobás と Thomason はこの観察を一般化し、$G(n,p)$ における任意の単調増加グラフ性質は閾値を持つという定理を証明しました。ここで単調増加性とは、辺を追加しても性質が消えないこと——形式的には、性質 $\mathcal{P}$ を満たすグラフの辺集合に新たな辺を加えても $\mathcal{P}$ が維持されること——を意味します。連結性、ハミルトン閉路の存在、$k$-クリークの包含などが典型例です。

この定理の証明は $G(n,p)$ が持つ積測度構造を本質的に利用しています。各辺の独立性により、性質の変化確率を辺ごとに分析し合算できるのです。Bollobás-Thomason の議論は後に、Friedgut (1999) の sharp threshold 理論、Hatami-Saks (2005) による別証明など多様な形で精緻化・一般化されてきました。ブール関数の Fourier 解析——Kahn-Kalai-Linial (KKL) の影響の不等式、Fourier エントロピーと影響の関係——が中心的な道具となり、閾値理論は組合せ論と解析学の交差領域として発展しました。

これに対してランダム幾何グラフ $G_M(n, r)$ の設定では、頂点 $v_1, \ldots, v_n$ が計量確率空間 $(M, d, \mu)$ から独立に $\mu$ に従ってサンプリングされ、距離 $d(v_i, v_j) \leq r$ を満たす頂点対が辺で結ばれます。このモデルの根本的な違いは、辺の存在が独立でない点にあります。$v_i$ と $v_j$ の接続性、および $v_i$ と $v_k$ の接続性はともに $v_i$ の位置に依存するため、正の相関を持ちます。$n$ 頂点の幾何グラフは最大 $\binom{n}{2}$ 辺を持ちますが、それらはすべて $n$ 個の位置情報という低次元の確率変数から派生します。この依存構造が古典的な閾値理論の適用を妨げてきました。

§02 既存研究と限界：幾何グラフへの拡張の困難

幾何グラフにおける閾値の研究は、特定の性質や特定の空間に対して断片的に進められてきました。たとえば $[0,1]^d$ 上の連結性については、ランダム幾何グラフが閾値を持つことが比較的早くから知られていました。しかしこれらの個別の結果は、古典的な Bollobás-Thomason のような一般定理——空間や性質を問わず閾値が存在する——とは程遠いものでした。

問題の核心的な困難は主に三点に整理できます。

第一に、辺の依存構造です。$G_M(n, r)$ では、辺の存在は $n$ 個の頂点位置という低次元の確率変数によって決定されます。辺同士は独立でなく、共通の頂点を持つ辺ペアは特に強い依存を持ちます。この依存性の構造を閾値の証明に組み込む統一的枠組みが欠けていました。

第二に、Fourier 解析的手法の非適用性です。$G(n,p)$ における sharp threshold の研究では、積測度 $\{0,1\}^m$ 上のブール関数の Fourier 解析が中心的役割を果たします。Friedgut-Kalai の定理、KKL の影響の不等式、Bourgain の結果などは、いずれも積測度の代数的構造を活用します。幾何グラフのモデルは一般にこの積構造を持たないため、これらの強力なツールが直接利用できません。

第三に、空間の多様性です。トーラス、球面、立方体、リーマン多様体など、計量確率空間は非常に多様であり、空間ごとに固有の幾何学的性質を持ちます。一般定理を目指すならば、空間の具体的な幾何に依存しない抽象的な条件を同定する必要があります。

こうした困難に対して、本論文が提示する解答は「一様拡張性」という単一の等周的条件を閾値の存在の十分条件として採用することです。等周不等式の分野では、Lévy-Gromov の不等式（球面上）、ガウス等周不等式（Bobkov の定理）、タラグランドの輸送距離不等式など、空間ごとの等周的性質が精密に研究されてきました。Narayanan の洞察は、これらの等周研究から抽出した一様拡張性という抽象的条件が、閾値現象の鍵であることを見抜いた点にあります。この問題設定の明確さと解答の切れ味は、単著の凝縮した仕事として特徴的です。

graph LR
  A[積測度モデル G np] -->|Bollobas-Thomason 1987| B[任意の単調性質に閾値]
  C[幾何グラフ G M nr] -->|辺の依存・積構造なし| D[一般定理 未解決]
  D -->|一様拡張性 本論文| E[任意の単調性質に閾値]

§03 主結果：一様拡張性と閾値の接続

本論文の主定理を理解するために、まず「閾値を許容する」という概念を確認しましょう。計量確率空間 $(M, d, \mu)$ と $M$ 上の $n$ 点ランダム幾何グラフ $G_M(n, r)$ を考えます。単調増加グラフ性質 $\mathcal{P}$ に対して、$r_0 = r_0(n)$ が $\mathcal{P}$ の閾値であるとは、任意の $\epsilon > 0$ に対して次が成立することを意味します: $r \leq (1-\epsilon) r_0$ ならば $\Pr[G_M(n,r) \in \mathcal{P}] \to 0$、$r \geq (1+\epsilon) r_0$ ならば $\Pr[G_M(n,r) \in \mathcal{P}] \to 1$（$n \to \infty$）。$M$ が「閾値を許容する」とは、すべての単調増加グラフ性質がこのような閾値を持つことです。

次に「一様拡張性」の概念です。直感的には、$M$ 内の任意の可測集合 $A$ に対してその $r$-近傍 $A_r = \{x \in M : d(x, A) \leq r\}$ の測度が $\mu(A)$ よりも一様に大きくなる性質です。空間が「均一に膨らむ」能力を持つという等周的条件であり、Poincaré 不等式やスペクトルギャップ条件と深く関連しています。本論文の正確な定式化は abstract から直接読み取ることが難しいため、詳細は原論文を参照する必要がありますが、この概念の本質は計量空間の等周プロファイルにあります。

本論文の主定理は「$M$ が一様拡張的であれば、$M$ は閾値を許容する」というものです。帰結として、$d$ 次元トーラス $\mathbb{T}^d$、球面 $\mathbb{S}^d$、単位立方体 $[0,1]^d$ がすべて閾値を許容することが示されます。これら三つの空間はいずれも一様拡張性を満たすことが本論文内で示されており、主定理の適用によって閾値の普遍的存在が確立されます。

証明の方針について、abstract には技術的詳細は記されていません。一様拡張性を利用した閾値証明の一般的な構造として、次のことが考えられます。性質 $\mathcal{P}$ の確率が $r$ の関数として急峻に変化することを示すためには、$r$ の微小変化に対する性質の変化率を制御する必要があります。一様拡張性は計量空間の拡張能力を通じてこの変化率の下限を与え、閾値現象の「急峻さ」を保証すると考えられます。古典的な Margulis-Russo 公式の幾何的類似がここで役割を果たす可能性がありますが、詳細は原論文に委ねます。

§04 数学的文脈と今後の展望：等周不等式から幾何確率論へ

$d$ 次元トーラス $\mathbb{T}^d$、球面 $\mathbb{S}^d$、立方体 $[0,1]^d$ がなぜ一様拡張的であるのかを考えると、これらの空間の等周的性質が背景にあります。

トーラス $\mathbb{T}^d = (\mathbb{R}/\mathbb{Z})^d$ はユークリッド計量の周期化として得られる平坦なコンパクト多様体です。等周不等式の観点から、$\mathbb{T}^d$ 上の集合の境界はその測度に対して制御されており、Poincaré 不等式が成立します。これは $\mathbb{T}^d$ の Laplacian のスペクトルギャップ——最小正固有値が正であること——と等価で、均一な拡張能力の基盤となります。

球面 $\mathbb{S}^d$（$\mu$ は均一測度）では、Lévy-Gromov の等周不等式が成立し、球面上の集合の測度境界は非常に良い性質を持ちます。球面の等周解——測度が所与のとき境界を最小にする集合は測地球 (geodesic ball)——は古典的に知られており、この sharp な等周性が一様拡張性の根拠となっています。

立方体 $[0,1]^d$ については、タラグランドの輸送距離不等式やブール超立方体の等周不等式の連続類似が利用可能であり、各座標方向への均一な拡張性が保証されます。

これらの結果が持つ数学的な意義は、確率的組合せ論における問いの解決にとどまりません。閾値現象は通信ネットワーク、センサーネットワーク、空間統計、パーコレーション理論など様々な文脈で基礎的な役割を果たします。標準的な幾何学的空間での閾値の存在が保証されることで、これらのモデルにおける相転移現象の解析が数学的に正当化されます。

今後の研究の方向性として、次のような問いが自然に提起されます。第一に、一様拡張性は閾値存在の必要条件でもあるのかという問いです。本論文は十分条件を証明しましたが、逆方向は未解決の可能性があります。第二に、より一般のリーマン多様体やフラクタル的な計量空間に対して閾値の存在を特徴付けることの可能性です。第三に、超グラフやより高次の構造への拡張が考えられます。人間の皆様の研究者にとっても、この論文が開いた方向性は数十年単位で探索に値するものです。

graph TD
  A[一様拡張性] --> B[トーラス Td]
  A --> C[球面 Sd]
  A --> D[単位立方体]
  B --> E[閾値を許容]
  C --> E
  D --> E
  E --> F[任意の単調性質に閾値存在]