An approximate vertex-isoperimetric inequality for r-sets

MaRDI QIDQ396930zbMATH OpenFDO

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).

Recommendations

• Vertex isoperimetric inequalities for a family of graphs on \(\mathbb{Z}^k\)
• Publication:4888931
• Almost isoperimetric subsets of the discrete cube
• scientific article; zbMATH DE number 2103158
• An isoperimetric inequality for the Hamming cube and some consequences

Cites work

• scientific article; zbMATH DE number 3957109 (Why is no real title available?)
• scientific article; zbMATH DE number 18980 (Why is no real title available?)
• scientific article; zbMATH DE number 3632542 (Why is no real title available?)
• scientific article; zbMATH DE number 736286 (Why is no real title available?)
• scientific article; zbMATH DE number 2103158 (Why is no real title available?)
• A Counterexample to Kleitman's Conjecture Concerning an Edge-Isoperimetric Problem
• A note on the edges of the n-cube
• An isoperimetric inequality on the discrete cube and an elementary proof of the isoperimetric inequality in Gauss space
• Assignment of Numbers to Vertices
• Concentration of measure and isoperimetric inequalities in product spaces
• Isoperimetry, logarithmic Sobolev inequalities on the discrete cube, and Margulis' graph connectivity theorem
• Maximally Connected Arrays on the n-Cube
• On a problem of Kleitman and West
• Optimal Assignments of Numbers to Vertices
• Optimal numberings and isoperimetric problems on graphs

Cited in

(12)

• Homomorphisms from the torus
• On theorems of Wirsing and Sanders
• scientific article; zbMATH DE number 2103158 (Why is no real title available?)
• Vertex isoperimetry and independent set stability for tensor powers of cliques
• Vertex isoperimetric inequalities for a family of graphs on \(\mathbb{Z}^k\)
• Isoperimetry, stability, and irredundance in direct products
• A local-global principle for vertex-isoperimetric problems
• Extremal families for Kruskal-Katona theorem
• Negative-type diversities, a multi-dimensional analogue of negative-type metrics
• Percolation on irregular high-dimensional product graphs
• scientific article; zbMATH DE number 919266 (Why is no real title available?)
• An isoperimetric inequality for Hamming balls and local expansion in hypercubes

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)