×

zbMATH — the first resource for mathematics

A correlational inequality for linear extensions of a poset. (English) Zbl 0562.06002
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.
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.
Reviewer: F.V.Burshtein

MSC:
06A06 Partial orders, general
05A20 Combinatorial inequalities
60C05 Combinatorial probability
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] R. Ahlswede and D. E. Daykin (1978) An inequality for the weights two families of sets, their unions and intersections,Z. Wahrscheinlichkeitstheorie and Verw. Gebeite 43, 183-185. · Zbl 0357.04011 · doi:10.1007/BF00536201
[2] K. P. Bogart (1973) Maximal dimensional partially ordered sets. I. Hiraguchi’s theorem,Discrete Math. 5, 21-31. · Zbl 0262.06001 · doi:10.1016/0012-365X(73)90024-1
[3] C. M. Fortuin, P. W. Kasteleyn, and J. Ginibre (1971) Correlation inequalities on some partially ordered sets,Comm. Math. Phys. 22, 89-103. · Zbl 0346.06011 · doi:10.1007/BF01651330
[4] R. L. Graham (1983) Applications of the FKG inequality and its relatives, inConference Proceedings, 12th Intern. Symp. Math. Programming, Springer, pp. 115-131. · Zbl 0561.06006
[5] L. A. Shepp (1980) The FKG inequality and some monotonicity properties of partial orders,SIAM J. Alg. Disc. Meth. 1, 295-299. · Zbl 0501.06006 · doi:10.1137/0601034
[6] L. A. Shepp (1982) The XYZ conjecture and the FKG inequality,Ann. Prob. 10, 824-827. · Zbl 0484.60010 · doi:10.1214/aop/1176993791
[7] P. M. Winkler (1983) Correlation among partial orders,SIAM J. Alg. Disc. Meth. 4, 1-7. · Zbl 0508.06004 · doi:10.1137/0604001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.