# Applied Extremal Combinatorics

##
18.409 Topics in Theoretical Computer Science

Instructor:
Dan Spielman.

This class meets TTh 2:30-4:00 in room
8-119.

Watch this page as the room may change.

(http://math.mit.edu/~spielman/AEC/)

# Course Announcement

This course covers topics in extremal combinatorics that are
useful for theoretical computer science and coding theory.
This year, we will focus on extremal graph theory and its
interaction with coding theory.
This course is designed for graduate students with experience in
combinatorics, theoretical computer science, or coding theory. Some
knowledge of group theory and linear algebra is necessary.

For each lecture, some student will produce a nice set of lecture
notes (for example, see
the notes from the last time I taught this class or
from
Advanced Complexity Theory).
This task will be divided evenly among the students taking the class
for credit.

The following is a list of the topics that I presently plan to discuss.
We can adjust this list to satisfy the interests of those in the class.

- Eigenvalues of graphs
- structures determined by eigenvalues
- Second eigenvalue/mixing rate
- Isoperimetric number, multicommodity flow, geometric
embeddings and isoperimetry
- Spectral partitioning,
geometric embeddings and eigenvalues

- Isomorphism testing
- Cospectral graphs
- Relation of eigenvalues to automorphisms and
testing isomorphism of graphs of bounded eigenvalue
multiplicity

- Expander graphs
- Random expanders
- Explicit constructions (probably Gabber-Galil)
- Application to re-using random bits

- Eigenvectors of graphs
- Planar graphs
- Regular polytopes
- Cayley graphs
- Strongly-regular graphs
- Relation to spherical designs, extremal point sets, and
density of sphere packings
- Limits of regularity

- Error-correcting codes
- Lower bounds
- Capacity
- Naive volume bound
- Elias's bound
- The JPL bound

- Classical constructions
- Random constructions
- The Golay code and other great codes
- Reed-Solomon codes
- Justesen codes
- Concatenated codes
- Convolutional codes

- Hot constructions
- Low-density parity-check codes
- Turbo codes
- Codes from extremal graphs

- Decoding and encoding algorithms

- A little extremal set theory
- Erdos-Ko-Rado theorem
- Ray-Chaudhuri--Wilson theorem