Exponential non-isomorphism conjecture for spanning trees of regular graphs

From papers

Let n,d3n,d\geq 3 be integers, and let GG be a connected nn-vertex dd-regular graph. Write Tunlabeled(G)T_{\mathrm{unlabeled}}(G) for the set of isomorphism classes of spanning trees of GG. Exponential spanning-tree conjecture. There exists a universal constant c>0c>0 depending only on dd such that

Tunlabeled(G)ecn.|T_{\mathrm{unlabeled}}(G)|\geq e^{cn}.

The paper proves an analogous result for sufficiently large degree and asks whether the threshold can be reduced to d0=3d_0=3; the conjecture asserts this bound for every d3d\geq3.

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.