Abstract
A relationship is established between (partially) ordered sets of dimension 2 chosen randomly on a labelled set, chosen randomly by isomorphism type, or generated by pairs of random linear orderings. As a consequence we are able to determine the limiting probability (in each of the above sample spaces) that a two-dimensional order is rigid, is uniquely realizable, or has uniquely orientable comparability graph; all these probabilities lie strictly between 0 and 1. Finally, we show that the number of 2-dimensional (partial) orderings of a labelled n-element set is \((1 + o(1))n!^2 /(2\sqrt e ).\).
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
B.Bollobas (1985) Random Graphs, Academic Press, London.
K. J.Compton (1988) The computational complexity of asymptotic problems. I: Partial orders, Inform. and Computation 78, 103–123.
D.Duffus and P.Winkler (1990) On the number of k-realizations of an ordered set, Order 7, 267–273.
B.Dushnik and E. W.Miller (1941) Partially ordered sets, Amer. J. Math. 63, 600–610.
M. El-Zahar and N. W. Sauer (1987), Asymptotic enumeration of two-dimensional posets, U. of Calgary Dept. of Mathematics and Statistics, Research Paper No. 643.
T.Gallai (1967) Transitiv orientierbare Graphen, Acta Math. Acad. Sci. Hungar. 18, 25–66.
D.Kelly (1985) Comparability graphs, in Graphs and Order (ed. I.Rival), D. Reidel, Dordrecht, pp. 3–40.
D.Kelly and W. T.Trotter (1981) Dimension theory for ordered sets, in Ordered Sets (ed. I.Rival), D. Reidel, Dordrecht, pp. 171–211.
D. J.Kleitman and B. L.Rothschild (1975) Asymptotic enumeration of partial orders on a finite set, Trans. Am. Math. Soc. 205, 205–210.
P.Winkler (1985) Random orders, Order 1, 317–331.
P.Winkler (1985) Connectedness and diameter for random orders of fixed dimension, Order 2, 165–171.
P.Winkler (1989) A counterexample in the theory of random orders, Order 5, 363–368.
Author information
Authors and Affiliations
Additional information
Communicated by I. Rival
On leave from Emory University, Atlanta, GA. Research at Emory supported by ONR grant N00014 85-K-0769.
Rights and permissions
About this article
Cite this article
Winkler, P. Random orders of dimension 2. Order 7, 329–339 (1990). https://doi.org/10.1007/BF00383197
Received:
Accepted:
Issue Date:
DOI: https://doi.org/10.1007/BF00383197