while exploiting the extra dimension. In particular, every vertex will climb up its chain half the distance it has from the top, and then, the collision between two vertices is resolved by setting the extra last bit to 1 for the first vertex and to 0 for the second vertex. More precisely, the vertex $c_{n-k}$, which is at the top of its chain, is mapped to $c_{n-k} \circ 1$, while $c_{n-k-1}$ is mapped to $c_{n-k} \circ 0$. The third vertex from the top $c_{n-k-2}$ is mapped to $c_{n-k-1} \circ 1$ while $c_{n-k-3}$ is mapped to $c_{n-k-1} \circ 0$ and so on. The vertex $c_k$ at the bottom of the chain is mapped to $c_{n/2} \circ 1$, which is indeed in ${\mathcal{B}_{n}}$.

Consider now two adjacent vertices $x,y$ in ${\{0,1\}^{n}}$. By the above, these vertices reside in “close” chains with roughly the same length and have roughly the same distance from the top of their respective chains. Thus, in the climbing process, both $x$ and $y$ will be mapped to vertices that have roughly the same distance from the top of their respective chains, and hence, from the discussion above, their images will be $O(1)$-close.

Proof of the Main Theorem {#sec:proof 