Proof of an entropy conjecture of Leighton and Moitra

2017/01/16 by Acan, Hüseyin, Devlin, Pat, Kahn, Jeff · 1 citation
#05C20 (Primary) #05D40 #06A07 (Secondary) #94A17 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1701.04321

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=\σ∈ S_n : σ(u)0, if ℙ is a probability distribution on S_n such that ℙ(A_uv)>1/2+ε for every arc uv of T, then the binary entropy of ℙ is at most (1-ϑ_ε)log₂ n! for some (fixed) positive ϑ_ε. When T is transitive the theorem is due to Leighton and Moitra; for this case we give a short proof with a better ϑ_ε.

Cited by

• Balancing Extensions in Posets of Large Width

Related

• Annealed almost periodic entropy
• Limit of the Maximum Random Permutation Set Entropy
• On the Shannon entropy of the number of vertices with zero in-degree in randomly oriented hypergraphs
• Entropy methods in combinatorics
• Exploring the entropic region