An approximate vertex-isoperimetric inequality for \(r\)-sets (Q396930)

From MaRDI portal
scientific article
Language Label Description Also known as
English
An approximate vertex-isoperimetric inequality for \(r\)-sets
scientific article

    Statements

    An approximate vertex-isoperimetric inequality for \(r\)-sets (English)
    0 references
    0 references
    0 references
    0 references
    14 August 2014
    0 references
    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\)).
    0 references
    discrete isoperimetric inequalities
    0 references

    Identifiers