Beyond Hammersley’s Last-Passage Percolation: a discussion on possible local and global constraints

Abstract

Hammersley’s Last-Passage Percolation (LPP), also known as Ulam’s problem, is a well-studied model that can be described as follows: let $m$ points be chosen uniformly and independently in [0,1]${}^2$, then what is the maximal number ${\mathcal{L}}_m$ of points that can be collected by an up-right path? We introduce here a generalization of this LPP, allowing for more general constraints than the up-right condition: the constraints may be either local or global. We give the correct order of ${\mathcal{L}}_m$ in a general manner, and we illustrate the interest and usefulness of this generalized LPP with examples and simulations.