Expander spanning subgraphs with large girth
From MaRDI portal
Publication:6357280
DOI10.1007/S11856-022-2446-8arXiv2012.15502MaRDI QIDQ6357280FDOQ6357280
Authors: Itai Benjamini, Mikołaj Frączyk, Gabor Kun 
Publication date: 31 December 2020
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.
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 Q6357280)
