## Large deviations for increasing sequences on the plane.(English)Zbl 0919.60040

Start with a homogeneous rate one Poisson point process on the plane. A sequence $$(x_1,t_1)$$, $$(x_2,t_2),\ldots, (x_m,t_m)$$ of these points is called increasing if $$x_1<x_2<\cdots<x_m$$ and $$t_1<t_2<\cdots<t_m$$. For $$-\infty<a<b<\infty$$ and $$0\leq s<t$$, let $${\mathbb L}((a,s),[b,t])$$ equal the maximal number of points on an increasing sequence contained in the rectangle $$(a,b]\times(s,t]$$. These random variables are independent for disjoint rectangles, the translation invariance of the Poisson points gives stationarity, and there is a built-in superadditivity. It is known that a nonrandom limit $$\gamma(x,t)=\lim_{n\to\infty}n^{-1}{\mathbb L}((0,0),(nx,nt))$$ exists a.s. for $$x,t\geq 0$$. Moreover, $$\gamma(x,t)=c\sqrt{xt}$$ for the constant $$c=\lim_{n\to\infty}n^{-1}L_n$$. Originally $$c$$ was defined through a random permutation. Choose a permutation on $$n$$ symbols uniformly at random among the $$n!$$ possible permutations, and let $$\Lambda_n$$ be the length of the longest increasing subsequence of the permutation. Then the same constant $$c$$ appears as the limit $$c=\lim_{n\to\infty}n^{-1/2}\Lambda_n$$. A. M. Vershik and S. V. Kerov [Sov. Math., Dokl. 18, 527-531 (1977); translation from Dokl. Akad. Nauk SSSR 233, 1024-1027 (1977; Zbl 0406.05008)] proved that $$c=2$$. The proof is combinatorial and makes use of Young diagrams. In the paper under review, the large deviations from the limit laws $$n^{-1}L_n\to 2$$ and $$n^{-1/2}\Lambda_n\to 2$$ are discussed. The rate function for lower tail deviations is derived from a result of B. F. Logan and L. A. Shepp [Adv. Math. 26, 206-222 (1977; Zbl 0363.62068)] about Young diagrams of random permutations. For the upper tail we use a coupling with Hammersley’s particle process and convex-analytic techniques.

### MSC:

 60F10 Large deviations 60C05 Combinatorial probability 60K35 Interacting random processes; statistical mechanics type models; percolation theory

### Citations:

Zbl 0406.05008; Zbl 0363.62068
Full Text: