Geodesic
An approximate vertex-isoperimetric inequality for \(r\)-sets
Demetres Christofides1 ; David Ellis1 ; Peter Keevash1
1Queen Mary, University of London
The electronic journal of combinatorics, Tome 20 (2013) no. 4
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

We prove a vertex-isoperimetric inequality for \([n]^{(r)}\), the set of all \(r\)-element subsets of \(\{1,2,\ldots,n\}\), where \(x,y \in [n]^{(r)}\) are adjacent if \(|x \Delta y|=2\). Namely, if \(\mathcal{A} \subset [n]^{(r)}\) with \(|\mathcal{A}|=\alpha {n \choose r}\), then its vertex-boundary \(b(\mathcal{A})\) satisfies\[|b(\mathcal{A})| \geq c\sqrt{\frac{n}{r(n-r)}} \alpha(1-\alpha) {n \choose r},\]where \(c\) is a positive absolute constant. For \(\alpha\) bounded away from 0 and 1, this is sharp up to a constant factor (independent of \(n\) and \(r\)).
DOI : 10.37236/2458
Classification : 05D05
Mots-clés : discrete isoperimetric inequalities

Demetres Christofides  1   ; David Ellis  1   ; Peter Keevash  1

1 Queen Mary, University of London 
@article{10_37236_2458,
     author = {Demetres Christofides and David Ellis and Peter Keevash},
     title = {An approximate vertex-isoperimetric inequality for \(r\)-sets},
     journal = {The electronic journal of combinatorics},
     year = {2013},
     volume = {20},
     number = {4},
     doi = {10.37236/2458},
     zbl = {1300.05308},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/2458/}
}
TY  - JOUR
AU  - Demetres Christofides
AU  - David Ellis
AU  - Peter Keevash
TI  - An approximate vertex-isoperimetric inequality for \(r\)-sets
JO  - The electronic journal of combinatorics
PY  - 2013
VL  - 20
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.37236/2458/
DO  - 10.37236/2458
ID  - 10_37236_2458
ER  - 
%0 Journal Article
%A Demetres Christofides
%A David Ellis
%A Peter Keevash
%T An approximate vertex-isoperimetric inequality for \(r\)-sets
%J The electronic journal of combinatorics
%D 2013
%V 20
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/2458/
%R 10.37236/2458
%F 10_37236_2458
Demetres Christofides; David Ellis; Peter Keevash. An approximate vertex-isoperimetric inequality for \(r\)-sets. The electronic journal of combinatorics, Tome 20 (2013) no. 4. doi: 10.37236/2458

Cité par Sources :