Longest increasing paths with gaps

MaRDI QIDQ4972751zbMATH OpenFDO

Authors Anne-Laure Basdevant, L. Gerin

Publication date 26 November 2019

Full work available at URL https://arxiv.org/abs/1805.09136, http://alea.impa.br/articles/v16/16-43.pdf

zbMATH Keywords

combinatorial probabilitylongest inlongest increasing subsequences

Mathematics Subject Classification ID

Combinatorial probability (60C05) Strong limit theorems (60F15) Interacting random processes; statistical mechanics type models; percolation theory (60K35)

Abstract: We consider a variant of the continuous and discrete Ulam-Hammersley problems: we study 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.For both cases (continuous and discrete) our approach rely on couplings with well-studied models: respectively the classical Ulam-Hammersley problem and last-passage percolation with geometric weights. Thanks to these couplings we obtain explicit limiting shapes in both settings.We also establish that, as in the classical Ulam-Hammersley problem, the fluctuations around the mean are given by the Tracy-Widom distribution.

Recommendations

• Longest increasing paths with Lipschitz constraints
• Ulam's problem and Hammersley's process
• Large deviations for increasing sequences on the plane
• Transversal fluctuations for increasing subsequences on the plane
• scientific article; zbMATH DE number 1867209

Cites work

• A microscopic model for the Burgers equation and longest increasing subsequences
• Bethe ansatz solution of the finite Bernoulli matching model of sequence alignment
• Discrete Hammersley's lines with sources and sinks
• Discrete orthogonal polynomial ensembles and the Plancherel measure
• Exact limiting shape for a simplified model of first-passage percolation on the plane
• Hammersley's interacting particle process and longest increasing subsequences
• scientific article; zbMATH DE number 3373691 (Why is no real title available?)
• Hydrodynamical methods for analyzing longest increasing subsequences
• Increasing sequences of independent points on the planar lattice
• On the distribution of the length of the longest increasing subsequence of random permutations
• On two variants of the longest increasing subsequence problem
• Optimality regions and fluctuations for Bernoulli last passage models
• Order of the variance in the discrete Hammersley process with boundaries
• Shape fluctuations and random matrices
• Soft edge results for longest increasing paths on the planar lattice
• The surprising mathematics of longest increasing subsequences

Cited in

(8)

• Transversal fluctuations for increasing subsequences on the plane
• Longest increasing paths with Lipschitz constraints
• scientific article; zbMATH DE number 1775012 (Why is no real title available?)
• scientific article; zbMATH DE number 1867209 (Why is no real title available?)
• scientific article; zbMATH DE number 5585075 (Why is no real title available?)
• Longest increasing path within the critical strip
• Maintaining longest paths incrementally
• Soft edge results for longest increasing paths on the planar lattice

This page was built for publication: Longest increasing paths with gaps

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4972751)