From Hammersleys lines to Hammersleys treesReportar como inadecuado

From Hammersleys lines to Hammersleys trees - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 MODAL-X - Modélisation aléatoire de Paris X 2 CMAP - Centre de Mathématiques Appliquées - Ecole Polytechnique 3 LMPT - Laboratoire de Mathématiques et Physique Théorique 4 LM-Orsay - Laboratoire de Mathématiques d-Orsay

Abstract : 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.

Keywords : Longest increasing subsequences Patience sorting Hammersley-s process Heap sorting Interacting particles systems

Autor: Anne-Laure Basdevant - Lucas Gerin - Jean-Baptiste Gouere - Arvind Singh -



Documentos relacionados