The height of a random partial order: Concentration of measure. (English) Zbl 0758.06001

Summary: The problem of determining the length \(L_ n\) of the longest increasing subsequence in a random permutation of \(\{1,\dots,n\}\) is equivalent to that of finding the height of a random two-dimensional partial order (obtained by intersecting two random linear orders). The expectation of \(L_ n\) is known to be about \(2\sqrt n\). Frieze investigated the concentration of \(L_ n\) about this mean, showing that, for \(\varepsilon>0\), there is some constant \(\beta>0\) such that \[ \text{Pr}(| L_ n-{\mathbf E}L_ n|\geq n^{1/3+\varepsilon})\leq\exp(-n^ \beta). \] In this paper we obtain similar concentration results for the heights of random \(k\)-dimensional orders, for all \(k\geq 2\). In the case \(k=2\), our method replaces the \(n^{1/3+\varepsilon}\) above with \(n^{1/4+\varepsilon}\), which we believe to be essentially best possible.


06A06 Partial orders, general
60C05 Combinatorial probability
05A99 Enumerative combinatorics
Full Text: DOI