Edge Isoperimetric Inequalities for Powers of the Hypercube

Abstract

For positive integers $n$ and $r$, we let $Q_n^r$ denote the $r$th power of the $n$-dimensional discrete hypercube graph, i.e., the graph with vertex-set $\{0,1{\}}^n$, where two 0-1 vectors are joined if they are Hamming distance at most $r$ apart. We study edge isoperimetric inequalities for this graph. Harper, Bernstein, Lindsey and Hart proved a best-possible edge isoperimetric inequality for this graph in the case $r=1$. For each $r\ge 2$, we obtain an edge isoperimetric inequality for $Q_n^r$; our inequality is tight up to a constant factor depending only upon $r$. Our techniques also yield an edge isoperimetric inequality for the `Kleitman-West graph' (the graph whose vertices are all the $k$-element subsets of $\{1,2,\dots ,n\}$, where two $k$-element sets have an edge between them if they have symmetric difference of size two); this inequality is sharp up to a factor of $2+o(1)$ for sets of size $\left(\genfrac{}{}{0ex}{}{n-s}{k-s}\right)$, where $k=o(n)$ and $s\in \mathbb{N}$.

arXiv comment29 pages, Electronic Journal of Combinatorics