Cycle lengths in the percolated hypercube
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911015340343296 |
|---|---|
| author | Anastos, Michael Diskin, Sahar Erde, Joshua Kang, Mihyun Krivelevich, Michael Lichev, Lyuben |
| author_facet | Anastos, Michael Diskin, Sahar Erde, Joshua Kang, Mihyun Krivelevich, Michael Lichev, Lyuben |
| contents | Let $Q^d_p$ be the random subgraph of the $d$-dimensional binary hypercube obtained after edge-percolation with probability $p$. It was shown recently by the authors that, for every $\varepsilon > 0$, there is some $c = c(\varepsilon)>0$ such that, if $pd\ge c$, then typically $Q^d_p$ contains a cycle of length at least $(1-\varepsilon)2^d$. We strengthen this result to show that, under the same assumptions, typically $Q^d_p$ contains cycles of all even lengths between $4$ and $(1-\varepsilon)2^d$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_16858 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Cycle lengths in the percolated hypercube Anastos, Michael Diskin, Sahar Erde, Joshua Kang, Mihyun Krivelevich, Michael Lichev, Lyuben Combinatorics Probability Let $Q^d_p$ be the random subgraph of the $d$-dimensional binary hypercube obtained after edge-percolation with probability $p$. It was shown recently by the authors that, for every $\varepsilon > 0$, there is some $c = c(\varepsilon)>0$ such that, if $pd\ge c$, then typically $Q^d_p$ contains a cycle of length at least $(1-\varepsilon)2^d$. We strengthen this result to show that, under the same assumptions, typically $Q^d_p$ contains cycles of all even lengths between $4$ and $(1-\varepsilon)2^d$. |
| title | Cycle lengths in the percolated hypercube |
| topic | Combinatorics Probability |
| url | https://arxiv.org/abs/2506.16858 |