Benjamini, Itai and Fraczyk, Mikolaj and Kun, Gábor (2022) Expander spanning subgraphs with large girth. ISRAEL JOURNAL OF MATHEMATICS. pp. 1-11. ISSN 0021-2172 (Submitted)
|
Text
2012.pdf Available under License Creative Commons Attribution. Download (148kB) | Preview |
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.
| Item Type: | Article |
|---|---|
| Subjects: | Q Science / természettudomány > QA Mathematics / matematika > QA166-QA166.245 Graphs theory / gráfelmélet |
| SWORD Depositor: | MTMT SWORD |
| Depositing User: | MTMT SWORD |
| Date Deposited: | 28 Sep 2022 14:06 |
| Last Modified: | 24 Apr 2023 11:50 |
| URI: | http://real.mtak.hu/id/eprint/150425 |
Actions (login required)
 |
Edit Item |
