Bounded-degree spanning trees in randomly perturbed graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2015
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913865394028544 |
|---|---|
| author | Krivelevich, Michael Kwan, Matthew Sudakov, Benny |
| author_facet | Krivelevich, Michael Kwan, Matthew Sudakov, Benny |
| contents | We show that for any fixed dense graph G and bounded-degree tree T on the same number of vertices, a modest random perturbation of G will typically contain a copy of T . This combines the viewpoints of the well-studied problems of embedding trees into fixed dense graphs and into random graphs, and extends a sizeable body of existing research on randomly perturbed graphs. Specifically, we show that there is $c = c(α,Δ)$ such that if G is an n-vertex graph with minimum degree at least $αn$, and T is an n-vertex tree with maximum degree at most $Δ$ , then if we add cn uniformly random edges to G, the resulting graph will contain T asymptotically almost surely (as $n\to\infty$ ). Our proof uses a lemma concerning the decomposition of a dense graph into super-regular pairs of comparable sizes, which may be of independent interest. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1507_07960 |
| institution | arXiv |
| publishDate | 2015 |
| record_format | arxiv |
| spellingShingle | Bounded-degree spanning trees in randomly perturbed graphs Krivelevich, Michael Kwan, Matthew Sudakov, Benny Combinatorics We show that for any fixed dense graph G and bounded-degree tree T on the same number of vertices, a modest random perturbation of G will typically contain a copy of T . This combines the viewpoints of the well-studied problems of embedding trees into fixed dense graphs and into random graphs, and extends a sizeable body of existing research on randomly perturbed graphs. Specifically, we show that there is $c = c(α,Δ)$ such that if G is an n-vertex graph with minimum degree at least $αn$, and T is an n-vertex tree with maximum degree at most $Δ$ , then if we add cn uniformly random edges to G, the resulting graph will contain T asymptotically almost surely (as $n\to\infty$ ). Our proof uses a lemma concerning the decomposition of a dense graph into super-regular pairs of comparable sizes, which may be of independent interest. |
| title | Bounded-degree spanning trees in randomly perturbed graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/1507.07960 |