The diameter of randomly twisted hypercubes

Abstract

The $n$-dimensional random twisted hypercube ${\mathbf{G}}_n$ is constructed recursively by taking two instances of ${\mathbf{G}}_{n-1}$, with any joint distribution, and adding a random perfect matching between their vertex sets. Benjamini, Dikstein, Gross, and Zhukovskii showed that its diameter is $O(n\log \log \log n/\log \log n)$ with high probability and at least $(n-1)/{\log }_{2}n$. We improve their upper bound by showing that $$\mathrm{diam}({\mathbf{G}}_n)=(1+o(1))\frac{n}{{\log }_{2}n}$$ with high probability.

6 pages, minor changes to address helpful referee comments, content matches version appearing in European Journal of Combinatorics