Uniform random sampling of simple branched coverings of the sphere by itself

摘要

We present the first polynomial uniform random sampling algorithm for simple branched coverings of degree n of the sphere by itself. More precisely, our algorithm generates in linear time increasing quadrangulations, which are equivalent combinatorial structures. Our result is based on the identification of some canonical labelled spanning trees, and yields a constructive proof of a celebrated formula of Hurwitz for the number of some factorizations of permutations in transpositions. The previous approaches were either non constructive or lead to exponential time algorithms for the sampling problem.