The diameter of randomly twisted hypercubes

MaRDI QIDQ6439048zbMATH OpenFDO

Authors Maurício Collares, Gabriel Dahia

Publication date 2 June 2023

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(nlogloglogn/loglogn)$ with high probability and at least $(n-1)/lo{g}_{2}n$. We improve their upper bound by showing that ${\displaystyle }$operatorname{diam}(mathbf{G}_n) = �ig(1 + o(1)�ig) frac{n}{log_2 n}${\displaystyle }$ with high probability.

This page was built for publication: The diameter of randomly twisted hypercubes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6439048)