On the Height of a Random Set of Points in a d-Dimensional Unit Cube

Abstract

We investigate, through numerical experiments, the asymptotic behavior of the length H_d(n) of a maximal chain (longest totally ordered subset) of a set of n points drawn from a uniform distribution on the d-dimensional unit cube V _D = [0, 1]_d. For d ≥ 2, it is known that c_d(n) = H_d(n)/n^1/d converges in probability to a constant C_d < e, with Iim _d→∞ C_d = e. For d = 2, the problem has been extensively studied, and it is known that C₂ = 2; C_d is not currently known for any d ≥ 3. Straightforward Monte Carlo simulations to obtain C_d have already been proposed, and shown to be beyond the scope of current computational resources. In this paper, we present a computational approach which yields feasible experiments that lead to estimates for C_d. We prove that H_d(n) can be estimated by considering only those chains close to the diagonal of the cube. A new conjecture regarding the asymptotic behavior of c_d(n) leads to even more efficient experiments. We present experimental support for our conjecture, and the new estimates of C_d obtained from our experiments, for d ∈ {3,4,S,6}.