Large matchings and nearly spanning, nearly regular subgraphs of random subgraphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916333564723200 |
|---|---|
| author | Diskin, Sahar Erde, Joshua Kang, Mihyun Krivelevich, Michael |
| author_facet | Diskin, Sahar Erde, Joshua Kang, Mihyun Krivelevich, Michael |
| contents | Given a graph $G$ and $p\in [0,1]$, the random subgraph $G_p$ is obtained by retaining each edge of $G$ independently with probability $p$. We show that for every $ε>0$, there exists a constant $C>0$ such that the following holds. Let $d\ge C$ be an integer, let $G$ be a $d$-regular graph and let $p\ge \frac{C}{d}$. Then, with probability tending to one as $|V(G)|$ tends to infinity, there exists a matching in $G_p$ covering at least $(1-ε)|V(G)|$ vertices.
We further show that for a wide family of $d$-regular graphs $G$, which includes the $d$-dimensional hypercube, for any $p\ge \frac{\log^5d}{d}$ with probability tending to one as $d$ tends to infinity, $G_p$ contains an induced subgraph on at least $(1-o(1))|V(G)|$ vertices, whose degrees are tightly concentrated around the expected average degree $dp$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_16458 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Large matchings and nearly spanning, nearly regular subgraphs of random subgraphs Diskin, Sahar Erde, Joshua Kang, Mihyun Krivelevich, Michael Combinatorics Probability Given a graph $G$ and $p\in [0,1]$, the random subgraph $G_p$ is obtained by retaining each edge of $G$ independently with probability $p$. We show that for every $ε>0$, there exists a constant $C>0$ such that the following holds. Let $d\ge C$ be an integer, let $G$ be a $d$-regular graph and let $p\ge \frac{C}{d}$. Then, with probability tending to one as $|V(G)|$ tends to infinity, there exists a matching in $G_p$ covering at least $(1-ε)|V(G)|$ vertices. We further show that for a wide family of $d$-regular graphs $G$, which includes the $d$-dimensional hypercube, for any $p\ge \frac{\log^5d}{d}$ with probability tending to one as $d$ tends to infinity, $G_p$ contains an induced subgraph on at least $(1-o(1))|V(G)|$ vertices, whose degrees are tightly concentrated around the expected average degree $dp$. |
| title | Large matchings and nearly spanning, nearly regular subgraphs of random subgraphs |
| topic | Combinatorics Probability |
| url | https://arxiv.org/abs/2407.16458 |