Title: An $O(n^2)$ bound for the relaxation time of a Markov chain on cladograms.
Author: Jason Schweinsberg
Date: March 2000 (revised June 2001)
Pub: RSA Vol 20 (2002)
Url: http://www3.interscience.wiley.com/cgi-bin/abstract/88511568/START
Abstract:
A cladogram is an unrooted tree with labeled leaves and unlabeled
internal branchpoints of degree $3$.  Aldous has studied a Markov
chain on the set of $n$-leaf cladograms in which each transition
consists of removing a random leaf and its incident edge from the
tree and then reattaching the leaf to a random edge of the remaining
tree.  Using coupling methods, Aldous has shown that the relaxation
time (i.e. the inverse of the spectral gap) for this chain is
$O(n^3)$.  Here, we use a method based on distinguished paths to
prove an $O(n^2)$ bound for the relaxation time, establishing 
a conjecture of Aldous.