The diameter of randomly twisted hypercubes
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.
Authors
- João Pedro Marciano (ORCID: https://orcid.org/0009-0000-5539-9061)
- Lucas Wagner Ribeiro Aragão (ORCID: https://orcid.org/0009-0004-7292-463X)
- Maurício Collares (ORCID: https://orcid.org/0000-0001-5856-611X)
- Gabriel Dahia
Institutions
- Instituto Nacional de Matemática Pura e Aplicada (BR)
- Universidade do Estado do Rio de Janeiro (BR)
- Graz University of Technology (AT)
- Instituto de Pesquisas Jardim Botânico do Rio de Janeiro (BR)
Publication Details
- Journal
- European Journal of Combinatorics
- Published
- 2024-10-10
- DOI
- https://doi.org/10.1016/j.ejc.2024.104078
- Primary Topic
- Interconnection Networks and Systems
- Type
- article
- Field-Weighted Citation Impact
- 0.00
Funders
- Coordenação de Aperfeiçoamento de Pessoal de Nível Superior
- Austrian Science Fund
- Conselho Nacional de Desenvolvimento Científico e Tecnológico