Connectedness and diameter for random orders of fixed dimension |
| |
Authors: | Peter Winkler |
| |
Institution: | (1) Department of Mathematics, Emory University, 30322 Atlanta, GA, U.S.A. |
| |
Abstract: | Let P
k
(n) be the (partial) order determined by intersecting k random linear orderings of a set of size n; equivalently, let P
k
(n) consist of n points chosen randomly and independently from the unit cube in
k
, with the induced product order. We show for each fixed k>1, that with probability approaching 1 as n![rarr](/content/j3j3135277165j63/xxlarge8594.gif) , the comparability graph of P
k
(n) is connected and has diameter 3. |
| |
Keywords: | 06A10 60C05 |
本文献已被 SpringerLink 等数据库收录! |
|