Proportional Transitivity in Linear Extensions of Ordered Sets

01 January 1986

New Image

Let p sub (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 sub 12=1, p sub 23=1, and similarly fo rpermutations of 123. The corresponding probabilistic or proportional transitivity law asserts that, for all (lambda, Mu) in the unit square, (p sub 12 >= lambda, p sub 23 >= Mu)->p sub 13 >= int(lambda, Mu), where int(lambda,Mu) is the infimum of p sub 13 over all finite posets that have p sub 12 >= lambda and p sub 23 >=Mu.