A family of finite graphs is an expander if it is uniformly sparse and robust, meaning the graphs have uniformly bounded degrees and are difficult to separate into two components. Benjamini asked if, instead of a family of finite graphs, there exists a single infinite graph with these properties, and conjectured there is none whatsoever. We study a version of this problem that uses random walks to formulate robustness, and we resolve the analogue of Benjamini's conjecture in this setting. This is joint work with Mikołaj Frączyk.
Infinite expander graphs and random walks
20.02.2020 15:15 - 17:00
Organiser:
H. Bruin, R. Zweimüller
Location: