RANDOM HIGH-DIMENSIONAL ORDERS

The random k-dimensional partial order P-k(n) on n points is defined b y taking n points uniformly at random from [0, 1](k). Previous work ha s concentrated on the case where k is constant: we consider the model where k increases with n. We pay particular attention to the height H- k(n) of P-k(n). We show that k = (t/log t!) log n is a sharp threshold function for the existence of a t-chain in P-k(n): if k - (t/log t!) log n tends to +proportional to then the probability that P-k(n) conta ins a t-chain tends to 0; whereas if the quantity tends to -proportion al to, then the probability tends to 1. We describe the behaviour of H -k(n) for the entire range of k(n). We also consider the maximum degre e of P-k(n). We show that, for each fixed d greater than or equal to 2 , k = e log n -1/2log log n is a threshold function for the appearance of an element of degree d. Thus the maximum degree undergoes very rap id growth near this value of k. We make some remarks on the existence of threshold functions in general, and give some bounds on the dimensi on of P-k(n) for large k(n).