The Match Set of a Random Permutation Has the FKG Property

We prove a conjecture of Joag-Dev and Goel that if M = M(σ) = {i: σ(i) = i} is the (random) match set, or set of fixed points, of a random permutation σ of 1,2,…,n, then f(M) and g(M) are positively correlated whenever f and g are increasing real-valued set functions on 2{1,…,n}, i.e., Ef(M) g(M) ≥ Ef(M) Eg(M). No simple use of the FKG or Ahlswede-Daykin inequality seems to establish this, despite the fact that the FKG hypothesis is "almost" satisfied. Instead we reduce to the case where f and g take values in {0,1}, and make a case-by-case argument: Depending on the specific form of f and g, we move the probability weights around so as to make them satisfy the FKG or Ahlswede-Daykin hypotheses, without disturbing the expectations Ef, Eg, Efg. This approach extends the methodology by which FKG-style correlation inequalities can be proved.