Combinatorics Seminar

When: Sunday, March 6, 10am Where: Schreiber 309 Speaker: Daniel Johannsen, Tel Aviv University Title: Embedding spanning trees in sparse expander graphs

Abstract:

A classical result by Erdos and Renyi 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^eps with eps>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 n^{2/3}log^2 n 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.