×

zbMATH — the first resource for mathematics

Proportional transitivity in linear extensions of ordered sets. (English) Zbl 0566.06002
Let \(p_{ij}\) denote the proportion of all linear extensions \(>*\) of a partial order on \(\{\) 1,2,3,...,n\(\}\) in which \(i>*j\). The deterministic transitivity law for the subset \(\{\) 1,2,3\(\}\) says that \((p_{12}=1,p_{23}=1)\Rightarrow p_{13}=1\), and similarly for permutations of 123. The corresponding probabilistic or proportional transitivity law asserts that, for all (\(\lambda\),\(\mu)\) in the unit square, \((p_{12}\geq \lambda,p_{23}\geq \mu)\Rightarrow p_{13}\geq f(\lambda,\mu)\), where f(\(\lambda\),\(\mu)\) is the infimum of \(p_{13}\) over all finite posets that have \(p_{12}\geq \lambda\) and \(p_{23}\geq \mu.\)
It is shown that \(f(\lambda,\mu)=0\) when \(\lambda +\mu <1\), and \(f(1,\mu)=\mu\). Moreover, f(\(\lambda\),1-\(\lambda)\leq 1/e\), and, when \(\lambda +\mu >1\) and \(\max \{\lambda,\mu \}<1\), f(\(\lambda\),\(\mu)\leq 1- (1-\lambda)(1-\mu)[1-\log (1-\lambda)(1-\mu)]\). The exact value of f is presently unknown for every case in which \(\lambda +\mu \geq 1\) and \(\max \{\lambda,\mu \}<1\).

MSC:
06A06 Partial orders, general
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Fishburn, P.C, On the family of linear extensions of a partial order, J. combin. theory, 17, 240-243, (1974) · Zbl 0274.06003
[2] Fishburn, P.C, On linear extension majority graphs of partial orders, J. combin. theory, 21, 65-70, (1976) · Zbl 0294.06001
[3] Fishburn, P.C, A correlational inequality for linear extensions of a poset, Order, 1, 127-137, (1984) · Zbl 0562.06002
[4] Lang, S, ()
[5] Shepp, L.A, The XYZ conjecture and the FKG inequality, Ann. probab., 10, 824-827, (1982) · Zbl 0484.60010
[6] Stanley, R.P, Two combinatorial applications of the Alexandrov-Fenchel inequalities, J. combin. theory ser. A, 31, 56-65, (1981) · Zbl 0484.05012
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.