##### Department of Mathematics,

University of California San Diego

****************************

### Math 269 - Combinatorics

## Jozsef Balogh

#### UCSD

## Almost spanning trees in Sparse Graph

##### Abstract:

We prove that sparse (pseudo-) random graphs contain every almost spanning bounded degree trees. We actually prove a stronger result, a local resilience type one, that the above statement holds even if from each vertex of a sparse pseudo-random graph half of the edges is removed. The proof uses Szemeredi's Regularity Lemma for sparse graphs, and modifies a theorem of Friedman and Peppenger. It is joint work with B. Csaba, M. Pei and W. Samotij.

### April 13, 2010

### 4:00 PM

### AP&M 7321

****************************