2019/01/27 by Chuzhoy, Julia, Nimavat, Rachit
#Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1901.09349
In this paper we study expander graphs and their minors. Specifically, we attempt to answer the following question: what is the largest function f(n,α,d), such that every n-vertex α-expander with maximum vertex degree at most d contains \bf every graph H with at most f(n,α,d) edges and vertices as a minor? Our main result is that there is some universal constant c, such that f(n,α,d)≥ (n)/(clog n)⋅ (\fracαd )c. This bound achieves a tight dependence on n: it is well known that there are bounded-degree n-vertex expanders, that do not contain any grid with Ω(n/log n) vertices and edges as a minor. The best previous result showed that f(n,α,d) ≥ Ω(n/logκn), where κ depends on both α and d. Additionally, we provide a randomized algorithm, that, given an n-vertex α-expander with maximum vertex degree at most d, and another graph H containing at most (n)/(clog n)⋅ (\fracαd )c vertices and edges, with high probability finds a model of H in G, in time poly(n)⋅ (d/α)O( log(d/α) ). We note that similar but stronger results were independently obtained by Krivelevich and Nenadov: they show that f(n,α,d)=Ω((nα2)/(d2log n) ), and provide an efficient algorithm, that, given an n-vertex α-expander of maximum vertex degree at most d, and a graph H with O( (nα2)/(d2log n) ) vertices and edges, finds a model of H in G. Finally, we observe that expanders are the `most minor-rich' family of graphs in the following sense: for every n-vertex and m-edge graph G, there exists a graph H with O ( (n+m)/(log n) ) vertices and edges, such that H is not a minor of G.