The diameter of randomly twisted hypercubes
Lucas Wagner Ribeiro Aragão, Maurício Collares, Gabriel Dahia, João Pedro Marciano · European Journal of Combinatorics · 2024
The n -dimensional random twisted hypercube G n is constructed recursively by taking two instances of 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 diam ( G n ) = ( 1 + o ( 1 ) ) n log 2 n with high probability.