Anticoncentration bound for random spanning trees

Conjecture 4.1 · arXiv:2603.17630

arXiv Conjecture high confidence— first stated 2026-03-18

Authors: Veronica Bitonti, Lukas Michel, Alex Scott

Status open high confidence

Conjecture 4.1 asks whether the optimal anticoncentration bound for a uniformly random spanning tree of a connected $n$-vertex graph with minimum degree $d$ is $n^{-(1/2-o_n(1))(d-1)}$, matching the extremal example $K_{d,n-d}$. The source paper proves the weaker bound $n^{-\Omega(d)}$ (confirming a conjecture of Lee), but the precise constant $1/2$ in the exponent remains open. No follow-up paper addressing this sharper bound was found in the literature as of May 2026.

Reviewer notes. The paper 2601.07740 ('Anticoncentration of random spanning trees in almost regular graphs', January 2026) is a closely related predecessor by the same research group but predates the source paper and does not address Conjecture 4.1. No post-March-2026 paper resolving the optimal constant $1/2$ was found. The conjecture is fresh (posted 2026-03-18) and open with high confidence.

Auto-reviewed 2026-05-14 with claude-sonnet-4-6 (web search enabled).

Conjecture. Let $d$ be sufficiently large, and let $n$ be sufficiently large relative to $d$. Suppose that $G$ is a connected graph with $n$ vertices and minimum degree at least $d$, and let $\mathcal{T}$ be a uniformly random spanning tree of $G$. Then, for every tree $T$ it holds that $$\mathbb{P}(\mathcal{T}\cong T)\leq n^{-(1/2-o_n(1))(d-1)}.$$

Context

The authors conjecture that the optimal constant factor in the exponent of the anticoncentration bound should be $1/2$, matching the anticoncentration of a uniformly random spanning tree of $K_{d,n-d}$. For $K_{d,n-d}$, a spanning tree up to isomorphism is determined by a minimal subtree connecting the $d$ vertices in the small class and the number of leaves attached to each of these $d$ vertices.

Notes. The full inequality in the statement was not explicitly reproduced in the extracted theorem block; the bound $n^{-(1/2-o_n(1))(d-1)}$ is inferred from the context text which states the optimal constant should be $1/2$ and that this would match $K_{d,n-d}$.

Source paper

Anticoncentration of random spanning trees in graphs with large minimum degree
Veronica Bitonti, Lukas Michel, Alex Scott · 2026-03-18
https://arxiv.org/abs/2603.17630