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