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

DOI10.37236/10859MaRDI QIDQ2684887zbMATH OpenOpenAlexFDO

Authors Baptiste Louf, Fiona Skerman

Publication date 17 February 2023

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2012.15722

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

linear sized expander subgraphsrandom walk

Mathematics Subject Classification ID

Expander graphs (05C48) Random walks on graphs (05C81) Graph minors (05C83) Large deviations (60F10)

Review text

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.

Recommendations

• Expanders -- how to find them, and what to find in them
• Finding and using expanders in locally sparse graphs
• Minors in expanding graphs
• Approximation algorithms for finding maximum induced expanders
• Expander spanning subgraphs with large girth

Cites work

• A Chernoff Bound for Random Walks on Expander Graphs
• Eigenvalues and expanders
• Expander graphs and their applications
• Expanders -- how to find them, and what to find in them
• Finding and using expanders in locally sparse graphs
• scientific article; zbMATH DE number 3337135 (Why is no real title available?)
• Large expanders in high genus unicellular maps
• Logarithmically small minors and topological minors
• On clusterings: good, bad and spectral
• Small complete minors above the extremal edge density
• Well-mixing vertices and almost expanders

Cited in

(5)

• Finding and using expanders in locally sparse graphs
• Expanders -- how to find them, and what to find in them
• Finding large expanders in graphs: from topological minors to induced subgraphs
• Crux, space constraints and subdivisions
• Modularity and graph expansion

This page was built for publication: Finding large expanders in graphs: from topological minors to induced subgraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2684887)