A correlational inequality for linear extensions of a poset
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.
- An inequality for the weights of two families of sets, their unions and intersections
- Correlation Among Partial Orders
- Correlation inequalities on some partially ordered sets
- scientific article; zbMATH DE number 3893259 (Why is no real title available?)
- Maximal dimensional partially ordered sets. I: Hiraguchi's theorem
- The FKG Inequality and Some Monotonicity Properties of Partial Orders
- The XYZ conjecture and the FKG inequality
- Random orders
- Proportional transitivity in linear extensions of ordered sets
- Universal correlations in finite posets
- Some correlation inequalities in finite posets
- Maximizing a correlational ratio for linear extensions of posets
- Linear extensions of infinite posets
- Correlation in partially ordered sets
- On proportional transitivity of ordered sets
- A combinatorial approach to correlation inequalities
- Balancing pairs and the cross product conjecture
- The 1/3–2/3 Conjecture for 5-Thin Posets
- The cross-product conjecture for width two posets
- Extensions of the Kahn-Saks inequality for posets of width two
- Effective Poset Inequalities
- Multivariate correlation inequalities for \(P\)-partitions
- A combinatorial approach to height sequences in finite partially ordered sets
- Order-invariant measures on causal sets
- First-Fit is linear on posets excluding two long incomparable chains
- A q-analogue of the FKG inequality and some applications
- Correlation inequalities for linear extensions
- Equality cases of the Alexandrov-Fenchel inequality are not in the polynomial hierarchy
- A note on linear extensions and incomparable pairs
- Events correlated with respect to every subposet of a fixed poset
This page was built for publication: A correlational inequality for linear extensions of a poset
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2266724)
