Schröder’s problems and scaling limits of random trees

Pitman, Jim; Rizzolo, Douglas

doi:10.1090/S0002-9947-2015-06254-0

Schröder’s problems and scaling limits of random trees
HTML articles powered by AMS MathViewer

by Jim Pitman and Douglas Rizzolo PDF

Trans. Amer. Math. Soc. 367 (2015), 6943-6969 Request permission

Abstract:

In his now classic paper of 1870, Schröder posed four combinatorial problems about the number of certain types of bracketings of words and sets. Here we address what these bracketings look like on average. For each of the four problems we prove that a uniform pick from the appropriate set of bracketings, when considered as a tree, has the Brownian continuum random tree as its scaling limit as the size of the word or set goes to infinity.

References

David Aldous, The continuum random tree. I, Ann. Probab. 19 (1991), no. 1, 1–28. MR 1085326
David Aldous, The continuum random tree. II. An overview, Stochastic analysis (Durham, 1990), London Math. Soc. Lecture Note Ser., vol. 167, Cambridge Univ. Press, Cambridge, 1991, pp. 23–70. MR 1166406 (93f:60010)
David Aldous, The continuum random tree. III, Ann. Probab. 21 (1993), no. 1, 248–289. MR 1207226
Patrick Billingsley, Convergence of probability measures, 2nd ed., Wiley Series in Probability and Statistics: Probability and Statistics, John Wiley & Sons, Inc., New York, 1999. A Wiley-Interscience Publication. MR 1700749, DOI 10.1002/9780470316962
Nicolas Curien and Igor Kortchemski, Random non-crossing plane configurations: a conditioned Galton-Watson tree approach, Random Structures Algorithms 45 (2014), no. 2, 236–260. MR 3245291, DOI 10.1002/rsa.20481
Michael Drmota, Random trees, SpringerWienNewYork, Vienna, 2009. An interplay between combinatorics and probability. MR 2484382, DOI 10.1007/978-3-211-75357-6
Thomas Duquesne and Jean-François Le Gall, Probabilistic and fractal aspects of Lévy trees, Probab. Theory Related Fields 131 (2005), no. 4, 553–603. MR 2147221, DOI 10.1007/s00440-004-0385-4
Philippe Flajolet and Robert Sedgewick, Analytic combinatorics, Cambridge University Press, Cambridge, 2009. MR 2483235, DOI 10.1017/CBO9780511801655
Bénédicte Haas and Grégory Miermont, Scaling limits of Markov branching trees with applications to Galton-Watson and random unordered trees, Ann. Probab. 40 (2012), no. 6, 2589–2666. MR 3050512, DOI 10.1214/11-AOP686
Bénédicte Haas, Grégory Miermont, Jim Pitman, and Matthias Winkel, Continuum tree asymptotics of discrete fragmentations and applications to phylogenetic models, Ann. Probab. 36 (2008), no. 5, 1790–1837. MR 2440924, DOI 10.1214/07-AOP377
Götz Kersting, On the height profile of a conditioned Galton-Watson tree, arXiv:1101.3656v1 (1998 (appeared on Arxiv 2011)).
V. F. Kolchin, Branching processes, random trees, and a generalized scheme of arrangements of particles, Mathematical Notes 21 (1977), 386–394, DOI 10.1007/BF01788236.
Igor Kortchemski, Invariance principles for Galton-Watson trees conditioned on the number of leaves, Stochastic Process. Appl. 122 (2012), no. 9, 3126–3172. MR 2946438, DOI 10.1016/j.spa.2012.05.013
Jean-François Le Gall, Random real trees, Ann. Fac. Sci. Toulouse Math. (6) 15 (2006), no. 1, 35–62 (English, with English and French summaries). MR 2225746, DOI 10.5802/afst.1112
Jean-François Marckert and Abdelkader Mokkadem, The depth first processes of Galton-Watson trees converge to the same Brownian excursion, Ann. Probab. 31 (2003), no. 3, 1655–1678. MR 1989446, DOI 10.1214/aop/1055425793
Peter McCullagh, Jim Pitman, and Matthias Winkel, Gibbs fragmentation trees, Bernoulli 14 (2008), no. 4, 988–1002. MR 2543583, DOI 10.3150/08-BEJ134
A. Meir and J. W. Moon, On the altitude of nodes in random trees, Canadian J. Math. 30 (1978), no. 5, 997–1015. MR 506256, DOI 10.4153/CJM-1978-085-0
Yu. L. Pavlov, The asymptotic distribution of maximum tree size in a random forest, Theor. Probab. Appl. 22 (1978), no. 3, 509–520.
Yu. L. Pavlov, Limit distributions of the height of a random forest, Teor. Veroyatnost. i Primenen. 28 (1983), no. 3, 449–457 (Russian, with English summary). MR 716303
Jim Pitman, Enumerations of trees and forests related to branching processes and random walks, Microsurveys in discrete probability (Princeton, NJ, 1997) DIMACS Ser. Discrete Math. Theoret. Comput. Sci., vol. 41, Amer. Math. Soc., Providence, RI, 1998, pp. 163–180. MR 1630413
J. Pitman, Combinatorial stochastic processes, Lecture Notes in Mathematics, vol. 1875, Springer-Verlag, Berlin, 2006. Lectures from the 32nd Summer School on Probability Theory held in Saint-Flour, July 7–24, 2002; With a foreword by Jean Picard. MR 2245368
Douglas Rizzolo, Scaling limits of Markov branching trees and Galton-Watson trees conditioned on the number of vertices with out-degree in a given set, to appear in Ann. Inst. Henri Poincaré Probab. Stat.
Ernst Schröder, Vier combinatorische probleme, Z. Math. Physik 15 (1870), 361–376.
Richard P. Stanley, Enumerative combinatorics. Vol. 2, Cambridge Studies in Advanced Mathematics, vol. 62, Cambridge University Press, Cambridge, 1999. With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin. MR 1676282, DOI 10.1017/CBO9780511609589