Some Probabilistic Trees with Algebraic Roots
Keywords:
Branched polymers, Random graphs, Random trees, Matrix-tree theorem
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.