Boris Pittel
The Ohio State University
Title
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 \geq 1 – exp(-\Theta(ε)*n^{1/t}), cardinality of a longest chain, i.e. a largest subset of comparable points, is at most (\bar{x}(t) + \epsilon)*n^{1/t}. The bound \bar{x}(t) complements an explicit lower bound obtained by Bollobas and Winkler in 1988. Furthermore, we use Dilworth’s theorem on partitions of a set into chains to prove that the cardinality of a largest antichain, i.e. a largest subset of incomparable points, is at least (1-\epsilon)*(n/e)^{1−1/t} with probability exponentially close to 1.
