Expander Graphs in Pure and Applied Mathematics
arXiv:1105.2389
Abstract
Expander graphs are highly connected sparse finite graphs. They play an important role in computer science as basic building blocks for network constructions, error correcting codes, algorithms and more. In recent years they have started to play an increasing role also in pure mathematics: number theory, group theory, geometry and more. This expository article describes their constructions and various applications in pure and applied mathematics.
This paper is based on notes prepared for the Colloquium Lectures at the Joint Annual Meeting of the American Mathematical Society (AMS) and the Mathematical Association of America (MAA). New Orleans, January 6-9, 2011
References in corpus (14)
- Finite Simple Groups as Expanders
- Expander graphs, gonality and variation of Galois representations
- Universal lattices and Property
- Approximate groups and their applications: work of Bourgain, Gamburd, Helfgott and Sarnak
- Linnik's ergodic method and the distribution of integer points on spheres
- Approximate subgroups of linear groups
- Rank gradient, cost of groups and the rank versus Heegaard genus problem
- Expansion properties of finite simple groups
- An inverse theorem for the Gowers U^{s+1}[N]-norm
- Generalization of Selberg's 3/16 Theorem and Affine Sieve
- Splitting fields of characteristic polynomials of random elements in arithmetic groups
- Invariable generation and the chebotarev invariant of a finite group
- Suzuki groups as expanders
- Edge Transitive Ramanujan Graphs and Highly Symmetric LDPC Good Codes