On Increasing Sequences Formed by Points from a Random Finite Subset of a Hypercube

Abstract

Consider $S$, a set of $n$ points chosen uniformly at random and independently from the unit hypercube of dimension $t>2$. Order $S$ by using the Cartesian product of the $t$ standard orders of $[0,1]$. We determine a constant $\bar x(t)<e$ such that, with probability $\ge 1-\exp(-\Theta(\varepsilon)n^{1/t})$, cardinality of a longest chain, i.e., a largest subset of comparable points, is at most $(\bar x(t)+\varepsilon)n^{1/t}$. The bound $\bar x(t)$ complements an explicit lower bound obtained by Bollobás and Winkler in 1988.