A quadratic ancestor inequality for spanning trees

技术摘要：关于生成树的二次祖先不等式

问题陈述
本文探讨了关于有限和无限图上的均匀生成树 (UST) 以及回路擦除随机游走 (LERW) 的几何性质的基本问题。具体而言，它针对两个开放问题：

1. UST 距离： 在有限传递图中，UST 中两个独立均匀顶点的期望距离是否具有 $\sqrt{n}$ 阶的通用下界（其中 $n$ 是顶点数）。这解决了 Benjamini 和 Kozma (2005) 的一个猜想。
2. LERW 生长指数： 确定三维 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 的最新进展。
• 生成函数： 构建了一个特定的多项式 $Q_B(z)$，它表示对森林 $T \setminus B$（其中 $B$ 是顶点子集）中各连通分量乘积的期望。该多项式被证明是齐次且完全对数凹的。
• 黑塞矩阵分析： 通过分析该多项式在原点处的对数黑塞矩阵（Hessian matrix），作者确立了矩阵 $H_B H_B^T - J_B$ 是半正定的。这里，$H_B$ 与根路径与集合 $B$ 相交的概率有关，$J_B$ 与三个顶点（两个目标点和一个根节点）位于森林中不同连通分量的概率有关。
• 不等式推导： 正定性导出了二次不等式：
  $$\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$ 中的概率。
• 向无限图扩展： 通过“质量生成森林”（带有杀灭率 $m$ 的 UST）并取 $m \to 0$ 的极限，将结果扩展到无限图（特别是 $\mathbb{Z}^3$）。这涉及耦合论证和行列式点过程性质。

主要贡献与结果

1. 二次祖先不等式 (定理 1.1)：
   本文确立了对于任何有限连通图、根 $r$ 和子集 $B$，矩阵 $H_B H_B^T - J_B$ 是半正定的。这意味着对于具有分布 $f$ 的独立随机顶点 $X, Y$，其最近公共祖先位于 $B$ 中的概率被其路径与 $B$ 相交概率的平方所界定：
   $$P(\text{LCAT}(X, Y) \in B) \leq P(\gamma_X \cap B \neq \emptyset)^2$$
   该不等式中的常数 1 被证明是优的。

2. 解决 Benjamini–Kozma 猜想 (定理 1.2)：
   通过将该不等式应用于有限传递图，作者证明了对于具有 $n$ 个顶点的图，UST 中的期望距离 $d_T(X, Y)$ 满足：
   $$\mathbb{E} d_T(X, Y) \geq \sqrt{n} - 1$$
   这证实了期望 UST 距离至少为 $\sqrt{n}$ 阶的猜想，且无需高维或特定模型的假设。

3. 三维 LERW 生长指数的下界 (定理 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 的相交 (定理 5.1)：
   作为生长指数界限的推论，本文证明了两个独立的 $\mathbb{Z}^3$ 无限 LERW 几乎处处无限次相交。

5. 长程 LERW (命题 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 辅助： 作者指出，虽然动机和向不等式的归约是其原创，但主要不等式（定理 1.1）的证明是在 AI 的辅助下完成的，AI 还帮助识别了定理 1.2 是一个推论。作者对数学内容保留全部责任。

本文并未提出新的实验设置或超出文中提到的对长程 LERW 和有线均匀生成森林 (WUSF) 数学扩展之外的未来应用。