The diameter of randomly twisted hypercubes

Lucas Aragão, Maurício Collares, Gabriel Dahia, João Pedro Marciano

Research output: Working paperPreprint

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 $$\operatorname{diam}(\mathbf{G}_n) = \big(1 + o(1)\big) \frac{n}{\log_2 n}$$ with high probability.
Original languageEnglish
Publication statusPublished - 2 Jun 2023

Keywords

  • math.CO
  • math.PR

Fingerprint

Dive into the research topics of 'The diameter of randomly twisted hypercubes'. Together they form a unique fingerprint.

Cite this