Expander spanning subgraphs with large girth

DOI10.1007/S11856-022-2446-8MaRDI QIDQ2689227zbMATH OpenOpenAlexFDO

Authors Itai Benjamini, Mikołaj Frączyk, Gabor Kun

Publication date 9 March 2023

Published in Israel Journal of Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

large Cheeger constantlarge random \(d\)-regular graphsLovász Local Lemma

Mathematics Subject Classification ID

Expander graphs (05C48) Random graphs (graph-theoretic aspects) (05C80)

Recommendations

• Finding and using expanders in locally sparse graphs
• Percolation on finite graphs and isoperimetric inequalities.
• Expanders -- how to find them, and what to find in them
• Large subgraphs without short cycles
• On high-girth expander graphs with localized eigenvectors

Cites work

• A constructive proof of the general Lovász local lemma
• A measurable-group-theoretic solution to von Neumann's problem
• A topological Tits alternative.
• Automaticity, goals, and environmental interactions.
• Every graph with a positive Cheeger constant contains a tree with a positive Cheeger constant
• Expander graphs and their applications
• Expansion in \(\text{SL}_d(\mathbb Z/q\mathbb Z)\), \(q\) arbitrary.
• Expansion of random graphs: new proofs, new results
• Girth in graphs
• Graph expansion and the unique games conjecture
• Graph sparsification by effective resistances
• HIGH DIMENSIONAL EXPANDERS
• High-girth near-Ramanujan graphs with localized eigenvectors
• scientific article; zbMATH DE number 4004190 (Why is no real title available?)
• scientific article; zbMATH DE number 3492718 (Why is no real title available?)
• Invariant percolation and measured theory of nonamenable groups
• Lifts, discrepancy and nearly optimal spectral gap
• Logarithmic girth expander graphs of \(SL_n({\mathbb{F}}_p)\)
• Quantum ergodicity on large regular graphs
• Ramanujan graphs with small girth
• The measurable Kesten theorem
• Uniform expansion bounds for Cayley graphs of \(\text{SL}_2(\mathbb F_p)\).

Cited in

(8)

• Spanning Eulerian subgraphs of large size
• Finding large expanders in graphs: from topological minors to induced subgraphs
• Finding and using expanders in locally sparse graphs
• Expanders Are Universal for the Class of All Spanning Trees
• scientific article; zbMATH DE number 7378741 (Why is no real title available?)
• Expander spanning subgraphs with large girth
• A survey of degree-boundedness
• Measurable Brooks's theorem for directed graphs

This page was built for publication: Expander spanning subgraphs with large girth

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