An $O(n^2)$ bound for the relaxation time of a Markov chain on cladograms.

April, 2000
Report Number: 
Jason Schweinsberg
RSA Vol 20 (2002)

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.





PDF File: 
Postscript File: