The diameter of randomly twisted hypercubes

The n-dimensional random twisted hypercube Gn is constructed recursively by taking two instances of Gn−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 hi...

Full description

Saved in:
Bibliographic Details
Published in:European journal of combinatorics 2025-02, Vol.124, p.104078, Article 104078
Main Authors: Aragão, Lucas, Collares, Maurício, Dahia, Gabriel, Marciano, João Pedro
Format: Article
Language:English
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The n-dimensional random twisted hypercube Gn is constructed recursively by taking two instances of Gn−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)/log2n. We improve their upper bound by showing that diam(Gn)=(1+o(1))nlog2n with high probability.
ISSN:0195-6698
DOI:10.1016/j.ejc.2024.104078