The geometry of random minimal factorizations of a long cycle via biconditioned bitype random trees

Féray, Valentin; Kortchemski, Igor

Annales Henri Lebesgue, Tome 1 (2018), pp. 149-226.

Nous étudions les factorisations minimales aléatoires d’un $n$-cycle en transpositions, c’est-à-dire les décompositions de $(1,\cdots ,n)$ comme un produit de $n-1$ transpositions. En représentant les transpositions comme des cordes du disque unité et en les lisant les unes après les autres, on obtient une suite croissantes de laminations du disque unité (i.e. de sous-ensembles compacts du disque unité constitués de cordes ne se croisant pas).

Quand le nombre de transpositions lues est de l’ordre $\sqrt{n}$, nous établissons l’existence d’une transition de phase et la convergence des laminations associées vers une nouvelle famille de laminations aléatoires à un paramètre, construites à partir de processus de Lévy.

Notre outil principle est le codage de ces factorisations minimal aléatoires par des arbres de Bienaymé–Galton–Watson bitype conditionnés. En particulier, nous obtenons des théorèmes limites pour de tels arbres, conditionnés à avoir un nombre fixe de nœuds de chaque couleur, et dont la loi de reproduction dépend de la taille à laquelle on conditionne. Nous pensons que ce résultat est aussi intéressant en lui-même.

We study random typical minimal factorizations of the $n$-cycle into transpositions, which are factorizations of $(1,...,n)$ as a product of $n-1$ 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 $\sqrt{n}$ 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.

Classification : 60C05, 60B15
Mots-clés : Permutation factorisation, random trees, non-crossing partitions, Lévy processes, Brownian triangulation

[ACEH16] Alexandrov, Alexander; Chapuy, Guillaume; Eynard, Bertrand; Harnad, John Weighted Hurwitz numbers and topological recursion: an overview (2016) (arXiv:1610.09408) | arXiv

[AHRV07] Angel, Omer; Holroyd, Alexander E.; Romik, Dan; Virág, Bálint Random sorting networks, Adv. Math., Volume 215 (2007) no. 2, pp. 839-868 | DOI | MR | Zbl

[AL11] Armendáriz, Inés; Loulakis, Michail Conditional distribution of heavy tailed random variables on large deviations of their sum, Stochastic Process. Appl., Volume 121 (2011) no. 5, pp. 1138-1147 | DOI | MR | Zbl

[Ald94a] Aldous, David Recursive self-similarity for random trees, random triangulations and Brownian excursion, Ann. Probab., Volume 22 (1994) no. 2, pp. 527-545 | DOI | MR | Zbl

[Ald94b] Aldous, David Triangulating the circle, at random, Amer. Math. Monthly, Volume 101 (1994) no. 3, pp. 223-233 | DOI | MR | Zbl

[AP98] Aldous, David; Pitman, Jim The standard additive coalescent, Ann. Probab., Volume 26 (1998) no. 4, pp. 1703-1726 | MR | Zbl

[BD06] Berestycki, Nathanaël; Durrett, Rick A phase transition in the random transposition random walk, Probab. Theory Related Fields, Volume 136 (2006) no. 2, pp. 203-233 | DOI | MR | Zbl

[Ber96] Bertoin, Jean Lévy processes, Cambridge Tracts in Mathematics, 121, Cambridge University Press, 1996 | Zbl

[Ber11] Berestycki, Nathanaël Emergence of giant cycles and slowdown transition in random transpositions and $k$-cycles, Electron. J. Probab., Volume 16 (2011) no. 5, pp. 152-173 | DOI | MR | Zbl

[Ber18] Berzunza, Gabriel 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 | DOI | MR | Zbl

[Bet18] Bettinelli, Jérémie Convergence of uniform noncrossing partitions toward the Brownian triangulation, Sém. Lotharigien Combin., Volume 80B (2018), #38, 12 pages (FPSAC Proceedings) | MR | Zbl

[BFG04] Bouttier, Jérémie; Francesco, Philippe Di; Guitter, Emmanuel Planar maps as labeled mobiles, Electron. J. Combin., Volume 11 (2004) no. 1 Research Paper 69, 27 pp. (electronic) | MR | Zbl

[Bia97] Biane, Philippe Some properties of crossings and partitions, Discrete Math., Volume 175 (1997) no. 1-3, pp. 41-53 | DOI | MR | Zbl

[Bia02] Biane, Philippe Parking functions of types a and b, Electron. J. Combin., Volume 9 (2002) no. 1 (Note #7, 5 pp) | MR | Zbl

[Bia05] Biane, Philippe Nombre de factorisations d’un grand cycle, Sém. Lothar. Combin., Volume 51 (2004/05) (Art. B51a, 4 pp) | MR | Zbl

[Bil68] Billingsley, Patrick Convergence of probability measures, first edition, Wiley, New-York, 1968 | Zbl

[BK00] Bennies, Jürgen; Kersting, Götz A random walk approach to Galton-Watson trees, J. Theoret. Probab., Volume 13 (2000), pp. 777-803 | DOI | MR | Zbl

[Bra14] Bravo, Gerónimo Uribe Bridges of Lévy processes conditioned to stay positive, Bernoulli, Volume 20 (2014) no. 1, pp. 190-206 | DOI | Zbl

[CB11] Chaumont, Loïc; Bravo, Gerónimo Uribe Markovian bridges: weak continuity and pathwise constructions, Ann. Probab., Volume 39 (2011) no. 2, pp. 609-647 | DOI | MR | Zbl

[CG11] Curien, Nicolas; Gall, Jean-François Le Random recursive triangulations of the disk via fragmentation theory, Ann. Probab., Volume 39 (2011) no. 6, pp. 2224-2270 | DOI | MR | Zbl

[CGH + 96] Corless, R. M.; Gonnet, G. H.; Hare, D. E. G.; Jeffrey, D. J.; Knuth, D. E. On the Lambert $W$ function, Adv. Comput. Math., Volume 5 (1996) no. 4, pp. 329-359 | DOI | MR | Zbl

[CK14] Curien, Nicolas; Kortchemski, Igor Random non-crossing plane configurations: a conditioned Galton-Watson tree approach, Random Structures Algorithms, Volume 45 (2014) no. 2, pp. 236-260 | DOI | MR | Zbl

[CK15] Curien, Nicolas; Kortchemski, Igor Percolation on random triangulations and stable looptrees, Probab. Theory Related Fields, Volume 163 (2015) no. 1-2, pp. 303-337 | DOI | MR | Zbl

[CL16] Chaumont, Loïc; Liu, Rongli 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 | DOI | MR | Zbl

[CW13] Curien, Nicolas; Werner, Wendelin The Markovian hyperbolic triangulation, J. Eur. Math. Soc., Volume 15 (2013) no. 4, pp. 1309-1341 | DOI | MR | Zbl

[Dau18] Dauvergne, Duncan The archimedean limit of random sorting networks (2018) (arXiv:1802.08934) | arXiv

[DMWZZ04] Diaconis, Persi; Mayer-Wolf, Eddy; Zeitouni, Ofer; Zerner, Martin P. W. The Poisson-Dirichlet law is the unique invariant distribution for uniform split-merge transformations, Ann. Probab., Volume 32 (2004) no. 1B, pp. 915-938 | MR | Zbl

[DS81] Diaconis, Persi; Shahshahani, Mehrdad Generating a random permutation with random transpositions, Z. Wahrsch. Verw. Gebiete, Volume 57 (1981) no. 2, pp. 159-179 | DOI | MR | Zbl

[Dur10] Durrett, Rick Probability: theory and examples, Cambridge Series in Statistical and Probabilistic Mathematics, 31, Cambridge University Press, Cambridge, 2010 | MR | Zbl

[Dén59] Dénes, József 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

[EG87] Edelman, Paul; Greene, Curtis Balanced tableaux, Adv. Math., Volume 63 (1987) no. 1, pp. 42-99 | DOI | MR | Zbl

[ELSV01] Ekedahl, Torsten; Lando, Sergei; Shapiro, Michael; Vainshtein, Alek Hurwitz numbers and intersections on moduli spaces of curves, Invent. Math., Volume 146 (2001) no. 2, pp. 297-327 | DOI | MR | Zbl

[FK18] Féray, Valentin; Kortchemski, Igor Trajectories in random minimal transposition factorizations (2018) (arXiv:1810.07586) | arXiv | Zbl

[FS09] Flajolet, Philippe; Sedgewick, Robert Analytic combinatorics, Cambridge University Press, Cambridge, 2009 | Zbl

[Fér12] Féray, Valentin Partial Jucys-Murphy elements and star factorizations, Eur. J. Combin., Volume 33 (2012), pp. 189-198 | DOI | MR | Zbl

[Gal05] Gall, Jean-François Le Random trees and applications, Probability Surveys (2005), pp. 245-311 | DOI | MR | Zbl

[GJ99a] Goulden, I. P.; Jackson, Daniel M. 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 | DOI | MR | Zbl

[GJ99b] Goulden, I. P.; Jackson, Daniel M. A proof of a conjecture for the number of ramified coverings of the sphere by the torus, J. Combin. Th. Ser. A, Volume 88 (1999) no. 2, pp. 246-258 | DOI | MR | Zbl

[GJ09] Goulden, I. P.; Jackson, Daniel M. Transitive powers of Young-Jucys-Murphy elements are central, Journal of Algebra, Volume 321 (2009) no. 7, pp. 1826-1835 | DOI | MR | Zbl

[GM11] Gall, Jean-François Le; Miermont, Grégory Scaling limits of random planar maps with large faces, Ann. Probab., Volume 39 (2011) no. 1, pp. 1-69 | DOI | MR | Zbl

[GP93] Goulden, I. P.; Pepper, S. Labelled trees and factorizations of a cycle into transpositions, Discrete Math., Volume 113 (1993) no. 1-3, pp. 263-268 | DOI | MR | Zbl

[GP08] Gall, Jean-François Le; Paulin, Frédéric Scaling limits of bipartite planar maps are homeomorphic to the 2-sphere, Geom. Funct. Anal., Volume 18 (2008) no. 3, pp. 893-918 | DOI | MR | Zbl

[GY02] Goulden, Ian; Yong, Alexander Tree-like properties of cycle factorizations, J. Combin. Theory Ser. A, Volume 98 (2002) no. 1, pp. 106-117 | DOI | MR | Zbl

[Hoe63] Hoeffding, Wassily Probability inequalities for sums of bounded random variables, J. Amer. Stat. Assoc., Volume 58 (1963) no. 301, pp. 13-30 | DOI | MR

[Hur91] Hurwitz, Adolf Ueber Riemann’sche Flächen mit gegebenen Verzweigungspunkten, Math. Ann., Volume 39 (1891) no. 1, pp. 1-60 | DOI | Zbl

[IR09] Irving, John; Rattan, Amarpreet Minimal factorizations of permutations into star transpositions, Discrete Mathematics, Volume 309 (2009) no. 6, pp. 1435-1442 | DOI | MR | Zbl

[Jac88] Jackson, Daniel Some combinatorial problems associated with products of conjugacy classes of the symmetric group, J. Combin. Theory Ser. A, Volume 49 (1988), pp. 363-369 | DOI | MR | Zbl

[Jan12] Janson, Svante Simply generated trees, conditioned Galton-Watson trees, random allocations and condensation, Probab. Surv., Volume 9 (2012), pp. 103-252 | DOI | MR

[JS03] Jacod, Jean; Shiryaev, Albert N. Limit theorems for stochastic processes, Grundlehren der Mathematischen Wissenschaften, 288, Springer-Verlag, Berlin, 2003 | MR | Zbl

[Kal81] Kallenberg, Olav Splitting at backward times in regenerative sets, Ann. Probab., Volume 9 (1981) no. 5, pp. 781-799 | DOI | MR | Zbl

[Kal02] Kallenberg, Olav Foundations of modern probability, Probability and its Applications, Springer-Verlag, New York, 2002 | DOI | Zbl

[KM16] Kortchemski, Igor; Marzouk, Cyril Triangulating stable laminations, Electron. J. Probab., Volume 21 (2016) (Paper No. 11, 31 p.) | MR | Zbl

[KM17] Kortchemski, Igor; Marzouk, Cyril Simply Generated Non-Crossing Partitions, Combin. Probab. Comput., Volume 26 (2017) no. 4, pp. 560-592 | DOI | MR | Zbl

[Kor14] Kortchemski, Igor Random stable laminations of the disk, Ann. Probab., Volume 42 (2014) no. 2, pp. 725-759 | DOI | MR | Zbl

[Kor15] Kortchemski, Igor Limit theorems for conditioned non-generic Galton-Watson trees, Ann. Inst. Henri Poincaré Probab. Stat., Volume 51 (2015) no. 2, pp. 489-511 | DOI | Numdam | MR | Zbl

[Kyp06] Kyprianou, Andreas E. Introductory lectures on fluctuations of Lévy processes with applications, Universitext, Springer-Verlag, Berlin, 2006 | Zbl

[Lin92] Lindvall, Torgny Lectures on the coupling method, Wiley Series in Probability and Mathematical Statistics, John Wiley & Sons, Inc., New York, 1992 | MR | Zbl

[Mie01] Miermont, Grégory Ordered additive coalescent and fragmentations associated to Levy processes with no positive jumps, Electron. J. Probab., Volume 6 (2001) (art. no. 14, 33 p.) | MR | Zbl

[Mie08] Miermont, Grégory Invariance principles for spatial multitype Galton-Watson trees, Ann. Inst. Henri Poincaré Probab. Stat., Volume 44 (2008) no. 6, pp. 1128-1161 | DOI | Numdam | MR | Zbl

[Mil77] Millar, P. W. Zero-one laws and the minimum of a Markov process, Trans. Amer. Math. Soc., Volume 226 (1977), pp. 365-391 | DOI | MR | Zbl

[MM03] Marckert, Jean-François; Mokkadem, Abdelkader The depth first processes of Galton-Watson trees converge to the same Brownian excursion, Ann. Probab., Volume 31 (2003) no. 3, pp. 1655-1678 | MR | Zbl

[MM07] Marckert, Jean-François; Miermont, Grégory Invariance principles for random bipartite planar maps, Ann. Probab., Volume 35 (2007) no. 5, pp. 1642-1705 | DOI | MR | Zbl

[Mos89] Moszkowski, Paul 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 | DOI | MR | Zbl

[Nev86] Neveu, Jacques Arbres et processus de Galton-Watson, Ann. Inst. Henri Poincaré Probab. Stat., Volume 22 (1986) no. 2, pp. 199-207 | Numdam | MR | Zbl

[NS06] Nica, Alexandru; Speicher, Roland Lectures on the combinatorics of free probability, London Mathematical Society Lecture Note Series, 335, Cambridge University Press, Cambridge, 2006 | MR | Zbl

[Oko00] Okounkov, Andrei Toda equations for Hurwitz numbers, Math. Res. Lett., Volume 7 (2000) no. 4, pp. 447-453 | DOI | MR | Zbl

[Pak99] Pak, Igor 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 | Zbl

[Pit06] Pitman, Jim 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 | Zbl

[Sch05] Schramm, Oded Compositions of random transpositions, Israel J. Math., Volume 147 (2005), pp. 221-243 | DOI | MR | Zbl

[SSV97] Shapiro, Boris; Shapiro, Michael; Vainshtein, Alek Ramified coverings of $s_2$ with one degenerate branching point and enumeration of edge-ordered graphs, Adv. in Math. Sci., Volume 34 (1997), pp. 219-228

[Sta84] Stanley, Richard P. On the number of reduced decompositions of elements of Coxeter groups, European J. Combin., Volume 5 (1984) no. 4, pp. 359-372 | DOI | MR | Zbl

[The] Thevenin, Paul (work in progress)

[Tót93] Tóth, Bálint Improved lower bound on the thermodynamic pressure of the spin $1/2$ Heisenberg ferromagnet, Lett. Math. Phys., Volume 28 (1993) no. 1, pp. 75-84 | DOI | MR | Zbl