Proof of an entropy conjecture of Leighton and Moitra

Abstract We prove the following conjecture of Leighton and Moitra. Let T be a tournament on [ n ] and S n the set of permutations of [ n ] . For an arc uv of T , let A u v = { σ ∈ S n : σ ( u ) σ ( v ) } . Theorem For a fixed e > 0 , if P is a probability distribution on S n such that P ( A u v ) > 1 / 2 + e for every arc uv of T, then the binary entropy of P is at most ( 1 − ϑ e ) log 2 ⁡ n ! for some (fixed) positive ϑ e . When T is transitive the theorem is due to Leighton and Moitra; for this case we give a short proof with a better ϑ e .