- Course description: Expander graphs. Cayley graphs. Property (T) and (tau); Margulis’s construction of Cayley expanders. Selberg’s 3/16 theorem. The Bourgain-Gamburd machine for constructing Cayley expanders. Quasirandomness. Product set estimates in finite groups of Lie type. Strongly dense free subgroups.

Announcements:

- (Feb 29) I will not be present for classes on Monday March 12.

- Instructor: Terence Tao, tao@math.ucla.edu, x64844, MS 6183
- Lecture: MWF 1-1:50, MS5137
- Quiz section: None
- Office Hours: Tu 1-2
- Textbook: None. I will post lecture notes on my blog site.
- Prerequisites: There are no specific prerequisites for this course, but a general maturity in understanding graduate-level mathematics will be assumed. Familiarity with topics such as algebraic groups, algebraic geometry, representation theory, or spectral theory will be helpful, although we will review what we need from these topics as the course progresses. The Fall 254A course on Hilbert’s fifth problem, while tangentially related to the material here, is not required as a prerequisite for this course.
- Grading: This is a topics course, so I am planning a fairly informal grading scheme. Basically, the base grade will be B provided you actually show up to a significant number of classes, and adjusted upwards according to whether you turn in any homework. There is no final or midterm for this course.
- Reading Assignment: Lecture notes will be provided on my blog site. Students are encouraged to comment on these posts. Note that the notes will cover more material than the lectures.
- Homework: Homework assignments will be assigned from the lecture notes, and will be posted on this page.

- Homework 1 (Due Mon, Jan 23):

- Notes 1, Exercise 1 (Qualitative expansion)
- Notes 1, Exercise 2 (Trace formulae)
- Notes 1, Exercise 9 (Expander mixing lemma)
- Notes 1, Exercise 11 (Expanders have low diameter)

- Homework 2 (Due Mon, Jan 30):

- Notes 2, Exercise 4 (Abelian groups do not expand)
- Notes 2, Exercise 11 (Property (T) and expansion)
- Notes 2, Exercise 14 (Property (T) and expansion, II)
- Notes 2, Exercise 19 (Kazhdan constants and amenability)

- Homework 3 (Due Mon, Feb 6)

- Notes 2, Exercise 23 (SL_2(Z) contains F_2)
- Notes 3, Exercise 6 (Unipotents generate SL_2)
- Notes 3, Exercise 7 (Groups generated by quasirandom groups)
- Notes 3, Exercise 10 (Products in quasirandom groups)

- Homework 4 (Due Mon, Feb 13)

- Homework 5 (Due Mon, Feb 27) (note: no classes Feb 20-24)

- Notes 3, Exercise 23 (Heat kernel bounds)
- Notes 4, Exercise 2 (99% Balog-Szemeredi-Gowers lemma)
- Notes 4, Exercise 7 (Large convolution implies control by approximate group)

- Homework 6 (Due Mon, Mar 5)

- Homework 7 (Due Wednesday, Mar 14)

- Notes 5, Exercise 11 (Alternate form of product theorem)
- Notes 5, Exercise 15 (Large conjugacy classes)

Online resources:

- The blog for this course.
- The Hoory-Linial-Wigderson survey of expander graphs.
- Alexander Lubotsky’s survey of expander graphs.
- Luca Trevisan’s notes on expander graphs in computer science.
- Nick Gill’s notes on expansion in groups.