Finding and using expanders in locally sparse graphs

DOI10.1137/17M1128721MaRDI QIDQ4604650zbMATH OpenOpenAlexWikidataFDO

Authors Michael Krivelevich

Publication date 5 March 2018

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

expandersgraph minorspositional gamesrandom graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Density (toughness, etc.) (05C42) Games on graphs (graph-theoretic aspects) (05C57) Random graphs (graph-theoretic aspects) (05C80) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85) Games involving graphs (91A43) Combinatorial games (91A46)

Abstract: We show that every locally sparse graph contains a linearly sized expanding subgraph. For constants $c_1>c_2>1$, $0<alpha<1$, a graph $G$ on $n$ vertices is called a $(c_1,c_2,alpha)$-graph if it has at least $c_{1}n$ edges, but every vertex subset $WsubsetV(G)$ of size $|W|lealphan$ spans less than $c_2|W|$ edges. We prove that every $(c_1,c_2,alpha)$-graph with bounded degrees contains an induced expander on linearly many vertices. The proof can be made algorithmic. We then discuss several applications of our main result to random graphs, to problems about embedding graph minors, and to positional games.

Recommendations

• Expanders -- how to find them, and what to find in them
• Finding large expanders in graphs: from topological minors to induced subgraphs
• Rolling backwards can move you forward: on embedding problems in sparse expanders
• Minors in expanding graphs
• Expander spanning subgraphs with large girth

Cites work

• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• A Separator Theorem for Nonplanar Graphs
• A Separator Theorem for Planar Graphs
• A sublinear bipartiteness tester for bounded degree graphs
• Anatomy of the giant component: the strictly supercritical regime
• Approximation algorithms for unique games
• Avoider-enforcer: the rules of the game
• Biased positional games on matroids
• Client-waiter games on complete and random graphs
• Difference Equations, Isoperimetric Inequality and Transience of Certain Random Walks
• Eigenvalues and expanders
• Expander graphs and their applications
• Four proofs for the Cheeger inequality and graph partition algorithms
• scientific article; zbMATH DE number 1003278 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 2115090 (Why is no real title available?)
• scientific article; zbMATH DE number 964896 (Why is no real title available?)
• Logarithmically small minors and topological minors
• Long cycles in locally expanding graphs, with applications
• Manipulative waiters with probabilistic intuition
• Minors in graphs of large girth
• On clusterings: good, bad and spectral
• Planarity, Colorability, and Minor Games
• Positional games
• Positional games and the second moment method
• Pseudo-random graphs
• Remarks on positional games. I
• Small complete minors above the extremal edge density
• Subexponential algorithms for unique games and related problems
• The probabilistic method
• Topological Cliques in Graphs
• Topological cliques in graphs II
• Waiter-Client and Client-Waiter planarity, colorability and minor games

Cited in

(14)

• Cycle lengths in expanding graphs
• Expansion in supercritical random subgraphs of the hypercube and its consequences
• Cycle lengths modulo k in expanders
• Finding large expanders in graphs: from topological minors to induced subgraphs
• Expander spanning subgraphs with large girth
• Well-mixing vertices and almost expanders
• Rolling backwards can move you forward: on embedding problems in sparse expanders
• Finding a bounded-degree expander inside a dense one
• Expanders -- how to find them, and what to find in them
• Large complete minors in random subgraphs
• Expanders via local edge flips in quasilinear time
• Expansion in supercritical random subgraphs of expanders and its consequences
• Crux, space constraints and subdivisions
• Modularity and graph expansion

This page was built for publication: Finding and using expanders in locally sparse graphs

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