Hostname: page-component-74656f9884-8r8nv Total loading time: 0 Render date: 2026-11-07T10:44:44.477Z Has data issue: false hasContentIssue false
  • English
  • Français

Simply Generated Non-Crossing Partitions

Published online by Cambridge University Press:  28 March 2017

IGOR KORTCHEMSKI  and
CYRIL MARZOUK
IGOR KORTCHEMSKI
Affiliation:
CNRS, CMAP, École Polytechnique, Université Paris-Saclay, Route de Saclay, 91128 Palaiseau CEDEX, France (e-mail: igor.kortchemski@normalesup.org)
CYRIL MARZOUK
Affiliation:
Institut für Mathematik, Universität Zürich, Winterthurerstrasse 190, CH-8057 Zürich, Switzerland (e-mail: cyril.marzouk@math.uzh.ch)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We introduce and study the model of simply generated non-crossing partitions, which are, roughly speaking, chosen at random according to a sequence of weights. This framework encompasses the particular case of uniform non-crossing partitions with constraints on their block sizes. Our main tool is a bijection between non-crossing partitions and plane trees, which maps such simply generated non-crossing partitions into simply generated trees so that blocks of size k are in correspondence with vertices of out-degree k. This allows us to obtain limit theorems concerning the block structure of simply generated non-crossing partitions. We apply our results in free probability by giving a simple formula relating the maximum of the support of a compactly supported probability measure on the real line in terms of its free cumulants.

Keywords

Primary 05C8060C05Secondary 05C0560J80

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 26 , Issue 4 , July 2017 , pp. 560 - 592
Copyright
Copyright © Cambridge University Press 2017 

References

[1] Abraham, C. (2016) Rescaled bipartite planar maps converge to the Brownian map. Ann. Inst. H. Poincaré Probab. Statist. 52 575–595.CrossRefGoogle Scholar
[2] Aldous, D. (1994) Triangulating the circle, at random. Amer. Math. Monthly 101 223–233.CrossRefGoogle Scholar
[3] Arizmendi, O. (2012) Statistics of blocks in k-divisible non-crossing partitions. Electron. J. Combin. 19 47.CrossRefGoogle Scholar
[4] Arizmendi, O. and Vargas, C. (2012) Products of free random variables and k-divisible non-crossing partitions. Electron. Commun. Probab. 17 11.CrossRefGoogle Scholar
[5] Benaych-Georges, F. (2006) Taylor expansions of R-transforms: Application to supports and moments. Indiana Univ. Math. J. 55 465–481.Google Scholar
[6] Bercovici, H. and Voiculescu, D. (1993) Free convolution of measures with unbounded support. Indiana Univ. Math. J. 42 733–773.Google Scholar
[7] Bernasconi, N., Panagiotou, K. and Steger, A. (2010) On properties of random dissections and triangulations. Combinatorica 30 627–654.Google Scholar
[8] Bertoin, J. (1996) Lévy Processes, Vol. 121 of Cambridge Tracts in Mathematics, Cambridge University Press.Google Scholar
[9] Billingsley, P. (1999) Convergence of Probability Measures, second edition, Wiley Series in Probability and Statistics, Wiley.Google Scholar
[10] Björnberg, J. and Stefánsson, S. (2014) Recurrence of bipartite planar maps. Electron. J. Probab. 19 31.Google Scholar
[11] Chaumont, L. (1997) Excursion normalisée, méandre et pont pour les processus de Lévy stables. Bull. Sci. Math. 121 377–403.Google Scholar
[12] Curien, N. and Kortchemski, I. (2014) Random non-crossing plane configurations: A conditioned Galton–Watson tree approach. Random Struct. Alg. 45 236–260.Google Scholar
[13] Dembo, A., Mörters, P. and Sheffield, S. (2005) Large deviations of Markov chains indexed by random trees. Ann. Inst. H. Poincaré Probab. Statist. 41 971–996.Google Scholar
[14] Dershowitz, N. and Zaks, S. (1986) Ordered trees and noncrossing partitions. Discrete Math. 62 215–218.Google Scholar
[15] Deutsch, E. and Noy, M. (2002) Statistics on non-crossing trees. Discrete Math. 254 75–87.Google Scholar
[16] Devroye, L., Flajolet, P., Hurtado, F., Noy, M. and Steiger, W. (1999) Properties of random triangulations and trees. Discrete Comput. Geom. 22 105–117.CrossRefGoogle Scholar
[17] Drmota, M., de Mier, A. and Noy, M. (2014) Extremal statistics on non-crossing configurations. Discrete Math. 327 103–117.CrossRefGoogle Scholar
[18] Duquesne, T. (2003) A limit theorem for the contour process of conditioned Galton–Watson trees. Ann. Probab. 31 996–1027.CrossRefGoogle Scholar
[19] Edelman, P. H. (1980) Chain enumeration and non-crossing partitions. Discrete Math. 31 171–180.CrossRefGoogle Scholar
[20] Flajolet, P. and Sedgewick, R. (2009) Analytic Combinatorics, Cambridge University Press.Google Scholar
[21] Gao, Z. and Wormald, N. C. (2000) The distribution of the maximum vertex degree in random planar maps. J. Combin. Theory Ser. A 89 201–230.CrossRefGoogle Scholar
[22] Hiai, F. and Petz, D. (2000) The Semicircle Law, Free Random Variables and Entropy, Vol. 77 of Mathematical Surveys and Monographs, AMS.Google Scholar
[23] Janson, S. (2012) Simply generated trees, conditioned Galton–Watson trees, random allocations and condensation. Probab. Surv. 9 103–252.Google Scholar
[24] Janson, S. (2014) Asymptotic normality of fringe subtrees and additive functionals in conditioned Galton–Watson trees. Random Struct. Alg. 48 57–101.CrossRefGoogle Scholar
[25] Janson, S., Jonsson, T. and Stefánsson, S. Ö. (2011) Random trees with superexponential branching weights. J. Phys. A: Math. Theor. 44, 485002.Google Scholar
[26] Janson, S. and Stefánsson, S. Ö. (2015) Scaling limits of random planar maps with a unique large face. Ann. Probab. 43 1045–1081.Google Scholar
[27] Kortchemski, I. (2014) Random stable laminations of the disk. Ann. Probab. 42 725–759.CrossRefGoogle Scholar
[28] Kreweras, G. (1972) Sur les partitions non croisées d'un cycle. Discrete Math. 1 333–350.Google Scholar
[29] Le Gall, J.-F. and Miermont, G. (2011) Scaling limits of random planar maps with large faces. Ann. Probab. 39 1–69.Google Scholar
[30] Le Gall, J.-F. and Paulin, F. (2008) Scaling limits of bipartite planar maps are homeomorphic to the 2-sphere. Geom. Funct. Anal. 18 893–918.Google Scholar
[31] Marckert, J.-F. and Panholzer, A. (2002) Noncrossing trees are almost conditioned Galton–Watson trees. Random Struct. Alg. 20 115–125.CrossRefGoogle Scholar
[32] McCammond, J. (2006) Noncrossing partitions in surprising locations. Amer. Math. Monthly 113 598–610.Google Scholar
[33] Meir, A. and Moon, J. W. (1978) On the altitude of nodes in random trees. Canad. J. Math. 30 997–1015.Google Scholar
[34] Ortmann, J. (2012) Large deviations for non-crossing partitions. Electron. J. Probab. 17 34.Google Scholar
[35] Ortmann, J. (2013) Functionals of the Brownian bridge. In Séminaire de Probabilités XLV, Vol. 2078 of Lecture Notes in Mathematics, Springer, pp. 433–458.Google Scholar
[36] Prodinger, H. (1983) A correspondence between ordered trees and noncrossing partitions. Discrete Math. 46 205–206.Google Scholar
[37] Shi, Q. (2015) On the number of large triangles in the Brownian triangulation and fragmentation processes. Stochastic Process. Appl. 125 4321–4350.Google Scholar
[38] Speicher, R. (1994) Multiplicative functions on the lattice of noncrossing partitions and free convolution. Math. Ann. 298 611–628.Google Scholar
[39] Stanley, R. P. (1999) Enumerative Combinatorics 2, Vol. 62 of Cambridge Studies in Advanced Mathematics, Cambridge University Press.Google Scholar
[40] Yano, F. and Yoshida, H. (2007) Some set partition statistics in non-crossing partitions and generating functions. Discrete Math. 307 3147–3160.Google Scholar