On the structure of subsets of the discrete cube with small edge boundary
Discrete analysis (2018)
Voir la notice de l'article provenant de la source Scholastica
arXiv
The edge isoperimetric inequality in the discrete cube specifies, for each pair of integers $m$ and $n$, the minimum size $g_n(m)$ of the edge boundary of an $m$-element subset of $\{0,1\}^{n}$; the extremal families (up to automorphisms of the discrete cube) are initial segments of the lexicographic ordering on $\{0,1\}^n$. We show that for any $m$-element subset $\mathcal{F} \subset \{0,1\}^n$ and any integer $l$, if the edge boundary of $\mathcal{F}$ has size at most $g_n(m)+l$, then there exists an extremal family $\mathcal{G} \subset \{0,1\}^n$ such that $|\mathcal{F} Δ\mathcal{G}| \leq Cl$, where $C$ is an absolute constant. This is best-possible, up to the value of $C$. Our result can be seen as a `stability' version of the edge isoperimetric inequality in the discrete cube, and as a discrete analogue of the seminal stability result of Fusco, Maggi and Pratelli concerning the isoperimetric inequality in Euclidean space.
David Ellis; Nathan Keller; Noam Lifshitz. On the structure of subsets of the discrete cube with small edge boundary. Discrete analysis (2018). http://geodesic.mathdoc.fr/item/DAS_2018_a12/
@article{DAS_2018_a12,
author = {David Ellis and Nathan Keller and Noam Lifshitz},
title = {On the structure of subsets of the discrete cube with small edge boundary},
journal = {Discrete analysis},
year = {2018},
language = {en},
url = {http://geodesic.mathdoc.fr/item/DAS_2018_a12/}
}