Kun Gábor: Expander spanning subgraphs with large girth

Bonylultságelmélet szeminárium

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.
Joint work with Benjamini and Fraczyk.

For Teams access please contact Zoltán Király (kiraly[at]cs.elte.hu).
Az előadás MAGYARUL lesz.