Combinatorial Theory Seminar

We introduce a new spanning tree model which we call Random Spanning Trees in Random Environment (RSTRE), which was introduced independently by A. Kúsz. As the inverse temperature beta varies in the underlying Gibbs measure, it interpolates between the uniform spanning tree and the minimum spanning tree. On the complete graph with n vertices, we show that with high probability, the diameter of the random spanning tree is of order n^1/2 when β=o(n/log n), and is of order n^1/3 when β > n^4/3 log n. We conjecture that the diameter exponent linearly interpolates between these two regimes as the power exponent of beta varies. Based on joint work with L. Makowiec and M. Salvi.

Denote by p(k) the limit, as n tends to infinity, of the probability that a random permutation on n letters has some invariant set of size k. For example, p(1) = 1 - 1/e. I will discuss the asymptotic behaviour of p(k). Joint work with Mehtaab Sawhney.

TBC