We study random typical minimal factorizations of the -cycle into transpositions, which are factorizations of as a product of transpositions. By viewing transpositions as chords of the unit disk and by reading them one after the other, one obtains a sequence of increasing laminations of the unit disk (i.e. compact subsets of the unit disk made of non-intersecting chords).
When an order of consecutive transpositions have been read, we establish, roughly speaking, that a phase transition occurs and that the associated laminations converge to a new one-parameter family of random laminations, constructed from excursions of specific Lévy processes.
Our main tools involve coding random minimal factorizations by conditioned two-type Bienaymé–Galton–Watson trees. We establish in particular limit theorems for two-type BGW trees conditioned on having given numbers of vertices of both types, and with an offspring distribution depending on the conditioning size. We believe that this could be of independent interest.
[AL11] Conditional distribution of heavy tailed random variables on large deviations of their sum, Stochastic Process. Appl., Volume 121 (2011) no. 5, pp. 1138-1147 | Article | MR 2775110 | Zbl 1218.60021
[Ber96] Lévy processes, Cambridge Tracts in Mathematics, 121, Cambridge University Press, 1996 | Zbl 0861.60003
[Ber18] On scaling limits of multitype Galton-Watson trees with possibly infinite variance, ALEA Lat. Am. J. Probab. Math. Stat., Volume 15 (2018) no. 1, pp. 21-48 | Article | MR 3748121 | Zbl 1378.60110
[Bet18] Convergence of uniform noncrossing partitions toward the Brownian triangulation, Sém. Lotharigien Combin., Volume 80B (2018), p. Article #38, 12pp., FPSAC Proceedings | MR 3940613 | Zbl 1415.52011
[Bil68] Convergence of probability measures, first edition, Wiley, New-York, 1968 | Zbl 0944.60003
[CL16] Coding multitype forests: application to the law of the total population of branching forests, Trans. Amer. Math. Soc., Volume 368 (2016) no. 4, pp. 2723-2747 | Article | MR 3449255 | Zbl 1342.60147
[Dén59] The representation of a permutation as the product of a minimal number of transpositions, and its connection with the theory of graphs, Magyar Tud. Akad. Mat. Kutató Int. Közl., Volume 4 (1959), pp. 63-71 | MR 115936
[FS09] Analytic combinatorics, Cambridge University Press, Cambridge, 2009 | Zbl 1165.05001
[GJ99a] The number of ramified coverings of the sphere by the double torus, and a general form for higher genera, J. Combin. Th. Ser. A, Volume 88 (1999) no. 2, pp. 259-275 | Article | MR 1723797 | Zbl 0936.05005
[Jac88] Some combinatorial problems associated with products of conjugacy classes of the symmetric group, J. Combin. Theory Ser. A, Volume 49 (1988), pp. 363-369 | Article | MR 964394 | Zbl 0682.20002
[Kyp06] Introductory lectures on fluctuations of Lévy processes with applications, Universitext, Springer-Verlag, Berlin, 2006 | Zbl 1104.60001
[Mie08] Invariance principles for spatial multitype Galton-Watson trees, Ann. Inst. Henri Poincaré Probab. Stat., Volume 44 (2008) no. 6, pp. 1128-1161 | Article | Numdam | MR 2469338 | Zbl 1178.60058
[Mos89] A solution to a problem of Dénes: a bijection between trees and factorizations of cyclic permutations, European J. Combin., Volume 10 (1989) no. 1, pp. 13-16 | Article | MR 977175 | Zbl 0672.05022
[Pak99] Reduced decompositions of permutations in terms of star transpositions, generalized Catalan numbers and k-ary trees, Discrete Math., Volume 204 (1999), pp. 329-335 | MR 1691876 | Zbl 0931.05003
[Pit06] Combinatorial stochastic processes, Lecture Notes in Mathematics, 1875, Springer-Verlag, Berlin, 2006 (Lectures from the 32nd Summer School on Probability Theory held in Saint-Flour, July 7–24. With a foreword by Jean Picard) | MR 2245368 | Zbl 1103.60004
[SSV97] Ramified coverings of with one degenerate branching point and enumeration of edge-ordered graphs, Adv. in Math. Sci., Volume 34 (1997), pp. 219-228
[The](work in progress)