Noga Alon
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Research Interests
Noga Alon has a total of 2 co-authors. Here are the top co-authors by number of shared publications:
- Benny Sudakov
ETH Zurich, Switzerland
1 shared publication - Michael Krivelevich
Tel Aviv University
1 shared publication
Latest Publications
- Open Access
Embedding nearly-spanning bounded degree trees
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-\epsilon)n vertices, in terms of the expansion properties of G. As a result we show that for fixed d\geq 2 and 0<\epsilon<1, there exists a constant c=c(d,\epsilon) such that a random graph G(n,c/n) contains almost surely a copy of every tree T on (1-\epsilon)n vertices with maximum degree at most d. We also prove that if an (n,D,\lambda)-graph G (i.e., a D-regular graph on n vertices all of whose eigenvalues, except the first one, are at most \lambda in their absolute values) has large enough spectral gap D/\lambda as a function of d and \epsilon, then G has a copy of every tree T as above.
Open AccessEmbedding nearly-spanning bounded degree trees
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-\epsilon)n vertices, in terms of the expansion properties of G. As a result we show that for fixed d\geq 2 and 0<\epsilon<1, there exists a constant c=c(d,\epsilon) such that a random graph G(n,c/n) contains almost surely a copy of every tree T on (1-\epsilon)n vertices with maximum degree at most d. We also prove that if an (n,D,\lambda)-graph G (i.e., a D-regular graph on n vertices all of whose eigenvalues, except the first one, are at most \lambda in their absolute values) has large enough spectral gap D/\lambda as a function of d and \epsilon, then G has a copy of every tree T as above.