An approximate vertex-isoperimetric inequality for r-sets

zbMATH Open1300.05308arXiv1203.3699MaRDI QIDQ396930FDOQ396930

Authors: Demetres Christofides, David Ellis, Peter Keevash 

Publication date: 14 August 2014

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

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

Full work available at URL: https://arxiv.org/abs/1203.3699

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

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

zbMATH Keywords

discrete isoperimetric inequalities

Mathematics Subject Classification ID

Extremal set theory (05D05)

Cites Work

• A note on the edges of the n-cube
• Maximally Connected Arrays on the n-Cube
• Optimal Assignments of Numbers to Vertices
• Concentration of measure and isoperimetric inequalities in product spaces
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Optimal numberings and isoperimetric problems on graphs
• An isoperimetric inequality on the discrete cube and an elementary proof of the isoperimetric inequality in Gauss space
• Assignment of Numbers to Vertices
• On a problem of Kleitman and West
• Isoperimetry, logarithmic Sobolev inequalities on the discrete cube, and Margulis' graph connectivity theorem
• Title not available (Why is that?)
• A Counterexample to Kleitman's Conjecture Concerning an Edge-Isoperimetric Problem

Cited In (12)

• Homomorphisms from the torus
• On theorems of Wirsing and Sanders
• Title not available (Why is that?)
• 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
• Extremal families for Kruskal-Katona theorem
• A local-global principle for vertex-isoperimetric problems
• Negative-type diversities, a multi-dimensional analogue of negative-type metrics
• Percolation on irregular high-dimensional product graphs
• Title not available (Why is that?)
• 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)