Random orders of dimension 2
Let \(P_ k\) be the random poset of dimension \(k\) on \(n\) elements obtained by intersecting \(k\) randomly and independently chosen linear orders; let \(P_ 2(n)=P(n)\) (also \(P_ 2(n)=\hbox{Ran}(n)\) elsewhere). Then, although in \(P=\bigcup_{k,n}P_ k(n)\), the finite posets, the \(0-1\) law holds, it is not true for \(P_ 2=\bigcup_ n P_ 2(n)\). Indeed, Winkler and Brightwell have observed that there are simple first- order properties with limits \((n\to\infty)\) other than 0 and 1 and Spencer has shown that such limits may even fail to exist. In this paper the author investigates the random poset \(P(n)\) as well as random variables \(Q(n)\) (all 2-dimensional orderings are equiprobable), \(U(n)\) (all isomorphism types, types are equiprobable) and \(I(n)\) (the number of realizations of the isomorphism class \([P(n)])\). Using a sequence of clever counting and structural lemmas the author shows that (Theorem 2.1) the number of elements in the range of \(P_ 2(n)\) is \((1+O(1)n!^ 2/(2\sqrt e)\), while (Theorem 4.5) the number of elements in the range of \(U(n)\) is \((1+O(1)n!/2\) (also proven by El-Zahar and Sauer). Since the random variables described represent distinct methods of obtaining random posets, it is also of interest to compare limiting probabilities as in Corollary 3.2, e.g.: Any statement with limiting probability in (0,1) in \(P(n)\) has limiting probability in (0,1) in \(Q(n)\). Similarly, if the limiting probability is 0 or 1 in \(P\), then it is so in \(Q(n)\). Thus, Spencer's result may also be considered relative to both ranges. The author also shows that for the properties `rigid', `uniquely realizable' and `has a uniquely transitively orientable comparability graph' the limiting probabilities are \(1/e\) in \(P(n)\) and \(1/(2\sqrt e)\) in \(Q(n)\).
- A counterexample in the theory of random orders
- Asymptotic Enumeration of Partial Orders on a Finite Set
- Connectedness and diameter for random orders of fixed dimension
- scientific article; zbMATH DE number 3914376 (Why is no real title available?)
- scientific article; zbMATH DE number 3769673 (Why is no real title available?)
- On the number of k-realizations of an ordered set
- Partially Ordered Sets
- Random orders
- The computational complexity of asymptotic problems. I: Partial orders
- Transitiv orientierbare Graphen
- A counterexample in the theory of random orders
- Nonconvergence in the theory of random orders
- On poset similarity
- Scaling limits for width two partially ordered sets: the incomparability window
- The causal set approach to quantum gravity
- Poset limits and exchangeable random posets
- A note on random k-dimensional posets
- The Ising model coupled to 2d orders
- scientific article; zbMATH DE number 446489 (Why is no real title available?)
- Box-Spaces and Random Partial Orders
- Existence thresholds and Ramsey properties of random posets
- scientific article; zbMATH DE number 3946188 (Why is no real title available?)
- The dimension of random ordered sets
- Ramsey Theory and Sequences of Random Variables
- Onset of the asymptotic regime for (uniformly random) finite orders
- Dimensionally restricted causal set quantum gravity: examples in two and three dimensions
- The random binary growth model
- Random partial orders defined by angular domains
- Random k-dimensional orders: Width and number of linear extensions
- On increasing sequences formed by points from a random finite subset of a hypercube
- Random graph orders
- Random variables related to a class of ordered structures
This page was built for publication: Random orders of dimension 2
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1177705)
