Random orders. (English) Zbl 0565.06002

For fixed integers k and n and a set S of cardinality n let \(P_ k(n)\) be the partial order on S given by the intersection of k randomly and independently chosen linear orders on S. The author begins to study the basic parameters of \(P_ k(n)\) (as height, width, number of extremal elements) for fixed k and large n. His object is to illustrate some techniques for dealing with these random orders and to lay the groundwork for the future research, hoping that they will be found to have useful properties not obtainable by known constructions.
Reviewer: Sh.A.Ayupov


06A06 Partial orders, general
60C05 Combinatorial probability
Full Text: DOI


[1] T. Apostol (1974)Mathematical Analysis, 2nd edn., Addison-Wesley, Reading, Mass. · Zbl 0309.26002
[2] B. Bollob?s (1984)Random Graphs, in preparation.
[3] B. Dushnik and E. W. Miller (1941) Partially ordered sets,Amer. J. Math. 63, 600-610. · Zbl 0025.31002
[4] P. Erd?s and A. R?nyi (1959) On random graphs I,Publ. Math. Debrecen 6, 290-297.
[5] P. Erd?s and A. R?nyi (1960) On evolution of random graphs,Mat. Kutat? Int. K?zl. 5, 17-60.
[6] P. Erd?s and J. Spencer (1974)Probabilistic Methods in Combinatorics, Academic Press, New York. · Zbl 0308.05001
[7] R. Fagin (1976) Probabilities on finite models,J. Symbolic Logic 41, 50-58. · Zbl 0341.02044
[8] P. C. Fishburn (1984) A correlational inequality for linear extensions of a poset,Order 1, 127-137. · Zbl 0562.06002
[9] C. M. Fortuin, P. W. Kasteleyn, and J. Ginibre (1971) Correlation inequalities on some partially ordered sets,Commun. Math. Phys. 22, 89-103. · Zbl 0346.06011
[10] P. R. Halmos (1950)Measure Theory, Van Nostrand, Princeton. · Zbl 0040.16802
[11] D. Kelly and W. T. Trotter (1982) Dimension theory for ordered sets, inOrdered Sets (ed. I. Rival), D. Reidel, Dordrecht. · Zbl 0499.06003
[12] D. J. Kleitman (1966) Families of non-disjoint sets,J. Comb. Theory 1, 153-155. · Zbl 0141.00801
[13] D. J. Kleitman and B. L. Rothschild (1975) Asymptotic enumeration of partial orders on a finite set,Trans. Am. Math. Soc. 205, 205-210. · Zbl 0302.05007
[14] R. M?hring (1985) Asymptotic behavior of ordered sets (Enumeration problem #4) inGraphs and Order (ed. I. Rival), D. Reidel, Dordrecht.
[15] M. Paoli, W. T. Trotter, and J. W. Walker (1985) Graphs and orders in Ramsey theory and in dimension theory, inGraphs and Order (ed. I. Rival), D. Reidel, Dordrecht (to appear). · Zbl 0566.05045
[16] L. A. Shepp (1982) The XYZ conjecture and the FKG inequality,Ann. Prob. 10, 824-827. · Zbl 0484.60010
[17] J. R. Shoenfield (1967)Mathematical Logic, Addison-Wesley, Reading, Mass. · Zbl 0155.01102
[18] E. Szpilrajn (1930) Sur l’extension de l’ordre partiel,Fund. Math. 16, 386-389. · JFM 56.0843.02
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.