Polynomial anticoncentration conjecture under a minimum-degree condition

From papers

Let d0,c>0d_0,c>0 be universal constants. For every integer dd0d\geq d_0, let GG be a connected nn-vertex graph with minimum degree at least dd, and let T\mathcal{T} be a uniformly random spanning tree of GG. For every nn-vertex tree TT, Minimum-degree anticoncentration conjecture.

Pr[TisoT]nc.\Pr\bigl[\mathcal{T}\simeq_{\mathrm{iso}}T\bigr]\leq n^{-c}.

This proposes a polynomial anticoncentration bound under the minimum-degree assumption, which is substantially weaker than almost regularity. Complete bipartite graphs show that the paper's stronger exponential conclusions fail under this weaker hypothesis, but the authors note that such graphs still contain polynomially many pairwise non-isomorphic spanning trees.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Hyunwoo Lee, “Anticoncentration of random spanning trees in almost regular graphs”, arXiv:2601.07740 (2026).

Solutions 0

No solutions have been posted yet.