{
"id": "1803.04958",
"version": "v1",
"published": "2018-03-13T17:54:30.000Z",
"updated": "2018-03-13T17:54:30.000Z",
"title": "Spanning trees in randomly perturbed graphs",
"authors": [
"Felix Joos",
"Jaehoon Kim"
],
"comment": "41 pages",
"categories": [
"math.CO"
],
"abstract": "A classical result of Koml\\'os, S\\'ark\\\"ozy and Szemer\\'edi states that every $n$-vertex graph with minimum degree at least $(1/2+ o(1))n$ contains every $n$-vertex tree with maximum degree $O(n/\\log{n})$ as a subgraph, and the bounds on the degree conditions are sharp. On the other hand, Krivelevich, Kwan and Sudakov recently proved that for every $n$-vertex graph $G_\\alpha$ with minimum degree at least $\\alpha n$ for any fixed $\\alpha >0$ and every $n$-vertex tree $T$ with bounded maximum degree, one can still find a copy of $T$ in $G_\\alpha$ with high probability after adding $O(n)$ randomly-chosen edges to $G_\\alpha$. We extend their results to trees with unbounded maximum degree. More precisely, for a given $n^{o(1)}\\leq \\Delta\\leq cn/\\log n$ and $\\alpha>0$, we determine the precise number (up to a constant factor) of random edges that we need to add to an arbitrary $n$-vertex graph $G_\\alpha$ with minimum degree $\\alpha n$ in order to guarantee a copy of any fixed $n$-vertex tree $T$ with maximum degree at most~$\\Delta$ with high probability.",
"revisions": [
{
"version": "v1",
"updated": "2018-03-13T17:54:30.000Z"
}
],
"analyses": {
"keywords": [
"randomly perturbed graphs",
"spanning trees",
"minimum degree",
"vertex tree",
"vertex graph"
],
"note": {
"typesetting": "TeX",
"pages": 41,
"language": "en",
"license": "arXiv",
"status": "editable"
}
}
}