Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

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


Authors: Jim Pitman and Douglas Rizzolo
Journal: Trans. Amer. Math. Soc. 367 (2015), 6943-6969
MSC (2010): Primary 60C05, 60J80
DOI: https://doi.org/10.1090/S0002-9947-2015-06254-0
Published electronically: January 15, 2015
MathSciNet review: 3378819
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] David Aldous, The continuum random tree. I, Ann. Probab. 19 (1991), no. 1, 1-28. MR 1085326 (91i:60024)
  • [2] 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)
  • [3] David Aldous, The continuum random tree. III, Ann. Probab. 21 (1993), no. 1, 248-289. MR 1207226 (94c:60015)
  • [4] Patrick Billingsley, Convergence of probability measures, 2nd ed., Wiley Series in Probability and Statistics: Probability and Statistics, John Wiley & Sons Inc., New York, 1999. MR 1700749 (2000e:60008)
  • [5] 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, https://doi.org/10.1002/rsa.20481
  • [6] Michael Drmota, Random trees, an interplay between combinatorics and probability, SpringerWienNewYork, Vienna, 2009. MR 2484382 (2010i:05003)
  • [7] 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 (2006d:60123), https://doi.org/10.1007/s00440-004-0385-4
  • [8] Philippe Flajolet and Robert Sedgewick, Analytic combinatorics, Cambridge University Press, Cambridge, 2009. MR 2483235 (2010h:05005)
  • [9] 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, https://doi.org/10.1214/11-AOP686
  • [10] 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 (2010d:60192), https://doi.org/10.1214/07-AOP377
  • [11] Götz Kersting, On the height profile of a conditioned Galton-Watson tree, arXiv:1101.3656v1 (1998 (appeared on Arxiv 2011)).
  • [12] 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.
  • [13] 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, https://doi.org/10.1016/j.spa.2012.05.013
  • [14] 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 (2007g:60055)
  • [15] 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 (2004g:60120), https://doi.org/10.1214/aop/1055425793
  • [16] Peter McCullagh, Jim Pitman, and Matthias Winkel, Gibbs fragmentation trees, Bernoulli 14 (2008), no. 4, 988-1002. MR 2543583 (2011a:60309), https://doi.org/10.3150/08-BEJ134
  • [17] A. Meir and J. W. Moon, On the altitude of nodes in random trees, Canad. J. Math. 30 (1978), no. 5, 997-1015. MR 506256 (80k:05043), https://doi.org/10.4153/CJM-1978-085-0
  • [18] Yu. L. Pavlov, The asymptotic distribution of maximum tree size in a random forest, Theor. Probab. Appl. 22 (1978), no. 3, 509-520.
  • [19] 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 (85d:05215)
  • [20] 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 (99g:60157)
  • [21] J. Pitman, Combinatorial stochastic processes, Lectures from the 32nd Summer School on Probability Theory held in Saint-Flour, July 7-24, 2002; with a foreword by Jean Picard, Lecture Notes in Mathematics, vol. 1875, Springer-Verlag, Berlin, 2006. MR 2245368 (2008c:60001)
  • [22] 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.
  • [23] Ernst Schröder, Vier combinatorische probleme, Z. Math. Physik 15 (1870), 361-376.
  • [24] Richard P. Stanley, Enumerative combinatorics. Vol. 2, with a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin, Cambridge Studies in Advanced Mathematics, vol. 62, Cambridge University Press, Cambridge, 1999. MR 1676282 (2000k:05026)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 60C05, 60J80

Retrieve articles in all journals with MSC (2010): 60C05, 60J80


Additional Information

Jim Pitman
Affiliation: Department of Statistics, University of California, Berkeley, California 94720
Email: pitman@stat.berkeley.edu

Douglas Rizzolo
Affiliation: Department of Mathematics, University of Washington, Seattle, Washington 98105
Email: drizzolo@math.washington.edu

DOI: https://doi.org/10.1090/S0002-9947-2015-06254-0
Received by editor(s): April 5, 2013
Received by editor(s) in revised form: June 12, 2013
Published electronically: January 15, 2015
Additional Notes: The first author was supported in part by NSF Grant No. 0806118
The second author was supported in part by NSF Grant No. 0806118, in part by the National Science Foundation Graduate Research Fellowship under Grant No. DGE 1106400, and in part by NSF DMS-1204840.
Article copyright: © Copyright 2015 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society