Finding long cycles in a percolated expander graphs
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866908423204896768 |
|---|---|
| author | Hollom, Lawrence |
| author_facet | Hollom, Lawrence |
| contents | Given a graph $G$, the percolated graph $G_p$ has each edge independently retained with probability $p$. Collares, Diskin, Erde, and Krivelevich initiated the study of large structures in percolated single-scale vertex expander graphs, wherein every set of exactly $k$ vertices of $G$ has at least $dk$ neighbours before percolation. We extend their result to a conjectured stronger form, proving that if $p = (1+\varepsilon)/d$ and $G$ is a graph on at least $k$ vertices which expands as above, then $G_p$ contains a cycle of length $Ω_\varepsilon(kd)$ with probability at least $1-\exp(-Ω_\varepsilon(k/d))$ as $k\rightarrow\infty$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_12162 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Finding long cycles in a percolated expander graphs Hollom, Lawrence Combinatorics Probability Given a graph $G$, the percolated graph $G_p$ has each edge independently retained with probability $p$. Collares, Diskin, Erde, and Krivelevich initiated the study of large structures in percolated single-scale vertex expander graphs, wherein every set of exactly $k$ vertices of $G$ has at least $dk$ neighbours before percolation. We extend their result to a conjectured stronger form, proving that if $p = (1+\varepsilon)/d$ and $G$ is a graph on at least $k$ vertices which expands as above, then $G_p$ contains a cycle of length $Ω_\varepsilon(kd)$ with probability at least $1-\exp(-Ω_\varepsilon(k/d))$ as $k\rightarrow\infty$. |
| title | Finding long cycles in a percolated expander graphs |
| topic | Combinatorics Probability |
| url | https://arxiv.org/abs/2506.12162 |