Connectedness and diameter for random orders of fixed dimension
Choose n points independently from the uniform distribution in \([0,1]^ k\) and define \(x\leq y\) if \(x_ i\leq y_ i\) for each i, \(1\leq i\leq k\). The obtained partial order \(P_ k(n)\) is said to be connected if the comparability graph \(G_ k(n)\) of \(P_ k(n)\) is connected. The diameter diam \(P_ k(n)\) is the least j such that any two vertices of \(G_ n(k)\) are connected by a path of length at most j. Theorem. Fix \(k>1\), then with probability approaching 1 as \(n\to \infty\), \(P_ k(n)\) is connected and diam \(P_ k(n)=3\).
- A counterexample in the theory of random orders
- Random orders of dimension 2
- Sequential selection of an increasing sequence from a multidimensional random sample.
- Uniform random posets
- scientific article; zbMATH DE number 4091572 (Why is no real title available?)
- LINKING OF RANDOM p-SPHERES IN Zd
- 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
This page was built for publication: Connectedness and diameter for random orders of fixed dimension
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1068112)
