# Graph Partitioning and Expanders

A summer course to be offered at the University of Salerno on July 12-20.

The mathematics of expander graphs is studied by three distinct communities:
1. The algorithmic problem of finding a small balanced cut in a graph (that is, of finding a certificate that a graph is *not* an expander) is a fundamental problem in the area of approximation algorithms, and good algorithms for it have many applications, from doing image segmentation to driving divide-and-conquer procedures.
2. Explicit constructions of highly expanding graphs have many applications in algorithms, data structures, derandomization and cryptography; many constructions are algebraic, and lead to deep questions in group theory, but certain new constructions are purely combinatorial.
3. The speed of convergence of MCMC (Markov-Chain Monte-Carlo) algorithms is related to the expansion of certain exponentially big graphs, and so the analysis of such algorithms hinges on the ability to bound the expansion of such graphs.
In this course we aim to present key results from these three areas, and to explore the common mathematical background.

Prerequisites: a basic course in linear algebra and a course on algorithms; preferably, also a basic understanding of linear programming and of duality

### References

On sparsest cut approximation algorithms:
On spectral graph theory and on explicit constructions of expander graphs:
On Markov-Chain Monte-Carlo algorithms for uniform generation and approximate counting.

### Lectures

There will be 14 lectures, of 90 minutes each.
• Day one, Lectures 1-2.
• Definition of expansion and sparsest cut
• Overview of the three parts of the course
• Introduction to spectral graph theory
• Easy direction of Cheeger's inequality

• Day two, Lectures 3-4.
• Cheeger's inequality
• Cayley graphs
• Characters of abelian groups

• Day three, Lectures 5-6.
• Characters of abelian groups (continued)
• Spectra of the cycle, the hypercube and the clique
• The Leighton-Rao relaxation of sparsest cut
• Rounding the LR relaxation using embeddings in L1

• Day four, Lectures 7-8.
• Proof of Bourgain's theorem on embedding general metrics in L1.
• Introduction to semidefinite programming.

• Day five, Lectures 9-10.
• More on semidefinite matrices
• The ARV relaxation of sparsest cut and of balanced separator
• Rounding the ARV relaxation of balanced separator (brief sketch)

The following is the initial tentative schedule:
1. Definitions: edge and vertex expansion, uniform and general sparsest cut problems, review of linear algebra
2. Eigenvalues and expansion, Cheeger's inequality and the spectral partitioning algorithm
3. Cheeger's inequality, continued
4. Eigenvalues, expansion, conductance, and random walks
5. Applications of expanders: derandomization
6. Applications of expanders: security amplification of one-way permutations
7. The Margulis-Gabor-Galil construction of expanders
8. The Zig-Zag graph product construction
9. Algorithms for finding sparse cuts: Leighton-Rao, and metric embeddings
10. Algorithms for finding sparse cuts: Arora-Rao-Vazirani
11. Arora-Rao-Vazirani, continued
12. Approximate counting, approximate sampling, and the MCMC method
13. Counting colorings in bounded-degree graphs
14. Counting perfect matchings in dense graphs