From Hammersley's lines to Hammersley's trees - Université Paris Nanterre Accéder directement au contenu
Article Dans Une Revue Probability Theory and Related Fields Année : 2018

From Hammersley's lines to Hammersley's trees

Résumé

We construct a stationary random tree, embedded in the upper half plane, with prescribed offspring distribution and whose vertices are the atoms of a unit Poisson point process. This process which we call Hammersley's tree process extends the usual Hammersley's line process. Just as Hammersley's process is related to the problem of the longest increasing subsequence, this model also has a combinatorial interpretation: it counts the number of heaps (i.e. increasing trees) required to store a random permutation. This problem was initially considered by Byers et. al (2011) and Istrate and Bonchis (2015) in the case of regular trees. We show, in particular, that the number of heaps grows logarithmically with the size of the permutation.
Fichier principal
Vignette du fichier
heap.pdf (1.22 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-01313542 , version 1 (10-05-2016)

Identifiants

Citer

Anne-Laure Basdevant, Lucas Gerin, Jean-Baptiste Gouere, Arvind Singh. From Hammersley's lines to Hammersley's trees. Probability Theory and Related Fields, 2018, 171 (1-2), pp.1-51. ⟨10.1007/s00440-017-0772-2⟩. ⟨hal-01313542⟩
241 Consultations
114 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More