Aldous’s mixing-time conjecture for the cladogram chain

For each $n\ge 3$ , let $\mathcal{C}_n$ be the set of unrooted binary trees with leaves labelled by $\{1,\ldots,n\}$ . Consider the Markov chain that, at each step, removes a uniformly random leaf, suppresses the resulting degree-two vertex, and reattaches the leaf by subdividing a uniformly random edge. Aldous's conjecture is that the total-variation mixing time $t_{\mathrm{mix}}(n)$ of this chain satisfies $t_{\mathrm{mix}}(n)=\Theta(n^2)$ ; equivalently, there exist constants $0<c<C<\infty$ and $n_0$ such that $c n^2\le t_{\mathrm{mix}}(n)\le C n^2$ for all $n\ge n_0$ .

References

Primary source

arXiv

Additional references

The Aldous chain on cladograms mixes in order n^2 steps — arXiv — Valentin Féray, Lucas Teyssier

Posted 3 weeks ago · edited 3 weeks ago

Progress summary

Refreshed 3 weeks ago

Claimed solved

A September 2026 unrefereed preprint claims to settle the conjecture, but independent verification has not yet appeared.

Aldous conjectured that the cladogram chain mixes in quadratic time, after establishing only bounds between quadratic and cubic time in work published on May 1, 2000.

Known results

Aldous, 2000: proved a lower bound of order $n^2$ and an upper bound of order $n^3$ , and conjectured the matching $n^2$ scale.
Löhr, Mytnik, and Winter, 2020: constructed the associated continuum diffusion and established its Feller and invariant-distribution properties; this does not resolve the quantitative mixing conjecture.

September 2026 claimed solution

Valentin Féray and Lucas Teyssier claim that a multi-subtree coupling and a drift statistic prove matching-order mixing, namely order $n^2$ . The result is currently supported only by their unrefereed preprint and remains unverified.

Current status (as of September 2026): The conjecture has a claimed $n^2$ -order solution in an unrefereed preprint, but its correctness remains unverified.

Sources

No solutions have been posted yet.