Penn Arts & Sciences Logo

Probability and Combinatorics

Tuesday, March 13, 2012 - 4:30pm

Mokshay Madiman

Yale

Location

University of Pennsylvania

DRL 3C6

We use common entropy-based tools to study general inequalities for sumsets in both discrete settings (in possibly nonabelian groups, motivated by additive combinatorics), and in continuous settings (in finite- dimensional real vector spaces, motivated by convex geometry and geometric functional analysis). In the discrete setting, we introduce the notion of "partition-determined functions" (generalizing group summation), present basic inequalities for the entropy of such functions of independent random variables, as well as cardinality inequalities for compound sets (generalizing sumsets). Corollaries include entropic analogues of general Pl\"unnecke-Ruzsa type inequalities, sumset cardinality inequalities in abelian groups generalizing inequalities of Gyarmati-Matolcsi-Ruzsa and Balister-Bollob\´as, and partial progress towards a conjecture of Ruzsa for sumsets in nonabelian groups. In the continuous setting, we give analogues of some of the above results for differential or continuous entropy, and (time- permitting) mention applications to convex geometry. (The discrete half is based on joint work with A. Marcus and P. Tetali, the continuous half is based on joint works with S. Bobkov and I. Kontoyiannis.)