BIRS Workshop Lecture Videos

Banff International Research Station Logo

BIRS Workshop Lecture Videos

Expander graphs both local and global Linial, Nathan


If $v$ is a vertex in a graph $G$ we denote by $G_v$ the subgraph of $G$ induced on $v$â s neighbors. An $(a,b)$ graph is an $a$-regular graph where every $G_v$ is $b$-regular. Q1: For which $a>b>0$ integers do there exist arbitrarily large, connected $(a,b)$-graphs Q2: Can such graphs be very good expanders Q3: What if you require in addition that every $G_v$ be connected Q4: Can you even make every $G_v$ a very good expander In this talk I will provide some answers to these and related questions and still leave much to be considered on this domain. Joint work with Michael Chapman and Yuval Peled

Item Media

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International