Longest increasing paths with gaps

Anne-Laure Basdevant (1) , Lucas Gerin (2)

1 MODAL'X - Modélisation aléatoire de Paris X
2 CMAP - Centre de Mathématiques Appliquées - Ecole Polytechnique

We study a variant of the continuous and discrete Ulam-Hammersley problems. We obtain the limiting behaviour of the maximal length of an increasing path through a Poisson point process (or a Bernoulli point process) with the restriction that there must be minimal gaps between abscissae and ordinates of successive points of the path. We also establish that, as in the classical Ulam-Hammersley problem, the fluctuations around the mean are given by the Tracy-Widom distribution.

Domaines: Probabilités [math.PR]; Combinatoire [math.CO]

Anne-Laure Basdevant, Lucas Gerin. Longest increasing paths with gaps. ALEA : Latin American Journal of Probability and Mathematical Statistics, 2019, 16 (2), pp.1141. ⟨10.30757/alea.v16-43⟩. ⟨hal-01796897v1⟩