The dimension of random ordered sets
In this important paper the authors introduce and study in some detail the space of random bipartite posets \(\Omega=\Omega(n,p)\) with typical elements \(P=(A\cup A',<)\), \(A=\{a_1,\dots,a_n\}\), \(A'=\{a_1',\dots,a_n'\}\) and if \(P\) has \(q\) relations \(a_i<a_j'\), Pr\((P)=p^q(1-p)^{n^2-q}\), with \(0\leq p\leq 1\). The object of the study undertaken here is to facilitate construction of posets with small maximum degree and cardinality but with large dimension, other than the standard example \(s_n\) consisting of the 1-subsets as well as the \((n- 1)\)-subsets of an \(n\)-set ordered by set inclusion. After developing a quantity of basic general theory on \(\Omega(n,p)\) and a great deal of further very delicate work, the authors establish the following key result: (T.3.1): Let \(t=t(n)\) be a non-negative function of \(n\), let \(p=p(n)\) be a function of \(n\) with \(0\leq p\leq 1\). Suppose that: (1) \(\lim_{n\to \infty}np=\infty\); (2) \(\lim_{n\to \infty}t/p(n-t)=\infty\); (3) \(\lim_{n\to \infty}\exp[\alpha][1-(1-p)\exp[\beta]]^\gamma =0\), with \(\alpha = 4t\log n\log np/p\), \(\beta=-24t/p(n-t)\), \(\gamma=p^2(n-t)^3/512\log^2np\). Then \(\dim P>t\) for almost all \(P\in \Omega(n,p)\). Using this theorem, then, given \(\varepsilon>0\) and \(t=\delta np\log np/(1+\delta p\log np)\), a careful computation/estimate yields the authors' (T.1.5): For every \(\varepsilon>0\), there exists a \(\delta>0\) so that if \((\log^{1+\varepsilon}n)/n<p\), \(1-n^{-1+\varepsilon}\), then \(\dim P>t\) for almost all \(P\in \Omega(n,p)\). Using (T.1.5) other inequalities are obtained which are useful in dimension estimates. The results reported here are compared to other obtained by Füredi and Kahn using probabilistic techniques. Furthermore, the authors use methods of Kleitman and Rothschild and some related to those developed by themselves to obtain inequalities for the space of labelled posets on \(n\) points uniformly distributed as in (T.1.7): There exist absolute constants \(c_1,c_2>0\) so that: \(n/4(1-c_1/\log n)<\dim P< n/4(1-c_2/\log n)\), for almost all labeled posets on \(n\) points. They close the paper with a collection of remarks and questions which will be points of departure for further developments in dimension theory for random posets of different types.
- An inequality for the weights of two families of sets, their unions and intersections
- Asymptotic Enumeration of Partial Orders on a Finite Set
- Families of Non-disjoint subsets
- scientific article; zbMATH DE number 4085656 (Why is no real title available?)
- scientific article; zbMATH DE number 3318560 (Why is no real title available?)
- On Representatives of Subsets
- A counterexample in the theory of random orders
- Random orders of dimension 2
- First order properties of random posets
- Linear extensions of random orders
- Incidence posets of trees in posets of large dimension
- On poset similarity
- Fractional dimension of partial orders
- A strange pigeon-hole principle
- On the order dimension of 1-sets versus k-sets
- Fractional local dimension
- Local boxicity
- Random bipartite posets and extremal problems
- The graph of critical pairs of a crown
- Cubicity, degeneracy, and crossing number
- Local boxicity and maximum degree
- One-dimensional central measures on numberings of ordered sets
- On Supremal and Maximal Sets with Respect to Random Partial Orders
- A note on random k-dimensional posets
- Forcing posets with large dimension to contain large standard examples
- 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
- An Ordered Random Set Coupling
- scientific article; zbMATH DE number 1339888 (Why is no real title available?)
- scientific article; zbMATH DE number 1948237 (Why is no real title available?)
- Random high-dimensional orders
- The length of random subsets of Boolean lattices
- Boxicity and topological invariants
- Better bounds for poset dimension and boxicity
- scientific article; zbMATH DE number 970805 (Why is no real title available?)
- The random binary growth model
- Bounding threshold dimension: realizing graphic Boolean functions as the AND of majority gates
- Boxicity, poset dimension, and excluded minors
- A survey on the boxicity and cubicity of graphs
- Some bounds on the threshold dimension of graphs
- Word-representation numbers of graphs: bottlenecks and bounds
- Random graph orders
This page was built for publication: The dimension of random ordered sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3977080)