Speaker:
Speaker Link:
Institution:
Time:
Host:
Location:
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.