Expander spanning subgraphs with large girth

Abstract

We conjecture that finite graphs with positive Cheeger constant admit a spanning subgraph with positive Cheeger constant and girth proportional to the diameter. We prove this conjecture for regular expander graphs with large expansion. Our proof relies on the Local Lemma.

11 pages. arXiv admin note: substantial text overlap with arXiv:1303.4982

References in corpus (3)

• Expansion of Random Graphs: New Proofs, New Results
• Expanders have a spanning Lipschitz subgraph with large girth
• Heat kernels are not uniform expanders