Exponential anticoncentration conjecture for random spanning trees

Less than 1 year old · traced to

Let ε>0\varepsilon>0 be real. There is a constant dε>0d_{\varepsilon}>0 such that for every integer d≥dεd\geq d_{\varepsilon}, every connected nn-vertex dd-regular graph GG, and a uniformly random spanning tree T\mathcal{T} of GG, let TT be any nn-vertex tree. Optimal anticoncentration conjecture.

Pr⁡[T≃isoT]≤e−(1−ε)n.\Pr\bigl[\mathcal{T}\simeq_{\mathrm{iso}}T\bigr]\leq e^{-(1-\varepsilon)n}.

The conjecture is motivated by the expected number of copies of a fixed tree in a random graph and is supported for the path by the Brégman–Minc inequality. The stated exponential scale is best possible up to lower-order terms, while extension to suitable (n,d,λ)(n,d,\lambda)-graphs is posed as an additional direction.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.