Féray, Valentin; Kortchemski, Igor
The geometry of random minimal factorizations of a long cycle via biconditioned bitype random trees
Annales Henri Lebesgue, Volume 1 (2018), p. 149-226

Metadata

KeywordsPermutation factorisation, random trees, non-crossing partitions, Lévy processes, Brownian triangulation

Abstract

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 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.


References

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

[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 | MR 2355610 | Zbl 1132.60008

[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 | MR 2775110 | Zbl 1218.60021

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

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

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

[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 | MR 2240787 | Zbl 1102.60005

[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 | MR 2754801 | Zbl 1228.60079

[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 | MR 3748121 | Zbl 1378.60110

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

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

[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 2097335 | Zbl 1060.05045

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

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

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

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

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

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

[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 | MR 2789508

[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 | MR 2932668 | Zbl 1252.60016

[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 | MR 1414285 | Zbl 0863.65008

[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 | MR 3245291 | Zbl 1301.05310

[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 | MR 3405619 | Zbl 1342.60164

[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 | MR 3449255 | Zbl 1342.60147

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

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

[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 115936

[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 2044670 | Zbl 1049.60088

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

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

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

[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 | MR 1864018 | Zbl 1073.14041

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

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

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

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

[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 | MR 2494750 | Zbl 1196.20016

[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 | MR 1723797 | Zbl 0936.05005

[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 | MR 1723796 | Zbl 0939.05006

[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 | MR 2778796 | Zbl 1204.05088

[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 | MR 2438999 | Zbl 1166.60006

[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 | MR 1212884 | Zbl 0779.05017

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

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

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

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

[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 | MR 964394 | Zbl 0682.20002

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

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

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

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

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

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

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

[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 | Numdam | MR 3335012 | Zbl 1315.60091

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

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

[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 1844511 | Zbl 0974.60054

[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 | Numdam | MR 2469338 | Zbl 1178.60058

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

[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 1989446 | Zbl 1049.05026

[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 | MR 2349571 | Zbl 1208.05135

[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 | MR 977175 | Zbl 0672.05022

[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 850756 | Zbl 0601.60082

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

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

[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 1691876 | Zbl 0931.05003

[Pit06] Pitman, Jim Combinatorial stochastic processes, Springer-Verlag, Berlin, Lecture Notes in Mathematics, Volume 1875 (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

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

[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 | Zbl 0876.14033

[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 | MR 782057 | Zbl 0587.20002

[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 | MR 1224836 | Zbl 0772.60103