论文标题
在图中找到大型扩展器：从拓扑未成年人到诱发子图
Finding large expanders in graphs: from topological minors to induced subgraphs
论文作者
论文摘要
在本文中，我们考虑了图的结构和几何特性，即大型扩展器的存在。 Krivelevich首先考虑了找到此类结构的问题[Siam J. Disc。数学。 32 1（2018）]。在这里，我们表明，找到一个大型诱发子图的问题可以简化为找到一个拓扑器的简单问题。我们的证明是建设性的，这在算法环境中很有帮助。我们还表明，扩展器图的每个大子图都包含一个大型子图，这本身就是一个扩展器。
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 Krivelevich [SIAM J. Disc. Math. 32 1 (2018)]. 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 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.
