A quadratic ancestor inequality for spanning trees

技術要約：全域木に関する二次的な祖先不等式

問題提起
本論文は、有限および無限グラフにおける一様全域木（UST）およびループ消去ランダムウォーク（LERW）の幾何学に関する根本的な問いに取り組んでいる。具体的には、以下の2つの未解決問題に対処している：

1. USTの距離： 有限な推移グラフにおいて、UST内の2つの独立な一様頂点間の期待距離が、$n$（頂点数）に対して$\sqrt{n}$のオーダーの普遍的な下界を持つか否か。これは、Benjamini and Kozma (2005) による予想を解決するものである。
2. LERW成長指数： 3次元LERWの成長指数$\beta$の厳密な下界の決定。ここで、$\beta = \lim_{R\to\infty} \frac{\log \mathbb{E}|\text{LE}(S[0, \tau_R])|}{\log R}$ と定義される。これまでの境界は1をわずかに上回る程度であった。

手法
本研究の核心は、「二次的な祖先不等式（Quadratic Ancestor Inequality）」と呼ばれる、重み付き全域木のための新しい不等式の導出である。その手法は以下の通りである：

• マトロイド多項式： 著者は、Anari, Liu, Oveis Gharan, Vinzant, および Brändén, Huh による最近の発展である「完全対数凹（completely log-concave）なマトロイド多項式」の理論を利用する。
• 母関数： 頂点集合 $B$ の部分集合に対する、フォレスト $T \setminus B$ の成分に関する積の期待値を表す特定の多項式 $Q_B(z)$ を構成する。この多項式は、完全対数凹であり、かつ斉次であることが示される。
• ヘッセ行列解析： 原点におけるこの多項式の対数のヘッセ行列を解析することにより、行列 $H_B H_B^T - J_B$ が半正定値であることを確立する。ここで、$H_B$ は根へのパスが集合 $B$ と交差する確率に関連し、$J_B$ は3つの頂点（2つのターゲットと根）がフォレスト内の異なる成分に属する確率に関連する。
• 不等式の導出： 半正定値性は、以下の二次不等式をもたらす：
  $$\sum_{x,y} f(x)f(y) a_B(x,y) \leq \left( \sum_x f(x) H_B(x) \right)^2$$
  ここで、$a_B(x,y)$ は $x$ と $y$ の最小共通祖先（LCA）が $B$ に含まれる確率である。
• 無限グラフへの拡張： 結果は、近似（exhaustion）の手法を用いて、無限グラフ（具体的には $\mathbb{Z}^3$）へと拡張される（「質量を持つ全域林（massive spanning forest）」、すなわち殺去率 $m$ を持つUSTを用い、$m \to 0$ の極限を取る）。これには、結合（coupling）議論と決定論的点過程の性質が含まれる。

主要な貢献および結果

1. 二次的な祖先不等式 (Theorem 1.1):
   本論文は、任意の有限連結グラフ、根 $r$、および部分集合 $B$ に対して、行列 $H_B H_B^T - J_B$ が半正定値であることを確立している。これは、分布 $f$ を持つ独立なランダム頂点 $X, Y$ について、それらのLCAが $B$ に含まれる確率が、根へのパス $\gamma_X$ が $B$ と交差する確率の二乗によって抑えられることを意味する：
   $$P(\text{LCAT}(X, Y) \in B) \leq P(\gamma_X \cap B \neq \emptyset)^2$$
   この不等式における定数1は、最適であることが示されている。

2. Benjamini–Kozma予想の解決 (Theorem 1.2):
   有限な推移グラフにこの不等式を適用することで、著者は、$n$ 個の頂点を持つグラフにおいて、USTにおける期待距離 $d_T(X, Y)$ が以下を満たすことを証明した：
   $$\mathbb{E} d_T(X, Y) \geq \sqrt{n} - 1$$
   これにより、高次元やモデル固有の仮定を必要とせずに、期待UST距離が少なくとも $\sqrt{n}$ のオーダーであるという予想が確認された。

3. 3D LERW成長指数の下界 (Theorem 1.3):
   本論文は、$\mathbb{Z}^3$ 上のLERWの成長指数 $\beta$ が $\beta \geq 3/2$ を満たすことを証明している。具体的には、無限のLERW $\eta$ に対して、定数 $c > 0$ が存在して以下が成り立つことを確立した：
   $$\mathbb{E} |\eta \cap B_R| \geq c R^{3/2}$$
   これは、従来の境界（$\beta > 1.0001$）を大幅に改善しており、スケーリング極限のハウスドルフ次元が少なくとも $3/2$ であることを示唆している。

4. 無限LERWの交差 (Theorem 5.1):
   成長指数の下界の帰結として、本論文は、$\mathbb{Z}^3$ 上の2つの独立な無限のLERWが、ほとんど確実に無限に交差することを証明している。

5. 長距離LERW (Proposition 5.3):
   この不等式は、ジャンプ分布 $q(z) \asymp |z|^{-3-\alpha}$ （$3/2 < \alpha < 2$）を持つ $\mathbb{Z}^3$ 上の長距離ランダムウォークにも適用される。成長指数 $\beta_\alpha$ は $\beta_\alpha \in [3/2, \alpha]$ を満たし、$\alpha \downarrow 3/2$ のとき $3/2$ に近づくことが示されている。

意義および主張
本論文は、二次的な祖先不等式が、全域木およびLERWを分析するための強力かつ一般的なツールとして機能することを主張している。

• 最適性： 不等式は鋭い境界として提示されており、定数1は最適である。
• 汎用性： この手法は、マトロイド多項式の完全対数凹性に依存しており、この性質は近似を通じて無限グラフを含む様々なグラフ構造に拡張可能である。
• 未解決問題の解決： 本研究は、推移グラフにおけるUST距離に関するBenjamini–Kozma予想を決定的に解決し、3D LERWの成長指数の下界を、単に1をわずかに上回る状態から $1.5$ へと大幅に改善した。
• AIによる支援： 著者は、動機付けおよび不等式への帰着は自身の考案であるが、主要な不等式（Theorem 1.1）の証明はAIの支援を受けて開発されたこと、また、Theorem 1.2がその系であることを特定する際にもAIが役立ったことを述べている。著者は数学的内容について全責任を負う。

本論文は、言及されている長距離LERWや有線一様全域林（WUSF）への数学的拡張を除き、新しい実験設定や将来的な応用を提案するものではない。