The Height of a Random Partial Order: Concentration of Measure

The problem of determining the length Lₙ of the longest increasing subsequence in a random permutation of \1, …, 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ₙ is known to be about 2√n. Frieze investigated the concentration of Lₙ about this mean, showing that, for ε > 0, there is some constant β > 0 such that Pr(|Lₙ - ELₙ| ≥ n1/3+ε) ≤ exp(-n^β). In this paper we obtain similar concentration results for the heights of random k-dimensional orders, for all k ≥ 2. In the case $k = 2$, our method replaces the n1/3+ε above with n1/4+ε, which we believe to be essentially best possible.