PreprintCC BY 4.0arXiv
A quadratic ancestor inequality for spanning trees
Abstract
We introduce a quadratic ancestor inequality for weighted spanning trees on finite undirected graphs and give two applications. First, for every finite n-vertex transitive graph, the expected distance in its uniform spanning tree (UST) between two independent uniform vertices is at least √n−1, resolving a conjecture in [Benjamini--Kozma, Comm. Math. Phys. 259 (2005), 257--286]. Second, we prove that the growth exponent of three-dimensional loop-erased random walk (LERW) is at least 3/2.
Related
- Spectral radius and edge-disjoint spanning trees of graphs with edge connectivity
- Spanning k-trees and the colorful Carathéodory theorem
- On Hypergraph Colorings and Completely Independent Spanning Trees in Chordal Graphs
- Constructing two completely independent spanning trees in dual-cubes
- Maximum number of spanning trees in bipartite graphs with a given diameter
BibTeX
@misc{cai2026quadratic,
title = {{A quadratic ancestor inequality for spanning trees}},
author = {Gefei Cai},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.22180},
eprint = {2610.22180},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.22180},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A quadratic ancestor inequality for spanning trees
AU - Gefei Cai
PY - 2026
DA - 2026/10/15
PB - arXiv
DO - 10.48550/arxiv.2610.22180
UR - https://arxiv.org/abs/2610.22180
AB - We introduce a quadratic ancestor inequality for weighted spanning trees on finite undirected graphs and give two applications. First, for every finite n-vertex transitive graph, the expected distance in its uniform spanning tree (UST) between two independent uniform vertices is at least √n−1, resolving a conjecture in [Benjamini--Kozma, Comm. Math. Phys. 259 (2005), 257--286]. Second, we prove that the growth exponent of three-dimensional loop-erased random walk (LERW) is at least 3/2.
ER -