Almost Isoperimetric Subsets of the Discrete Cube

DOI10.1017/S0963548311000083zbMath1227.05257arXiv1310.8179MaRDI QIDQ2998850

David Ellis

Publication date: 11 May 2011

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Related Items

A limit theorem for continuous selectors ⋮ Around two theorems and a lemma by Lucio Russo ⋮ A stability result for the cube edge isoperimetric inequality ⋮ Stability for vertex isoperimetry in the cube ⋮ An isoperimetric inequality for the Hamming cube and some consequences ⋮ An Inequality for Functions on the Hamming Cube ⋮ On a biased edge isoperimetric inequality for the discrete cube ⋮ Isoperimetry in integer lattices ⋮ On the structure of subsets of the discrete cube with small edge boundary ⋮ Stability versions of Erdős-Ko-Rado type theorems via isoperimetry ⋮ Vertex-isoperimetric stability in the hypercube ⋮ Juntas in theℓ₁-grid and Lipschitz maps between discrete tori ⋮ Concentration on the Boolean hypercube via pathwise stochastic analysis

Cites Work

• Threshold for monotone symmetric properties through a logarithmic Sobolev inequality
• Shadows and intersections: Stability and new proofs
• A note on the edges of the n-cube
• Boolean functions with low average sensitivity depend on few coordinates
• On Russo's approximate zero-one law
• Boolean functions whose Fourier transform is concentrated on the first two levels.
• Thresholds and Expectation Thresholds
• Assignment of Numbers to Vertices
• Edge-Isoperimetric Inequalities and Influences
• Maximally Connected Arrays on the n-Cube
• Optimal Assignments of Numbers to Vertices