Random partial orders defined by angular domains (Q634753): Difference between revisions

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.