An approximate vertex-isoperimetric inequality for r-sets

Authors Demetres Christofides, David Ellis, Peter Keevash

Publication date 14 August 2014

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1203.3699, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v20i4p15

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

discrete isoperimetric inequalities

Mathematics Subject Classification ID

Extremal set theory (05D05)

Abstract: We prove a vertex-isoperimetric inequality for [n]^(r), the set of all r-element subsets of {1,2,...,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 the vertex-boundary b(mathcal{A}) satisfies |b(mathcal{A})| geq csqrt{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).

Review text

Summary: 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\)).

Recommendations

Cites work

Cited in

(12)

This page was built for publication: An approximate vertex-isoperimetric inequality for \(r\)-sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q396930)