Embedding nearly-spanning bounded degree trees
| dc.creator | Alon, Noga | |
| dc.creator | Krivelevich, Michael | |
| dc.creator | Sudakov, Benny | |
| dc.date | 2007-06-27 | |
| dc.date.accessioned | 2026-07-07T08:12:49Z | |
| dc.date.available | 2026-07-07T08:12:49Z | |
| dc.description | We derive a sufficient condition for a sparse graph G on n vertices to contain a copy of a tree T of maximum degree at most d on (1-ε)n vertices, in terms of the expansion properties of G. As a result we show that for fixed d\geq 2 and 0<ε<1, there exists a constant c=c(d,ε) such that a random graph G(n,c/n) contains almost surely a copy of every tree T on (1-ε)n vertices with maximum degree at most d. We also prove that if an (n,D,λ)-graph G (i.e., a D-regular graph on n vertices all of whose eigenvalues, except the first one, are at most λin their absolute values) has large enough spectral gap D/λas a function of d and ε, then G has a copy of every tree T as above. | |
| dc.identifier | https://arxiv.org/abs/0706.4100 | |
| dc.identifier | http://arxiv.org/abs/0706.4100 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/132588 | |
| dc.subject | Combinatorics | |
| dc.title | Embedding nearly-spanning bounded degree trees | |
| dc.type | text |