2013/10/31 by David Ellis · 1 citation
Mathematics · #math.CO #msc:05D05
published as Combinatorics, Probability and Computing 20 (2011), 363-380 · Typos corrected in Conjectures 12 and 13
arxiv created 2013/11/27 · arxiv updated 2013/11/28
We show that a set A ⊂ \0,1\n with edge-boundary of size at most |A| (log2(2n/|A|) + ε) can be made into a subcube by at most (2 ε/log2(1/ε))|A| additions and deletions, provided ε is less than an absolute constant. We deduce that if A ⊂ \0,1\n has size 2t for some t ∈ ℕ, and cannot be made into a subcube by fewer than δ|A| additions and deletions, then its edge-boundary has size at least |A| log2(2n/|A|) + |A| δlog2(1/δ) = 2t(n-t+δlog2(1/δ)), provided δ is less than an absolute constant. This is sharp whenever δ= 1/2j for some j ∈ \1,2,…,t\.