首页 | 本学科首页   官方微博 | 高级检索  
     


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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号