Nearly optimal embeddings of trees
| dc.creator | Sudakov, Benny | |
| dc.creator | Vondrak, Jan | |
| dc.date | 2007-07-13 | |
| dc.date.accessioned | 2026-07-07T08:18:22Z | |
| dc.date.available | 2026-07-07T08:18:22Z | |
| dc.description | In this paper we show how to find nearly optimal embeddings of large trees in several natural classes of graphs. The size of the tree T can be as large as a constant fraction of the size of the graph G, and the maximum degree of T can be close to the minimum degree of G. For example, we prove that any graph of minimum degree d without 4-cycles contains every tree of size εd^2 and maximum degree at most (1-2ε)d - 2. As there exist d-regular graphs without 4-cycles of size O(d^2), this result is optimal up to constant factors. We prove similar nearly tight results for graphs of given girth, graphs with no complete bipartite subgraph K_{s,t}, random and certain pseudorandom graphs. These results are obtained using a simple and very natural randomized embedding algorithm, which can be viewed as a "self-avoiding tree-indexed random walk". | |
| dc.identifier | https://arxiv.org/abs/0707.2079 | |
| dc.identifier | http://arxiv.org/abs/0707.2079 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/134407 | |
| dc.subject | Combinatorics | |
| dc.subject | Probability | |
| dc.subject | 05D40 | |
| dc.title | Nearly optimal embeddings of trees | |
| dc.type | text |