Random non-crossing plane configurations: A conditioned Galton-Watson tree approach

Nicolas Curien, Igor Kortchemski

Research output: Contribution to journalArticlepeer-review

Abstract

We study various models of random non-crossing configurations consisting of diagonals of convex polygons, and focus in particular on uniform dissections and non-crossing trees. For both these models, we prove convergence in distribution towards Aldous' Brownian triangulation of the disk. In the case of dissections, we also refine the study of the maximal vertex degree and validate a conjecture of Bernasconi, Panagiotou and Steger. Our main tool is the use of an underlying Galton-Watson tree structure.

Original languageEnglish
Pages (from-to)236-260
Number of pages25
JournalRandom Structures and Algorithms
Volume45
Issue number2
DOIs
Publication statusPublished - 1 Jan 2014
Externally publishedYes

Keywords

  • Brownian triangulation
  • Conditioned Galton-Watson trees
  • Dissections
  • Non-crossing plane configurations
  • Probability on graphs

Fingerprint

Dive into the research topics of 'Random non-crossing plane configurations: A conditioned Galton-Watson tree approach'. Together they form a unique fingerprint.

Cite this