Proof of an entropy conjecture of Leighton and Moitra

摘要

We prove the following conjecture of Leighton and Moitra. Let T be a tournament on [n] and (sic)(n) the set of permutations of [n]. For an arc uv of T, let A(uv) = {sigma is an element of(sic)(n) : sigma(u) sigma(v)}.