Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, December 01, 2015, 12:15 pm
Duration: 30 minutes
Location: CAB G51
Speaker: Rajko Nenadov
The celebrated result of Friedman and Pippenger gives a sufficient expansion condition for the containment of all small trees (i.e. 1-degenerate graphs). It was further generalised by Haxell to larger trees and both results were subsequently utilised in proofs of universality of random graphs with respect to the family of almost-spanning bounded-degree trees. We take a step towards generalising these results to d-degenerate graphs. In particular, we show that certain expansion properties, which can be observed in random graphs, are sufficient for the containment of bounded-degree d-degenerate graphs. The proof relies on a simple greedy, deterministic embedding algorithm.
Automatic MiSe System Software Version 1.4803M | admin login