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