🔢 mathematics

A quadratic ancestor inequality for spanning trees

This paper introduces a quadratic ancestor inequality for weighted spanning trees and applies it to prove that the expected distance between two random vertices in the uniform spanning tree of any finite transitive graph is at least $\sqrt{n}-1$ , as well as to establish that the growth exponent of three-dimensional loop-erased random walk is at least 3/2.

Original authors: Gefei Cai

Published 2026-10-16

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Gefei Cai

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a vast, invisible forest growing on a network of points and lines. In the world of mathematics, this is not a collection of trees with leaves and bark, but a structure called a spanning tree. It is a way of connecting every single point in a network to every other point using the fewest possible lines, without ever forming a closed loop. These structures appear everywhere in science, from the wiring of electrical grids to the way information flows through the internet. But when these networks are random, and the connections are chosen by chance, a deep mystery arises: how far apart are two points when you travel along the unique path that connects them inside this random tree? For decades, mathematicians have wondered if there is a universal rule governing this distance, a rule that holds true no matter how complex or large the network becomes.

The question is particularly pressing for networks that look the same from every point, known as transitive graphs. In such a network, if you pick two random spots and ask how many steps it takes to walk from one to the other along the random tree, the answer seems to depend on the size of the whole network. A specific conjecture suggested that this average distance should grow at least as fast as the square root of the total number of points. If the network has one million points, the average trip should be at least one thousand steps. Proving this has been a stubborn challenge, requiring tools that could handle the intricate, probabilistic nature of these random forests.

A researcher named Gefei Cai has now solved this problem by introducing a new mathematical tool, a "quadratic ancestor inequality." To understand what this tool does, imagine looking at a random tree and picking a specific point as the starting place, or root. Every other point in the tree has a unique path leading back to this root. If you pick two other points, their paths will eventually merge at a single point where they first meet on the way to the root. This meeting point is called their lowest common ancestor. The new inequality provides a strict rule about how likely it is for these ancestors to fall into a specific group of points. It states that the probability of two random points sharing an ancestor in a certain area is always less than or equal to the square of the probability that a single random point's path passes through that same area.

This rule might sound abstract, but it acts like a powerful lever. By applying this inequality to the problem of random trees on transitive graphs, Cai was able to prove the long-standing conjecture. The result is definitive: for any finite network where every point looks the same, the average distance between two random points in the uniform spanning tree is indeed at least the square root of the total number of points, minus one. This confirms that the distance grows in a predictable, substantial way, resolving a question that had remained open since 2005. The proof relies on a sophisticated area of mathematics involving polynomials and the properties of random structures, but the outcome is a clear, concrete fact about the geometry of random networks.

The implications of this discovery extend far beyond just measuring distances. The same mathematical machinery was used to investigate the behavior of a process called loop-erased random walk. This process involves a particle wandering randomly through a three-dimensional grid, but with a twist: whenever the particle visits a spot it has already been to, the loop it just completed is erased, leaving behind a clean, non-intersecting path. Scientists have long been trying to determine the "growth exponent" of this path, a number that describes how the length of the path increases as the particle wanders further out.

Using the new inequality, Cai proved that in three dimensions, the length of this path grows at least as fast as the distance raised to the power of 1.5. This means that as the path extends, it becomes significantly longer than a simple straight line, but not as tangled as a fully space-filling curve. This finding establishes a firm lower bound for the growth exponent, settling a debate about how these paths behave in three-dimensional space. It also leads to a surprising conclusion about two such paths starting from different places: they will almost certainly cross each other infinitely many times as they wander through the infinite grid.

The work also sheds light on what happens when the rules of the random walk are changed to allow for longer jumps. In these scenarios, the growth of the path is still governed by similar principles, with the length growing at least as fast as the square root of the distance, provided the jumps are not too extreme. The paper does not just offer a new number; it provides a robust framework for understanding how randomness shapes structure. By establishing a fundamental inequality that links the geometry of trees to the probabilities of their paths, the research offers a new lens through which to view the hidden order within chaotic systems. The results are not simulations or guesses; they are rigorous proofs that hold true for any network fitting the described conditions, offering a solid foundation for future exploration in probability and statistical physics.

Technical Summary: A Quadratic Ancestor Inequality for Spanning Trees

Problem Statement
The paper addresses fundamental questions regarding the geometry of uniform spanning trees (UST) and loop-erased random walks (LERW) on finite and infinite graphs. Specifically, it targets two open problems:

UST Distance: Whether the expected distance between two independent uniform vertices in the UST of a finite transitive graph admits a universal lower bound of order $\sqrt{n}$ , where $n$ is the number of vertices. This resolves a conjecture by Benjamini and Kozma (2005).
LERW Growth Exponent: Determining a rigorous lower bound for the growth exponent $\beta$ of three-dimensional LERW, defined as $\beta = \lim_{R\to\infty} \frac{\log \mathbb{E}|\text{LE}(S[0, \tau_R])|}{\log R}$ . Previous bounds were only slightly above 1.

Methodology
The core of the work is the derivation of a new inequality for weighted spanning trees, termed the Quadratic Ancestor Inequality. The methodology proceeds as follows:

Matroid Polynomials: The author utilizes the theory of completely log-concave matroid polynomials, a recent development by Anari, Liu, Oveis Gharan, and Vinzant, and Brändén and Huh.
Generating Functions: A specific polynomial $Q_B(z)$ is constructed, representing the expectation of a product over components of the forest $T \setminus B$ (where $B$ is a subset of vertices). This polynomial is shown to be homogeneous and completely log-concave.
Hessian Analysis: By analyzing the Hessian matrix of the logarithm of this polynomial at the origin, the author establishes that the matrix $H_B H_B^T - J_B$ is positive semidefinite. Here, $H_B$ relates to the probability that a root path intersects a set $B$ , and $J_B$ relates to the probability that three vertices (two targets and the root) lie in distinct components of the forest.
Inequality Derivation: The positive semidefiniteness yields the quadratic inequality:
$\sum_{x,y} f(x)f(y) a_B(x,y) \leq \left( \sum_x f(x) H_B(x) \right)^2$
where $a_B(x,y)$ is the probability that the lowest common ancestor (LCA) of $x$ and $y$ lies in $B$ .
Extension to Infinite Graphs: The results are extended to infinite graphs (specifically $\mathbb{Z}^3$ ) via the "massive spanning forest" (a UST with a killing rate $m$ ) and taking the limit as $m \to 0$ . This involves coupling arguments and determinantal point process properties.

Key Contributions and Results

The Quadratic Ancestor Inequality (Theorem 1.1):
The paper establishes that for any finite connected graph, root $r$ , and subset $B$ , the matrix $H_B H_B^T - J_B$ is positive semidefinite. This implies that for independent random vertices $X, Y$ with distribution $f$ , the probability that their LCA lies in $B$ is bounded by the square of the probability that the path from $X$ to $r$ intersects $B$ :
$P(\text{LCAT}(X, Y) \in B) \leq P(\gamma_X \cap B \neq \emptyset)^2$
The constant 1 in this inequality is shown to be optimal.
Resolution of the Benjamini–Kozma Conjecture (Theorem 1.2):
Applying the inequality to finite transitive graphs, the author proves that for a graph with $n$ vertices, the expected distance $d_T(X, Y)$ in the UST satisfies:
$\mathbb{E} d_T(X, Y) \geq \sqrt{n} - 1$
This confirms the conjecture that the expected UST distance is at least of order $\sqrt{n}$ without requiring high-dimensional or model-specific assumptions.
Lower Bound for 3D LERW Growth Exponent (Theorem 1.3):
The paper proves that the growth exponent $\beta$ for LERW on $\mathbb{Z}^3$ satisfies $\beta \geq 3/2$ . Specifically, it establishes that for the infinite LERW $\eta$ , there exists a constant $c > 0$ such that:
$\mathbb{E} |\eta \cap B_R| \geq c R^{3/2}$
This improves upon previous bounds (which were $\beta > 1.0001$ ) and implies that the Hausdorff dimension of the scaling limit is at least $3/2$ .
Intersection of Infinite LERWs (Theorem 5.1):
As a consequence of the growth exponent bound, the paper proves that two independent infinite LERWs on $\mathbb{Z}^3$ intersect infinitely often almost surely.
Long-Range LERW (Proposition 5.3):
The inequality is applied to long-range random walks on $\mathbb{Z}^3$ with jump distribution $q(z) \asymp |z|^{-3-\alpha}$ (for $3/2 < \alpha < 2$ ). The growth exponent $\beta_\alpha$ is shown to satisfy $\beta_\alpha \in [3/2, \alpha]$ , approaching $3/2$ as $\alpha \downarrow 3/2$ .

Significance and Claims
The paper claims that the Quadratic Ancestor Inequality serves as a powerful, general tool for analyzing spanning trees and LERWs.

Optimality: The inequality is presented as a sharp bound, with the constant 1 being optimal.
Generality: The method relies on the complete log-concavity of matroid polynomials, a property that extends to various graph structures, including infinite graphs via exhaustion.
Resolution of Open Problems: The work definitively answers the Benjamini–Kozma conjecture regarding UST distances on transitive graphs and provides a significant improvement on the lower bound for the 3D LERW growth exponent, moving it from just above 1 to $1.5$.
AI Assistance: The author notes that while the motivation and the reduction to the inequality were their own, the proof of the main inequality (Theorem 1.1) was developed with the assistance of AI, which also helped identify Theorem 1.2 as a corollary. The author retains full responsibility for the mathematical content.

The paper does not propose new experimental setups or future applications beyond the mathematical extensions to long-range LERWs and wired uniform spanning forests (WUSF) mentioned in the text.

More like this