ISSN:
1572-9273
Keywords:
06A10
;
Poset
;
linear extension
;
correlation
;
universal correlation
;
Winkler's Theorem
;
universal negative correlation
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
Abstract Posets A, B⫇X×X, with X finite, are said to be universally correlated (A↑B) if, for all posets R over X, (i.e., all posets R⫇Y×Y with X⫇Y), we have P(R∪A) P(R∪B)≤P(R∪A∪B) P(R). Here P(R∪A), for instance, is the probability that a randomly chosen bijection from Y to the totally ordered set with |Y| elements is a linear extension of R∪A. We show that A↑B iff, for all posets R over X, P(R∪A) P(R∪B)≤P(R∪A∪B) P(R∪(A∩B)). Winkler proved a theorem giving a necessary and sufficient condition for A↑B. We suggest an alteration to his proof, and give another condition equivalent to A↑B. Daykin defined the pair (A, B) to be universally negatively correlated (A B) if, for all posets R over X, P(R∪A) P(R∪B)≥P(R∪A∪B) P(R∪(A∩B)). He suggested a condition for A↓B. We give a counterexample to that conjecture, and establish the correct condition. We write A↓B if, for all posets R over X, P(R∪A) P(R∪B)≥P(R∪A∪B) P(R). We give a necessary and sufficient condition for A↓B. We also give constructive techniques for listing all pairs (A, B) satisfying each of the relations A↑B, A↓B, and A↓B.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF00334852
Permalink