Michael Krivelevich


Tel Aviv University


Tuesday, February 18, 2020 - 11:00am




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.