An isoperimetric inequality for antipodal subsets of the discrete cube. (May 2018)

• Record Type: Journal Article
• Authors: Ellis, David; Leader, Imre
• Is Part Of: European journal of combinatorics. Volume 70(2018)
• Page Start: 149
• Page End: 154
• Publication Date: 2018-05
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2017.12.003
• Languages: English
• ISSNs: 0195-6698

Abstract

Abstract: We say a family of subsets of { 1, 2, …, n } is antipodal if it is closed under taking complements. We prove a best-possible isoperimetric inequality for antipodal families of subsets of { 1, 2, …, n } (of any size). Our inequality implies that for any k ∈ N, among all such families of size 2 k, a family consisting of the union of two antipodal ( k − 1 ) -dimensional subcubes has the smallest possible edge boundary.