Some Probabilistic Trees with Algebraic Roots

Abstract

We consider several probabilistic processes defining a random graph. One of these processes appeared recently in connection with a factorization problem in the symmetric group. For each process, we prove that the probability for the random graph to be a tree has an unexpectedly simple expression, which is independent of most parameters of the problem. This raises many open questions.