Edge isoperimetric inequalities for powers of the hypercube (Q2121790)

Summary: 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. \textit{L. H. Harper} [J. Soc. Ind. Appl. Math. 12, 131--135 (1964; Zbl 0222.94004)], \textit{A. J. Bernstein} [SIAM J. Appl. Math. 15, 1485--1489 (1967; Zbl 0157.26004)], \textit{J. H. Lindsay II} [Am. Math. Mon. 71, 508--516 (1964; Zbl 0279.05019)] and \textit{S. Hart} [Discrete Math. 14, 157--163 (1976; Zbl 0363.05058)] proved a best-possible edge isoperimetric inequality for this graph in the case \(r=1\). For each \(r \geq 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,\ldots,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 \(\binom{n-s}{k-s} \), where \(k=o(n)\) and \(s \in \mathbb{N}\).