A correlational inequality for linear extensions of a poset |
| |
Authors: | Peter C. Fishburn |
| |
Affiliation: | 1. AT & T Bell Laboratories, 07974, Murray Hill, NJ, USA
|
| |
Abstract: | Suppose 1, 2, and 3 are pairwise incomparable points in a poset onn≥3 points. LetN (ijk) be the number of linear extensions of the poset in whichi precedesj andj precedesk. Define λ by $$lambda = frac{{N(213)N(312)}}{{left[ {N(123) + N(132)} right]left[ {N(231) + N(321)} right]}}$$ Two applications of the Ahlswede-Daykin evaluation theorem for distributive lattices are used to prove that λ?(n?1)2/(n+1)2 for oddn, and λ?(n?2)/(n+2) for evenn. Simple examples show that these bounds are best-possible. Shepp (Annals of Probability, 1982) proved thatP(12)?P(12/13), the so-calledxyz inequality, whereP(ij) is the probability thati precedesj in a randomly chosen linear extension of the poset, thus settling a conjecture of I. Rival and B. Sands. The preceding bounds on λ yield a simple proof ofP(12)<P(12/13), which had also been conjectured by Rival and Sands. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|