Proportional transitivity in linear extensions of ordered sets (Q1059089): Difference between revisions

Let \(p_{ij}\) denote the proportion of all linear extensions \(>*\) of a partial order on \(\{\) 1,2,3,...,n\(\}\) in which \(i>*j\). The deterministic transitivity law for the subset \(\{\) 1,2,3\(\}\) says that \((p_{12}=1,p_{23}=1)\Rightarrow p_{13}=1\), and similarly for permutations of 123. The corresponding probabilistic or proportional transitivity law asserts that, for all (\(\lambda\),\(\mu)\) in the unit square, \((p_{12}\geq \lambda,p_{23}\geq \mu)\Rightarrow p_{13}\geq f(\lambda,\mu)\), where f(\(\lambda\),\(\mu)\) is the infimum of \(p_{13}\) over all finite posets that have \(p_{12}\geq \lambda\) and \(p_{23}\geq \mu.\) It is shown that \(f(\lambda,\mu)=0\) when \(\lambda +\mu <1\), and \(f(1,\mu)=\mu\). Moreover, f(\(\lambda\),1-\(\lambda)\leq 1/e\), and, when \(\lambda +\mu >1\) and \(\max \{\lambda,\mu \}<1\), f(\(\lambda\),\(\mu)\leq 1- (1-\lambda)(1-\mu)[1-\log (1-\lambda)(1-\mu)]\). The exact value of f is presently unknown for every case in which \(\lambda +\mu \geq 1\) and \(\max \{\lambda,\mu \}<1\).