Correlation Among Partial Orders
Peter M. Winkler · SIAM Journal on Algebraic and Discrete Methods · 1983
If A is a poset and P is a (finite) poset whose underlying set contains the elements of A, then A is said to occur in a linear extension L of P if each relation in A is realized in L; if L is chosen at random, A can be regarded as an event whose probability is the number of linear extensions in which it occurs divided by the total number of linear extensions of P. We give a complete characterization of the pairs of partial orders which are never negatively correlated, i.e., the pairs A, B with the following property: for any poset P whose underlying set contains the elements of A and of B, $\text{Pr} ( A\,{\text{and}}\,B )\geqq \text{Pr} ( A ) \text{Pr} ( B )$.