Almost Isoperimetric Subsets of the Discrete Cube

作者：Ellis David^*

来源：Combinatorics Probability & Computing, 2011, 20(3): 363-380.

DOI：10.1017/S0963548311000083

We show that a set A subset of {0, 1}(n) with edge-boundary of size at most
vertical bar A vertical bar(log(2)(2(n)/vertical bar A vertical bar) + epsilon)
can be made into a subcube by at most (2 epsilon/log(2)(1/epsilon))vertical bar A vertical bar additions and deletions, provided epsilon is less than an absolute constant.
We deduce that if A subset of {0, 1}(n) has size 2(t) for some t is an element of N, and cannot be made into a subcube by fewer than delta vertical bar A vertical bar additions and deletions, then its edge-boundary has size at least
vertical bar A vertical bar log(2)(2(n)/vertical bar A vertical bar) + vertical bar A vertical bar delta log(2)(1/delta) = 2(t)(n - t + delta log(2)(1/delta)),
provided delta is less than an absolute constant. This is sharp whenever delta = 1/2(j) for some j is an element of {1, 2, ... , t}.

• 出版日期2011-5