Random graph orders
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.
- Connectedness and diameter for random orders of fixed dimension
- scientific article; zbMATH DE number 3493681 (Why is no real title available?)
- scientific article; zbMATH DE number 3059214 (Why is no real title available?)
- Minimizing Setups for Ordered Sets: A Linear Algebraic Approach
- On the Maximal Number of Strongly Independent Vertices in a Random Acyclic Directed Graph
- Probabilities on finite models
- Probability Inequalities for Sums of Bounded Random Variables
- Random orders
- Sharp concentration of the chromatic number on random graphs \(G_{n,p}\)
- Weighted sums of certain dependent random variables
- Random orders of dimension 2
- First order properties of random posets
- On poset similarity
- On tail distribution of interpost distance
- The reversal ratio of a poset.
- Parallel execution of schedules with random dependency graph
- Uniform random posets
- A phase transition phenomenon in a random directed acyclic graph
- A note on random k-dimensional posets
- Continuum limits for classical sequential growth models
- Performance considerations on a random graph model for parallel processing
- scientific article; zbMATH DE number 446489 (Why is no real title available?)
- Box-Spaces and Random Partial Orders
- The dimension of random ordered sets
- The Structure of Random Graph Orders
- Random graph orders do not satisfy a 0–1 law
- scientific article; zbMATH DE number 845729 (Why is no real title available?)
- scientific article; zbMATH DE number 1420916 (Why is no real title available?)
- Onset of the asymptotic regime for (uniformly random) finite orders
- Evaluating topological ordering in directed acyclic graphs
- Zero-one laws with variable probability
- scientific article; zbMATH DE number 970794 (Why is no real title available?)
- The random binary growth model
- Order-invariant measures on causal sets
- Logical limit laws for Mallows random permutations
- Loose paths in random ordered hypergraphs
This page was built for publication: Random graph orders
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q911622)
