Speaker: Michael Krivelevich, Tel Aviv University
Title: Embedding large minors in weak expanders and in sparse random graphs

                         ABSTRACT

A graph G on n vertices is called an alpha-expander if the external neighborhood of every vertex subset U of size |U|<=n/2 in G has size at least alpha*|U|.

Extending and improving the results of Plotkin, Rao and Smith, and of Kleinberg and Rubinfeld from the 90s, we prove that for every alpha>0, an alpha-expander G on n vertices contains every graph H with at most cn/log n vertices and edges as a minor, for c=c(alpha)>0. Alternatively, every n-vertex graph G without sublinear separators contains all graphs with cn/logn vertices and edges as minors. Consequently, a supercritical random graph G(n,(1+epsilon)/n) is typically minor-universal for the class of graphs with cn/log n vertices and edges. The order of magnitude n/log n in the above results is optimal.

A joint work with Rajko Nenadov.