The diameter of randomly twisted hypercubes
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914969541410816 |
|---|---|
| author | Aragão, Lucas Collares, Maurício Dahia, Gabriel Marciano, João Pedro |
| author_facet | Aragão, Lucas Collares, Maurício Dahia, Gabriel Marciano, João Pedro |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2306_01728 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | The diameter of randomly twisted hypercubes Aragão, Lucas Collares, Maurício Dahia, Gabriel Marciano, João Pedro Combinatorics Probability 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. |
| title | The diameter of randomly twisted hypercubes |
| topic | Combinatorics Probability |
| url | https://arxiv.org/abs/2306.01728 |