On Mappings on the Hypercube with Small Average Stretch

Lucas Boczkowski, Igor Shinkar

Let $A\subseteq \{0,1{\}}^n$ be a set of size $2^{n-1}$, and let $\varphi :\{0,1{\}}^{n-1}\to A$ be a bijection. We define the average stretch of $\varphi$ as ${\sf avgStretch}(ϕ) = {\mathb…