Graph Partitioning and Expanders
A summer course to be offered at the University of Salerno on July 1220.
About the course
The mathematics of expander graphs is studied by three distinct
communities:
 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 divideandconquer procedures.

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.
 The speed of
convergence of MCMC (MarkovChain MonteCarlo) 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 MarkovChain MonteCarlo algorithms for uniform generation
and approximate counting.
Lectures
There will be 14 lectures, of 90 minutes each.
 Day one, Lectures 12.
 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 34.
 Cheeger's inequality
 Cayley graphs
 Characters of abelian groups
 Day three, Lectures 56.
 Characters of abelian groups (continued)
 Spectra of the cycle, the hypercube and the clique
 The LeightonRao relaxation of sparsest cut
 Rounding the LR relaxation using embeddings in L1
 Day four, Lectures 78.
 Proof of Bourgain's theorem on embedding general metrics in L1.
 Introduction to semidefinite programming.
 Day five, Lectures 910.
 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:
 Definitions: edge and vertex expansion, uniform and general sparsest
cut problems, review of linear algebra
 Eigenvalues and expansion, Cheeger's inequality and the spectral
partitioning algorithm
 Cheeger's inequality, continued
 Eigenvalues, expansion, conductance, and random walks
 Applications of expanders: derandomization
 Applications of expanders: security amplification of oneway permutations
 The MargulisGaborGalil construction of expanders
 The ZigZag graph product construction
 Algorithms for finding sparse cuts: LeightonRao, and metric embeddings
 Algorithms for finding sparse cuts: AroraRaoVazirani
 AroraRaoVazirani, continued
 Approximate counting, approximate sampling, and the MCMC method
 Counting colorings in boundeddegree graphs
 Counting perfect matchings in dense graphs