Expander Graphs -- Both Local and Global

Understand

Let $G=(V,E)$ be a finite graph.

• For $v\in V$ we denote by $G_v$ the subgraph of $G$ that is induced by $v$'s neighbor set.
• We say that $G$ is $(a,b)$-regular for $a>b>0$ integers, if $G$ is $a$-regular and $G_v$ is $b$-regular for every $v\in V$.
• Recent advances in PCP theory call for the construction of infinitely many $(a,b)$-regular expander graphs $G$ that are expanders also locally.