# Expanders and Pseudorandom Graphs

## CSC2429/MAT1306, Fall 2024

## Course Info

Instructor: Swastik Kopparty (swastik.kopparty@utoronto.ca)

Class Time and Place: Mondays 10am-12noon, EM 119 *(Note the nonstandard location: Emmanuel College near the ROM)*

TA: Devansh Shringi (devansh.shringi@mail.utoronto.ca)

*Please email me if you are not registered and want to be added to the mailing list.*

*Please use the course piazza site for questions and discussions.*

This course is about various kinds of pseudorandom graphs such as expander graphs. These are graphs
that appear to be random - a single graph that shares properties with most graphs.
There is a rich and interesting theory with applications to many topics in theoretical computer science and
discrete math. It will also be an opportunity to see many interesting and general-purpose probabilistic, algebraic and analytic tools.
Some possible topics:

- Graph eigenvalues and combinatorial aspects
- Expander graphs: constructions, theory, applications to derandomization of algorithms
- Pseudorandomness of dense graphs, the Szemeredi regularity lemma.
- High dimensional expanders
- Applications to extremal combinatorics

### Homework

Homework 1, Due October 28.
### Scribing

Latex file for scribing,
Latex definitions file.
Scribing guidelines.
### Lectures

- September 9: probability warmup, triangles in G(n,p), the zero-one law for G(n,p)
(notes)
- September 16: the zero-one law for G(n,p) continued, the number of C_4 in a graph with given edge density
- September 23: linear algebra warmup, graph eigenvalues, quasirandomness for dense graphs
- September 30: quasirandomness - discrepancy, eigenvalues, subgraph counts. Szemeredi regularity lemma (the statement), triangle removal lemma.
- October 7: Random walks on graphs, (absolute eigenvalue) expanders, expander mixing lemma, edge expansion.
- October 14: NO CLASS - Thanksgiving
- October 21:
- October 28: NO CLASS - Reading Week
- November 4:
- November 11:
- November 18:
- November 25:
- December 2:
- December 3 (Tuesday): Bonus class

### Papers for reading projects