A correlational inequality for linear extensions of a poset (Q2266724): Difference between revisions

The numbers 1, 2 and 3 are pairwise incomparable points in a poset on \(n\geq 3\) points. Let N(ijk) be the number of linear extensions of the poset in which i precedes j and j precedes k. On this base \(\lambda\) is defined by a special formula. Two applications of the Ahlswede-Daykin evaluation theorem for distributive lattices are used to prove that \(\lambda \leq (n-1)^ 2/(n+1)^ 2\) for odd n, and \(\lambda \leq (n- 2)/(n+2)\) for even n. \textit{L. A. Shepp} [Ann. Probab. 10, 824-827 (1982; Zbl 0484.60010)] proved that P(12)\(\leq P(12| 13)\), the so-called xyz inequality, where P(ij) is the probability that i precedes j in a randomly chosen linear extension of the poset, thus settling a conjecture of Rival and Sands. The preceding bounds on \(\lambda\) yield a simple proof of \(P(12)<P(12| 13)\), which had also been conjectured by Rival and Sands.