The polynomial lower-bound conjecture for non-isomorphic spanning trees

Let dd be sufficiently large, and let nn be sufficiently large relative to dd. Suppose that GG is a connected graph with nn vertices and minimum degree at least dd.

Non-isomorphic spanning-tree lower-bound conjecture. The number of non-isomorphic spanning trees of GG is at least

Ω(nd1).\Omega(n^{d-1}).

The complete bipartite graph Kd,ndK_{d,n-d} has Ω(nd1)\Omega(n^{d-1}) non-isomorphic spanning trees, motivating this as an essentially optimal lower bound. The preceding sharp anticoncentration conjecture would imply only the weaker lower bound n(1/2on(1))(d1)n^{(1/2-o_n(1))(d-1)}, so the stronger claim remains open.

Sources & referencesView supporting material

Primary source

Veronica Bitonti, Lukas Michel and Alex Scott, “Anticoncentration of random spanning trees in graphs with large minimum degree”, arXiv:2603.17630 (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.