Random partial orders defined by angular domains
Suppose we select, uniformly and at random, \(d=d(n)\) of the \(n!\) total orders of \([n]=\{1,2,\ldots n\}\). We then define a \(d\)-dimensional random partial order \(\prec\) by saying that \(x\prec y\) if and only if \(x\leq y\) in all \(d\) of the total orders. This is equivalent to choosing \(n\) points uniformly and at random in the \(d\)-dimensional unit cube \(Q_{d}\) and then saying that one point is less than or equal to another if and only if it is less than or equal to it in all \(d\) components. The paper under review modifies this by noting that if \(d=2\), \(P_{1}\prec P_{2}\) if and only if \(P_{2}\) is in the positive upper quadrant defined by the two axis-parallel axes through \(P_{1}\), and replacing the two axes (at angle \(\pi/2\) to each other) with another angle \(0\leq \alpha\leq \pi\). More formally, given \(P_{1}=(x_{1},y_{1})\) and \(P_{2}=(x_{2},y_{2})\), say \(P_{1}\prec P_{2}\) in the \(\alpha\)-ordering if and only if \(x_{1}+y_{1}\leq x_{2}+y_{2}\) and \(P_{2}\) lies in the open angular domain at \(P_{1}\) of angle \(\alpha\) with angle bisector parallel to the line \(y=x\). Carrying out this process for \(n\) points selected uniformly and at random we get a random partial order \({\mathcal P}_{\alpha,n}\). (Thus the classical case is when \(\alpha=\pi/2\).) The main topic of interest is the question of the length of the longest chain \(L_{\alpha, n}\) in this random poset. (In the classical \(2\)-dimensional partial order, the answer is close to \(2\sqrt{n}\), see the paper for a much more precise summary.) The main result is that \(L_{\alpha,n}\) is, except for \(\alpha\) extremely close to 0 or 1, about \(2\sqrt{n\tan (\alpha/2)}\). More precisely, using \(f(n)=\omega g(n)\) to mean that \(f(n)/g(n)\rightarrow \infty\) as \(n\rightarrow\infty\), we have, provided \(\omega(\log^{2}(n)/n)\leq \alpha\leq \pi-\omega(1/n)\) \(L_{\alpha,n}/\sqrt{n\tan(\alpha/2)}\rightarrow 2\) as \(n\rightarrow \infty\), the convergence being convergence in probability. The authors show a similar result for points from a Poisson process with mean \(n\) as opposed to a genuinely uniform distribution, and also show that the result fails if \(\alpha=o(\log^{2}(n)/n)\) or \(\alpha=\pi-o(1/n)\). We can also consider the comparability graph \(G_{\alpha, n}\) of the partial order, where two vertices of the partial order are adjacent if and only if they are comparable. The authors show that \(G_{\alpha, n}\) has diameter 1 if \(\pi-\alpha=o(n^{-2})\), 2 if \(\pi-\alpha=\omega(n^{-2})\) and \(\alpha-\pi/2=\omega(n^{-1/2})\), and 3 if \(0\leq \alpha-\pi/2=o(n^{-1/2})\). Again, corresponding results hold in the Poisson process rather than uniform distribution. Though some of the proofs focus on a natural transformation to choosing points in a rhombus and arguing with the classical \(\pi/2\)-partial order, the authors note that their parametrization gives a natural `evolution' of a random poset from an antichain when \(\alpha=0\) to a chain when \(\alpha=\pi\) and this allows them to define an appropriate notion of hitting times for monotone properties. For example, they show that the hitting time for having a connected comparability graph is \(\pi/2\). They can similarly show that the evolution of \(G_{\alpha, n}\) differs from that of an Erdős-Rényi random graph, in that there is a strictly positive limiting probability that the graph is disconnected but contains no isolated vertex.
- A variational problem for random Young tableaux
- Box-Spaces and Random Partial Orders
- Connectedness and diameter for random orders of fixed dimension
- scientific article; zbMATH DE number 446489 (Why is no real title available?)
- scientific article; zbMATH DE number 3630761 (Why is no real title available?)
- scientific article; zbMATH DE number 1047715 (Why is no real title available?)
- scientific article; zbMATH DE number 3373691 (Why is no real title available?)
- Longest increasing subsequences: from patience sorting to the Baik-Deift-Johansson theorem
- On increasing subsequences of random permutations
- On the distribution of the length of the longest increasing subsequence of random permutations
- On the length of the longest monotone subsequence in a random permutation
- Random orders
- The height of a random partial order: Concentration of measure
- The Longest Chain Among Random Points in Euclidean Space
This page was built for publication: Random partial orders defined by angular domains
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q634753)
