Finding large expanders in graphs: from topological minors to induced subgraphs
| Autor: | Louf, Baptiste, Skerman, Fiona |
|---|---|
| Rok vydání: | 2020 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| DOI: | 10.37236/10859 |
| Popis: | 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. Comment: 16 pages, 8 figures |
| Databáze: | arXiv |
| Externí odkaz: |
|