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_{uv}=\{\sigma \in S_n:\sigma (u)<\sigma (v)\}$. $\text{Theorem.}$ For a fixed $\epsilon >0$, if $\mathbb{P}$ is a probability distribution on $S_n$ such that $\mathbb{P}(A_{uv})>1/2+\epsilon$ for every arc $uv$ of $T$, then the binary entropy of $\mathbb{P}$ is at most $(1-{\vartheta }_{\epsilon }){\log }_{2}n!$ for some (fixed) positive ${\vartheta }_{\epsilon }$. When $T$ is transitive the theorem is due to Leighton and Moitra; for this case we give a short proof with a better ${\vartheta }_{\epsilon }$.

arXiv comment10 pages