Expander graphs - where Combinatorics and Albegra compete and cooperate.
Avi Wigderson, IAS Princeton and The Hebrew university

Abstract:

Expansion of graphs can be given equivalent definitions in combinatorial and algebraic terms. This is the most basic connection between combinatorics and algebra illuminated by expanders and the quest to construct them. The talk will survey how fertile this connection has been to both fields, focusing on recent results. In particular, we'll explain the zig-zag product of graphs, how it leads to an elementary combinatorial construction of expanders, and its relation to semi-direct product in groups.

Host: Manuel Blum