Random graph orders
type: Item
instance of: scholarly article
title: Random graph orders
zbMATH Open document ID: 0697.06004
DOI: 10.1007/BF00341633
published in: Order
publication date: 1989-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 06A06
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 60C05
zbMATH DE Number: 4142096
zbMATH Keywords: height
zbMATH Keywords: jump number
zbMATH Keywords: dimension
zbMATH Keywords: random posets
zbMATH Keywords: random graph
zbMATH Keywords: diagram
zbMATH Keywords: transitive closure
zbMATH Keywords: random graph orders
zbMATH Keywords: random diagrams
Wikidata QID: Q57401611
author: Michael Albert
author: Alan Frieze
reviewed by: J. Neggers
MaRDI profile type: Publication
cites work: Weighted sums of certain dependent random variables
cites work: On the Maximal Number of Strongly Independent Vertices in a Random Acyclic Directed Graph
cites work: Probabilities on finite models
cites work: Q5798359
cites work: Minimizing Setups for Ordered Sets: A Linear Algebraic Approach
cites work: Probability Inequalities for Sums of Bounded Random Variables
cites work: Q4076577
cites work: Sharp concentration of the chromatic number on random graphs \(G_{n,p}\)
cites work: Random orders
cites work: Connectedness and diameter for random orders of fixed dimension
full work available at URL: https://doi.org/10.1007/bf00341633
OpenAlex ID: W1974575606
description: scientific article; zbMATH DE number 4142096