Finding large expanders in graphs: from topological minors to induced subgraphs (Q2684887)

Summary: In this paper, we consider a structural and geometric property of graphs, namely the presence of large expanders. The problem of finding such structures was first considered by \textit{M. Krivelevich} [SIAM J. Discrete Math. 32, No. 1, 611--623 (2018; Zbl 1381.05040)]. Here, we show that the problem of finding a large induced subgraph that is an expander can be reduced to the simpler problem of finding a large topological minor that is an expander. Our proof is constructive, which is helpful in an algorithmic setting. We also show that every large subgraph of an expander graph contains a large subgraph which is itself an expander.