Penn Arts & Sciences Logo

Probability and Combinatorics

Tuesday, April 11, 2017 - 3:00pm

Patrick Devlin



University of Pennsylvania

DRL 4N30

Suppose F is a random (not necessarily uniform) permutation of {1, 2, ... , n} such that |Prob(F(i) < F(j)) -1/2| > epsilon for all i,j. We show that under this assumption, the entropy of F is at most (1-delta)log(n!), for some fixed delta depending only on epsilon [proving a conjecture of Leighton and Moitra]. In other words, if (for every distinct i,j) our random permutation either noticeably prefers F(i) < F(j) or prefers F(i) > F(j), then the distribution inherently carries significantly less uncertainty (or information) than the uniform distribution. Our proof relies on a version of the regularity lemma, a combinatorial bookkeeping gadget, and a few basic probabilistic ideas. The talk should be accessible for any background, and we will gently recall any relevant notions (e.g., entropy) as needed. Those unhappy with the talk are welcome to form an unruly mob to depose the speaker, and pitchforks and torches will be available for purchase. This is from a recent paper joint with Huseyin Acan and Jeff Kahn.