Almost Isoperimetric Subsets of the Discrete Cube
Almost Isoperimetric Subsets of the Discrete Cube
复制标题
离散立方体的几乎等周子集
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
David Ellis
中科院分区：
文献类型：
--
作者：
David Ellis
我们证明了一个集合A ∈ {0，1}n，其边边界的大小至多为[|一|（log_{2}（2^{n}/|一|）+）]可以最多（2ε/log 2（1/ε））|一|添加和删除，只要ε小于绝对常数。我们推出，如果A <${0，1}n的大小为2 t，且不能以小于δ的距离成为子立方体，|一|添加和删除，则其边缘边界的大小至少[|一|log_{2}（2^{n}/|一|) + |一|delta log_{2}（1/delta）= 2^{t}（n-t+delta log_{2}（1/delta））]，条件是δ小于绝对常数。当δ = 1/2 j时，对于某个j ∈ {1，2，. . ., t}。
We show that a set A ⊂ {0, 1}n with edge-boundary of size at most [|A| (log_{2}(2^{n}/|A|) + epsilon)] 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| log_{2}(2^{n}/|A|) + |A| delta log_{2}(1/delta) = 2^{t}(n-t+delta log_{2}(1/delta)),] provided δ is less than an absolute constant. This is sharp whenever δ = 1/2j for some j ∈ {1, 2, . . ., t}.