In which we prove properties of expander graphs.
Category Archives: Expanders
CS294 Lecture 18: Margulis-Gabber-Galil Expanders
In which we present an algebraic construction of expanders.
1. The Marguli-Gabber-Galil Expanders
We present a construction of expander graphs due to Margulis, which was the first explicit construction of expanders, and its analysis due to Gabber and Galil. The analysis presented here includes later simplifications, and it follows an exposition of James Lee.
CS294 Lecture 17: Zig-zag Product, continued
In which we analyze the zig-zag graph product.
CS294 Lecture 15: Abelian Cayley graphs
In which we show how to find the eigenvalues and eigenvectors of Cayley graphs of Abelian groups, we find tight examples for various results that we proved in earlier lectures, and, along the way, we develop the general theory of harmonic analysis which includes the Fourier transform of periodic functions of a real variable, the discrete Fourier transform of periodic functions of an integer variable, and the Walsh transform of Boolean functions.
Earlier, we prove the Cheeger inequalities
and the fact that Fiedler’s algorithm, when given an eigenvector of , finds a cut
such that
. We will show that all such results are tight, up to constants, by proving that
- The dimension-
hypercube
has
and
, giving an infinite family of graphs for which
, showing that the first Cheeger inequality is exactly tight.
- The
-cycle
has
, and
, giving an infinite family of graphs for which
, showing that the second Cheeger inequality is tight up to a constant.
- There is an eigenvector of the 2nd eigenvalue of the hypercube
, such that Fiedler’s algorithm, given such a vector, outputs a cut
of expansion
, showing that the analysis of the Fiedler’s algorithm is tight up to a constant.
In this lecture we will develop some theoretical machinery to find the eigenvalues and eigenvectors of Cayley graphs of finite Abelian groups, a class of graphs that includes the cycle and the hypercube, among several other interesting examples. This theory will also be useful later, as a starting point to talk about constructions of expanders.
For readers familiar with the Fourier analysis of Boolean functions, or the discrete Fourier analysis of functions , or the standard Fourier analysis of periodic real functions, this theory will give a more general, and hopefully interesting, way to look at what they already know.
CS 294 Lecture 14: ARV Analysis, Part 3
In which we complete the analysis of the ARV rounding algorithm
We are finally going to complete the analysis of the Arora-Rao-Vazirani rounding algorithm, which rounds a Semidefinite Programming solution of a relaxation of sparsest cut into an actual cut, with an approximation ratio .
In previous lectures, we reduced the analysis of the algorithm to the following claim.
CS294 Lecture 13: ARV Analysis, cont’d
In which we continue the analysis of the ARV rounding algorithm
We are continuing the analysis of the Arora-Rao-Vazirani rounding algorithm, which rounds a Semidefinite Programming solution of a relaxation of sparsest cut into an actual cut, with an approximation ratio .
In previous lectures, we reduced the analysis of the algorithm to the following claim.
CS294 Lecture 12: ARV Analysis
In which we begin the analysis of the ARV rounding algorithm
We want to prove
Lemma 1 (ARV Main Lemma) Let
be a negative-type metric over a set
such that the points are contained in a unit ball and have constant average distance, that is,
- there is a vertex
such that
for every
![]()
![]()
Then there are sets
such that
;
- for every
and every
,
![]()
where the multiplicative factors hidden in the
and
notations depend only on
.
In this lecture, we will show how to reduce the ARV Main Lemma to a statement of the following form: if is a set of vectors such that the metric
in the ARV Main Lemma can be written as
, and
is a random Gaussian vectors, and if
is such that with
probability, there are
disjoint pairs
such that
and
, then
. We will then prove such a statement in the next lecture.
CS294 Lecture 11: ARV
In which we introduce semi-definite programming and a semi-definite programming relaxation of sparsest cut, and we reduce its analysis to a key lemma that we will prove in the next lecture(s)
CS294 Lecture 10: Bourgain’s Theorem
In which we prove Bourgain’s theorem.
Today we prove the following theorem.
Theorem 1 (Bourgain) Let
be a semimetric defined over a finite set
. Then there exists a mapping
such that, for every two elements
,
where
is an absolute constant. Given
, the mapping
can be found with high probability in randomized polynomial time in
.
Together with the results that we proved in the last lecture, this implies that an optimal solution to the Leighton-Rao relaxation can be rounded to an -approximate solution to the sparsest cut problem. This was the best known approximation algorithm for sparsest cut for 15 years, until the Arora-Rao-Vazirani algorithm, which will be our next topic.
CS294 Lecture 9: The Sparsest Cut Problem
In which we introduce the sparsest cut problem and the Leighton-Rao relaxation.
1. The Uniform Sparsest Cut problem, Edge Expansion and
Let be an undirected graph with
vertices.
We define the uniform sparsity of a cut as
(we will omit the subscript when clear from the context) and the uniform sparsest cut of a graph is
In -regular graphs, approximating the uniform sparsest cut is equivalent (up to a factor of 2 in the approximation) to approximating the edge expansion, because, for every cut
, we have
and, noting that, for every, ,
we have, for every ,
and so
It will be instructive to see that, in -regular graphs,
is a relaxation of
, a fact that gives an alternative proof of the easy direction
of Cheeger’s inequalities.