Building Expanders in Three Steps

Special Computer Science/Discrete Mathematics Lecture
Topic:Building Expanders in Three Steps
Speaker:Amir Yehudayoff
Affiliation:Technion--Israel Institute of Technology
Date:Thursday, February 23
Time/Room:3:30pm - 4:30pm/S-101

The talk will have 2 parts (between the parts we will have a break). In the first part, we will discuss two options for using groups to construct expander graphs (Cayley graphs and Schreier diagrams). Specifically, we will see how to construct monotone expanders in this way. As in recent works (e.g. of Bourgain and Gamburd), we will see that the proof consists of 3 different steps. We will shortly discuss these 3 steps. In the second part of the talk we will discuss the 3 steps in more detail, with focus on the last 2: (ii) Helfgott's proof of a product theorem in SL(2,p), and (iii) quasirandom groups, and the use of 2-transitivity to replace quasirandomness.