The longest chain among random points in Euclidean space

Abstract:

Let $n$ random points be chosen independently from the uniform distribution on the unit $k$-cube ${[0,1]^k}$. Order the points coordinate-wise and let ${{\mathbf {H}}_k}\left ( n \right )$ be the cardinality of the largest chain in the resulting partially ordered set. We show that there are constants ${c_1},{c_2}, \ldots$ such that ${c_k} < e,\;{\lim _{k \to \infty }}{c_k} = e$, and ${\lim _{n \to \infty }}{{\mathbf {H}}_k}\left ( n \right )/{n^{1/k}} = {c_k}$ in probability. This generalizes results of Hammersley, Kingman and others on Ulam’s ascending subsequence problem, and settles a conjecture of Steele.