Embedding multidimensional grids into optimal hypercubes

Let $G$ and $H$ be graphs, with $\mathrm{\mid }V(H)\mathrm{\mid }\ge \mathrm{\mid }V(G)\mathrm{\mid }$, and $f:V(G)\rightarrow V(H)$aonetoonemapoftheirvertices\mathrm{.}Let$dilation(f) = max{ dist_{H}(f(x),f(y)): xy\in E(G) }$,where$dist_{H}(v,w)$ is the distance between vertices $v$ and $w$ of $H$. Now let $B(G,H)$ = $min_{f}{ dilation(f) }$,overallsuchmaps$f$. The parameter $B(G,H)$ is a generalization of the classic and well studied “bandwidth” of $G$, defined as $B(G,P(n))$, where $P(n)$ is the path on $n$ points and $n=\mathrm{\mid }V(G)\mathrm{\mid }$. Let $[a_1\times a_2\times \cdots \times a_k]$ be the $k$-dimensional grid graph with integer values $1$ through $a_i$ in the $i$’th coordinate. In this paper, we study $B(G,H)$ in the case when $G = [a_{1}\times a_{2}\times \cdots \times a_{k} ]$and$H$isthehypercube$Q_{n}$ofdimension$n = \lceil log_{2}(|V(G)|) \rceil$, the hypercube of smallest dimension having at least as many points as $G$. Our main result is that $$B([a_1\times a_2\times \cdots \times a_k],Q_n)\le 3k,$$ provided $a_i\ge 2^{22}$ for each $1\le i\le k$. For such $G$, the bound $3k$ improves on the previous best upper bound $4k+O(1)$. Our methods include an application of Knuth’s result on two-way rounding and of the existence of spanning regular cyclic caterpillars in the hypercube.