Edge isoperimetric inequalities for powers of the hypercube

Cyrus Rashtchian¹ ; William Raynaud²

¹University of California, San Diego
²Queen Mary University of London

The electronic journal of combinatorics, Tome 29 (2022) no. 1

Résumé

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 \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}$.

Détail

DOI : 10.37236/9032

Classification : 05C35, 05C70, 05C30, 05D05
Mots-clés : binary ordering, discrete isoperimetric inequalities, Hamming distance, Kleitman-West graph