Special Computer Science/Discrete Mathematics Lecture

Building Expanders in Three Steps

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.

Date & Time

February 23, 2012 | 3:30pm – 4:30pm

Location

S-101

Affiliation

Technion--Israel Institute of Technology