Some Probabilistic Trees with Algebraic Roots

  • Olivier Bernardi
  • Alejandro H. Morales
Keywords: Branched polymers, Random graphs, Random trees, Matrix-tree theorem


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.

Article Number