An isoperimetric inequality for antipodal subsets of the discrete cube

2016/09/14 by David Ellis, Ellis, David, Imre Leader +1
Mathematics · #05D05 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05D05

paper · pdf · doi:10.48550/arxiv.1609.04270

A new proof of Lemma 6 (kindly suggested by an anonymous referee) has been given; this shortens our original argument. An acknowledgement and a conclusion have been added, and minor changes have been made to improve readability

arxiv created 2017/11/11 · arxiv updated 2017/11/15

Abstract

A family of subsets of \1,2,…,n\ is said to be \em antipodal if it is closed under taking complements. We prove a best-possible isoperimetric inequality for antipodal families of subsets of \1,2,…,n\. Our inequality implies that for any k ∈ ℕ, among all such families of size 2^k, a family consisting of the union of a (k-1)-dimensional subcube and its antipode has the smallest possible edge boundary.

Related

• On the structure of subsets of the discrete cube with small edge\n boundary
• A stability result for the cube edge isoperimetric inequality
• A cubical antipodal theorem
• Almost isoperimetric subsets of the discrete cube
• The isoperimetric inequality for a minimal submanifold in Euclidean space