Some Probabilistic Trees with Algebraic Roots

Olivier Bernardi, Alejandro H. Morales


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.


Branched polymers, Random graphs, Random trees, Matrix-tree theorem

Full Text: PDF