printable pdf
比利时vs摩洛哥足彩 ,
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

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