×

zbMATH — the first resource for mathematics

Random graph orders. (English) Zbl 0697.06004
Random graphs are graphs associated with a probability measure depending on rules of “construction” of the random graph. Random posets are considered in a similar light. Thus, the same poset P may be the poset element of several different random posets. In this very interesting paper the authors construct a random poset from a random graph with the p-value usually taken at \(1/2\) and the set of vertices taken to be \(\{1,...,n\}\) for some fixed n. The orientation is provided by the order \(i<j\) if (ij) is an edge and i is the smaller integer, then extending this by taking transitive closure. In constructing the diagram only covering relations are retained, so that some edges may be dropped from the original graph. Some parameters of the poset, such as height, will not be affected by the process of taking a transitive closure. The random posets obtained in the manner described are referred to as random graph orders (of a particular p-value). The authors demonstrate the existence of constants c and r such that:
(1) \(.5654<c<.610\) and Pr(\(\lim_{n\to \infty}H_ n/n=c)=1\) where \(H_ n\) is the height of an n-point random graph order \((p=);\)
(2) \(.034<r<.289\) and Pr(\(\lim_{n\to \infty}S_ n/n=c)=1\) where \(S_ n\) is the set-up or jump number of an n point random graph order \((p=).\)
The flow of the counting arguments used indicates that the class developed is a nice one and corresponds well to intuitive notions of what one might expect. Other ideas are discussed, including the failure of the 0-1 law in the case of existence of unique minimal elements and a conjecture that dimension \(D_ n\) is sharply concentrated with expected value approximately \(\sqrt{2 \log n/\log 2}\). In order to study random diagrams it appears that the approach taken in this paper could also be a most natural one.

MSC:
06A06 Partial orders, general
05C80 Random graphs (graph-theoretic aspects)
60C05 Combinatorial probability
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] K. Azuma (1967) Weighted sums of certain dependent random variables, Tokuku Math. J. 19, 357-367. · Zbl 0178.21103 · doi:10.2748/tmj/1178243286
[2] A. Barak and P. Erdös (1984) On the maximal number of strongly independent vertices in a random acyclic directed graph, SIAM J. Algebraic Discete Methods 5, 508-514. · Zbl 0558.05026 · doi:10.1137/0605049
[3] K. Compton (1987) The computational complexity of asymptotic problems I: Partial orders (preprint).
[4] R. Fagin (1976) Probabilities on finite models, J. Symbolic Logic 41, 50-58. · Zbl 0341.02044 · doi:10.2307/2272945
[5] William Feller (1950) An Introduction to Probability Theory and its Applications, (2nd edn.), Wiley, New York. · Zbl 0039.13201
[6] G. Gierz and W. Poguntke (1983) Minimizing setups for ordered sets: a linear algebraic approach, SIAM J. Algebraic Discrete Methods 4, 132-144. · Zbl 0517.06004 · doi:10.1137/0604016
[7] W. Hoeffding (1963) Probability inequalities of sums of bounded random variables, J. Amer. Stat. Assoc. 58, 13-30. · Zbl 0127.10602 · doi:10.2307/2282952
[8] S. Karlin and H. M. Taylor (1975) A First Course in Stochastic Processes. Academic Press, New York. · Zbl 0315.60016
[9] G. Polya and G. Szëgo (1972) Problems and Theorems in Analysis 1, Springer-Verlag, New York.
[10] E. Shamir and J. Spencer (1987) Sharp concentration of the chromatic numbers on random graphs G n,p, Combinatiorica 7, 121-129. · Zbl 0632.05024 · doi:10.1007/BF02579208
[11] P. Winkler (1984) Random orders, Order 1, 317-331. · Zbl 0565.06002 · doi:10.1007/BF00582738
[12] P. Winkler (1985) Connectedness and diameter for random orders of fixed dimension. Order 2, 165-171. · Zbl 0581.06001 · doi:10.1007/BF00334854
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.