Random Walks on Trees and Matchings

We give sharp rates of convergence for a natural Markov chain on the space of phylogenetic trees and dually for the natural random walk on the set of perfect matchings in the complete graph on $2n$ vertices. Roughly, the results show that (1/2) n log n steps are necessary and suffice to achieve randomness. The proof depends on the representation theory of the symmetric group and a bijection between trees and matchings.