Expanders are families of finite connected graphs that are sparse and at the same time highly connected, i.e. hard to disconnect. What makes them fascinating is their ubiquity not only in computer science (designing algorithms, error correcting codes, derandomization, ...) but also in mathematics, with applications ranging from low-dimensional topology to group theory, to operator algebras (see the remarkable survey paper).
展开▼
