Open Collections

Description

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