Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Tuesday, April 24, 2012, 12:15 pm
Duration: 30 minutes
Location: CAB G51
Speaker: Daniel Johannsen (Tel Aviv University)
A classical result by Erdős and Rényi states that asymptotically almost surely (a.a.s.) a random graph G in the G(n,p) model is connected if the expected degree pn of its vertices is slightly larger than log(n). Naturally, this also implies that such a graph contains a spanning tree.
Recently, Krivelevich showed that if pn is at least of order nε with ε>0 then G a.a.s. contains any single fixed spanning tree with bounded maximum degree.
We study the question for which values of pn the random graph G contains every spanning tree with bounded maximum degree.
To this end, we investigate sparse graphs on n vertices which satisfy certain natural expansion properties. We show that each graph with these properties does indeed contain every n-vertex tree with bounded maximum degree. We then see that a random graph drawn according to the G(n,p) model with pn at least of order n2/3log2n a.a.s. has the desired expansion properties and therefore contains every n-vertex tree with bounded maximum degree.
Joint work with Michael Krivelevich and Wojciech Samotij.
Automatic MiSe System Software Version 1.4803M | admin login