Random orders of dimension 2 (Q1177705): Difference between revisions

Let \(P_ k\) be the random poset of dimension \(k\) on \(n\) elements obtained by intersecting \(k\) randomly and independently chosen linear orders; let \(P_ 2(n)=P(n)\) (also \(P_ 2(n)=\hbox{Ran}(n)\) elsewhere). Then, although in \(P=\bigcup_{k,n}P_ k(n)\), the finite posets, the \(0-1\) law holds, it is not true for \(P_ 2=\bigcup_ n P_ 2(n)\). Indeed, Winkler and Brightwell have observed that there are simple first- order properties with limits \((n\to\infty)\) other than 0 and 1 and Spencer has shown that such limits may even fail to exist. In this paper the author investigates the random poset \(P(n)\) as well as random variables \(Q(n)\) (all 2-dimensional orderings are equiprobable), \(U(n)\) (all isomorphism types, types are equiprobable) and \(I(n)\) (the number of realizations of the isomorphism class \([P(n)])\). Using a sequence of clever counting and structural lemmas the author shows that (Theorem 2.1) the number of elements in the range of \(P_ 2(n)\) is \((1+O(1)n!^ 2/(2\sqrt e)\), while (Theorem 4.5) the number of elements in the range of \(U(n)\) is \((1+O(1)n!/2\) (also proven by El-Zahar and Sauer). Since the random variables described represent distinct methods of obtaining random posets, it is also of interest to compare limiting probabilities as in Corollary 3.2, e.g.: Any statement with limiting probability in (0,1) in \(P(n)\) has limiting probability in (0,1) in \(Q(n)\). Similarly, if the limiting probability is 0 or 1 in \(P\), then it is so in \(Q(n)\). Thus, Spencer's result may also be considered relative to both ranges. The author also shows that for the properties `rigid', `uniquely realizable' and `has a uniquely transitively orientable comparability graph' the limiting probabilities are \(1/e\) in \(P(n)\) and \(1/(2\sqrt e)\) in \(Q(n)\).