The objective of this course is to present a number of recent constructions of expander graphs, which are a type of sparse but “pseudorandom” graph of importance in computer science, the theory of random walks, geometric group theory, and in number theory. The subject of expander graphs and their applications is an immense one, and we will not possibly be able to cover it in full in this course. In particular, we will say almost nothing about the important applications of expander graphs to computer science, for instance in constructing good pseudorandom number generators, derandomising a probabilistic algorithm, constructing error correcting codes, or in building probabilistically checkable proofs. For such topics, I recommend the survey of Hoory-Linial-Wigderson. We will also only pass very lightly over the other applications of expander graphs, though if time permits I may discuss at the end of the course the application of expander graphs in finite groups such as to certain sieving problems in analytic number theory, following the work of Bourgain, Gamburd, and Sarnak.
Instead of focusing on applications, this course will concern itself much more with the task of constructing expander graphs. This is a surprisingly non-trivial problem. On one hand, an easy application of the probabilistic method shows that a randomly chosen (large, regular, bounded-degree) graph will be an expander graph with very high probability, so expander graphs are extremely abundant. On the other hand, in many applications, one wants an expander graph that is more deterministic in nature (requiring either no or very few random choices to build), and of a more specialised form. For the applications to number theory or geometric group theory, it is of particular interest to determine the expansion properties of a very symmetric type of graph, namely a Cayley graph; we will also occasionally work with the more general concept of a Schreier graph. It turns out that such questions are related to deep properties of various groups of Lie type (such as
or
), such as Kazhdan’s property (T), the first nontrivial eigenvalue of a Laplacian on a symmetric space
associated to
, the quasirandomness of
(as measured by the size of irreducible representations), and the product theory of subsets of
. These properties are of intrinsic interest to many other fields of mathematics (e.g. ergodic theory, operator algebras, additive combinatorics, representation theory, finite group theory, number theory, etc.), and it is quite remarkable that a single problem – namely the construction of expander graphs – is so deeply connected with such a rich and diverse array of mathematical topics. (Perhaps this is because so many of these fields are all grappling with aspects of a single general problem in mathematics, namely when to determine whether a given mathematical object or process of interest “behaves pseudorandomly” or not, and how this is connected with the symmetry group of that object or process.)
(There are also other important constructions of expander graphs that are not related to Cayley or Schreier graphs, such as those graphs constructed by the zigzag product construction, but we will not discuss those types of graphs in this course, again referring the reader to the survey of Hoory, Linial, and Wigderson.)
— 1. Expander graphs —
We begin by defining the concept of an expander graph formally. As with many fundamentally important concepts in mathematics, there are a number of equivalent definitions of this concept. We will adopt a “spectral” perspective towards expander graphs, defining them in terms of a certain spectral gap, but will relate this formulation of expansion to the more classical notion of edge expansion later in this section.
We begin by recalling the notion of a graph. To avoid some very minor technical issues, we will work with undirected, loop-free, multiplicity-free graphs (though later, when we discuss Cayley graphs, we will allow loops and repetition).
Definition 1 A graph is a pair
, where
is a set (called the vertex set of
), and
is a collection of unordered pairs
of distinct elements
of
, known as the edge set of
. Elements of
or
are called vertices and edges of
A graph is finite if the vertex set (and hence the edge set) is finite. If
is a natural number, we say that a graph
is
-regular if each vertex of
is contained in exactly
edges in
; we refer to
as the degree of the regular graphs.
Example 2 The complete graph
on a vertex set
has edge set
. If
has
elements, the complete graph is
-regular.
In this course, we will mostly be interested in constant-degree large finite regular graphs, in which is fixed (e.g.
), and the number
of vertices is going off to infinity.
Given a finite graph , one can define the adjacency operator
on functions
by the formula
thus is the sum of
over all of the neighbours of
. If one enumerates the vertices
as
in some fashion, then one can associate
with an
matrix, known as the adjacency matrix of
(with this choice of vertex enumeration).
As our graphs are undirected, the adjacency operator is clearly self-adjoint (and the adjacency matrix is real symmetric). By the spectral theorem,
thus has
real eigenvalues
We will write as
whenever we need to emphasise the dependence on the graph
.
The largest eigenvalue is easily understood for
-regular graphs:
Lemma 3 If
is a
-regular graph, then
Proof: Clearly (where we write
for the constant function), and so
is an eigenvalue of
with eigenvector
. On the other hand, for any
with norm one, one has
and so has operator norm
(or equivalently, all eigenvalues of
lie between
and
). The claim follows.
Now we turn to the next eigenvalue after .
Definition 4 Let
and
. A finite
-regular graph is said to be a (one-sided)
-expander if one has
and a two-sided
-expander if one also has
A sequence
of finite
-regular graphs is said to be a one-sided (resp. two-sided) expander family if there is an
such that
is a one-sided (resp. two-sided)
-expander for all sufficiently large
.
Remark 5 The operator
is sometimes known as the graph Laplacian (though note that it is also common to use the normalisation
instead of
in many texts, particularly if one wishes to generalise to graphs that are not perfectly regular). This is a positive semi-definite operator with at least one zero eigenvalue (corresponding to the eigenvector
). A graph is an
-expander if and only if there is a spectral gap of size
in
, in the sense that the first eigenvalue of
exceeds the second by at least
. The graph Laplacian is analogous to the classical Laplacian in Euclidean space (or the Laplace-Beltrami operator on Riemannian manifolds); we will see some formalisations of this analogy later in this course.
The original definition of expander graphs focused on one-sided expanders, but it will be slightly more natural in this course to focus on the two-sided expanders.
Strictly speaking, we have not defined the notion of a (one or two-sided) expander graph in the above definition; we have defined an -expander graph for any given parameter
, and have defined the notion of an expander family, which is a sequence of graphs rather than for an individual graph. One could propose defining an expander graph to be a graph that is a one or two-sided
-expander for some
(or equivalently, a graph
such that the constant sequence
is an expander family), but this definition collapses to existing concepts in graph theory:
Exercise 6 (Qualitative expansion) Let
, and let
be a finite
-regular graph.
- Show that
if and only if
is not connected.
- Show that
if and only if
contains a non-empty bipartite graph as a connected component.
Thus, a graph is a one-sided expander for some
if and only if it is connected, and a two-sided expander for some
if and only if it is connected and not bipartite.
It is therefore necessary to either keep a more quantitative track of the parameter, or work with expander families (typically involving vertex sets whose cardinality goes to infinity) rather than with individual graphs. (Alternatively, one could adopt a nonstandard analysis viewpoint and work with ultra expander graphs – i.e. ultraproducts of expander families – but we will postpone using this viewpoint until much later in the course.) Nevertheless, we will often informally drop the
parameter (or the use of families) and informally refer simply to “expander graphs” in our discussion.
Exercise 7 (Trace formulae) Let
be a
-regular graph on
vertices for some
.
- (i) Show that
.
- (ii) Show that
.
- (iii) Show that
, where
denotes a quantity that goes to zero as
for fixed
.
Remark 8 The above exercise places an upper bound on how strong of a two-sided expansion one can obtain for a large
-regular graph. It is not quite sharp; it turns out that one can obtain the improvement
a result of Alon and Boppana; see for instance the survey of Hoory-Linial-Wigderson for a proof. Graphs with
are known as Ramanujan graphs, and (as the name suggests) have connections to number theory, but we will not discuss this topic here; see for instance this text of Davidoff, Sarnak, and Valette for more discussion.
We will give a probabilistic construction of an expander family later, but let us first give an example of a family of regular graphs that is not an expander family.
Exercise 9 For each
, let
be the
-regular graph whose vertex set is the cyclic group
, and whose edge set is the set of pairs
for
. (This is a basic example of a Cayley graph. Cayley graphs will be discussed in more depth in the next set of notes.)
- Show that the eigenvalues of the adjacency operator
associated to
are
for
. (Hint: you may find the discrete Fourier transform to be helpful.)
- Show that
is not a one-sided expander family (and is thus not a two-sided expander family either). This is despite
always being connected (and non-bipartite for
odd).
The next exercise shows that the complete graph is an excellent expander; the whole point, though, of expander graph constructions is to come up with much sparser graphs that still has many of the connectivity and expansion properties of the complete graph.
Exercise 10 Let
be the complete graph on
vertices, which is of course a
-regular graph. Show that
and so
is a one-sided
-expander and a two-sided
-expander. (This is not a counterexample to Exercise 7(iii), because the error term
is only negligible in the regime when
is either fixed or is a very slowly growing function of
, and this is definitely not the case for the complete graph.)
Exercise 11 Let
be a
-regular graph on
vertices. Let
be the complement graph, consisting of all the edges connecting two vertices in
that are not in
, thus
is an
-regular graph. Show that
for all
.
Exercise 12 Let
be an even number, and let
be the complete bipartite graph between two sets of
vertices each, thus
is an
-regular graph. Show that
and
. Thus,
is a one-sided
-expander, but is not a two-sided expander at all.
Exercise 13 (Expansion and Poincaré inequality) If
is a
-regular graph and
is a function, define the gradient magnitude
by the formula
Show that
is a one-sided
-expander if and only if one has the Poincaré inequality
whenever
has mean zero.
— 2. Connection with edge expansion —
The intuition to explain Exercise 9 should be that while is, strictly speaking, connected, it is not very strongly connected; the paths connecting a typical pair of points are quite long (comparable to
, the number of vertices) and it is easy to disconnect the graph into two large pieces simply by removing a handful of edges.
We now make this intuition more precise. Given two subsets of the vertex set
in a graph
, define
to be the set of all pairs
such that
. Note that the cardinality of this set can be expressed in terms of the adjacency operator as
Define the boundary of a subset
of
to be the set
, thus
is essentially the set of all edges that connect an element of
to an element outside of
. We define the edge expansion ratio
of the graph
to be given by the formula
where ranges over all subsets of
of cardinality at most
. (Some upper bound on
is needed to avoid this quantity from degenerating, since
becomes empty when
.) The quantity
can be interpreted as a type of isoperimetric constant for
, analogous to the Cheeger constant of a compact Riemannian manifold, and so
is sometimes known as the Cheeger constant of the graph
.
Note that is non-zero precisely when
is connected. (If
is disconnected, at least one of the components
will have cardinality less than
.) We have an analogous statement for one-sided expansion:
Proposition 14 (Weak discrete Cheeger inequality) Let
, and let
be a family of finite
-regular graphs. Then the following are equivalent:
- (i)
form a one-sided expander family.
- (ii) There exists
such that
for all sufficiently large
.
Proof: Let be a large number. We abbreviate
as
.
We first establish the easy direction of this proposition, namely that (i) implies (ii). If is large enough, then from the hypothesis (i) we have
for some
independent of
.
Let be a subset of
with
. We consider the quantity
We split into a multiple
of the first eigenvector
, plus the remainder
, Using the spectral decomposition of
, we can upper bound (1) by
which after a brief calculation evaluates to
On the other hand, (1) is also equal to the number of (ordered) pairs of adjacent vertices . Since each
is adjacent to exactly
vertices, we conclude that there are at least
pairs
such that
and
. Thus
and so , and the claim (ii) follows.
Now we establish the harder direction, in which we assume (ii) and prove (i). Thus we may assume that for some
independent of
.
The difficulty here is basically that the hypothesis (ii) only controls the action of
on indicator functions
, whereas the conclusion (ii) basically requires us to understand
for arbitrary functions
. Indeed, from the spectral decomposition one has
whenever has norm one and mean zero, and
is independent of
. Since
has real matrix coefficients, we may assume without loss of generality that
is real.
The mean zero hypothesis is needed to keep the function away from
, but it forces
to change sign. It will be more convenient to first establish a variant of (2), namely that
whenever is non-negative and supported on a set of cardinality at most
.
Let us assume (3) for now and see why it implies (2). Let have norm one and mean zero. We split
into positive and negative parts, where
are non-negative with disjoint supports. Observe that
is positive, and so
Also we have
At least one of and
is supported on a set of size at most
. By symmetry we may assume that
has this small support. Let
be a small quantity (depending on
) to be chosen later. If
has
norm at least
, then applying (3) to
(and the trivial bound
for
) we have
which would suffice. So we may assume that has norm at most
. By Cauchy-Schwarz, this implies that
, and thus (as
has mean zero)
. Ordering the values
and applying Markov’s inequality, we see that we can split
as the sum of a function
supported on a set of size at most
, plus an error of
norm
. Applying (3) to
and
and using the triangle inequality (and Cauchy-Schwarz) to deal with the error term, we see that
which also suffices (if is sufficiently small).
It remains to prove (3). We use the “wedding cake” decomposition, writing as an integral
where . By construction, all the
have cardinality at most
and are non-increasing in
. Also, a computation of the
norm shows that
Expanding and using symmetry, we obtain
We can bound the integrand in two ways. Firstly, since is bounded by
, one has
Secondly, we may bound by
.
On the other hand, from the hypothesis we see that
, and hence
We insert the first bound for and the second bound for
, for some
to be determined later, and conclude that
Interchanging the integrals in the second integral, we conclude that
For small enough, one can check that
for some
depending only on
, and the claim (3) then follows from (4).
Example 15 The graphs in Exercise 9 contain large sets with small boundary (e.g.
for
), which gives a non-spectral way to establish that they do not form an expander family.
Exercise 16 Show that if
, then the only expander families of
-regular graphs are those families of bounded size (i.e. the vertex sets
have cardinality bounded in
).
Remark 17 There is a more precise relationship between the edge expansion ratio
and the best constant
that makes
a one-sided
-expander, namely the discrete Cheeger inequality
first proven by Dodzuik, by Alon-Milman, and by Alon (and based on a continuous isoperimetric inequality of Cheeger and of Buser); see for instance this blog post of Luca Trevisan for a proof of the second inequality (the first inequality is already implicit in the proof of the above lemma). However, we will not use this more precise inequality here.
There is an analogous criterion for two-sided expansion, but it is more complicated to state. Here is one formulation that is quite useful:
Exercise 18 (Expander mixing lemma) Let
be a
-regular graph on
vertices which is a two-sided
-expander. Show that for any subsets
of
, one has
(Actually, the factors
on the right-hand side can be refined slightly to
and
respectively.)
Thus, two-sided expanders behave analogously to the pseudorandom graphs that appear in the Szemerédi regularity lemma (but with the caveat that expanders are usually sparse graphs, whereas pseudorandom graphs are usually dense).
Here is variant of the above lemma that more closely resembles Proposition 14.
Exercise 19 Let
, and let
be a family of finite
-regular graphs. Show that the following are equivalent:
- (i)
form a two-sided expander family.
- (ii) There exists
such that whenever
is sufficiently large and
are subsets of
of cardinality at most
, then
.
The exercises below connect expansion to some other graph-theoretic properties. On a connected graph , one can define the graph metric
by defining
to be the length of the shortest path from
to
using only edges of
. This is easily seen to be a metric on
.
Exercise 20 (Expanders have low diameter) Let
be a
-regular graph on
vertices that is a one-sided
-expander for some
and
. Show that there is a constant
depending only on
and
such that for every vertex
and any radius
, the ball
has cardinality
(Hint: first establish the weaker bound
.) In particular,
has diameter
, where the implied constant can depend on
and
.
Exercise 21 (Expanders have high connectivity) Let
be a
-regular graph on
vertices that is a one-sided
-expander for some
and
. Show that if one removes
edges from
for some
, then the resulting graph has a connected component of size at least
, where
depends only on
and
.
Exercise 22 (Expanders have high chromatic number) Let
be a
-regular graph on
vertices that is a two-sided
-expander for some
and
.
- (i) Show that any independent set in
has cardinality at most
.
- (ii) Show that the chromatic number of
is at least
. (Of course, this bound only becomes non-trivial for
close to
; however, it is still useful for constructing bounded-degree graphs of high chromatic number and large girth.)
Exercise 23 (Expansion and concentration of measure) Let
be a
-regular graph on
vertices that is a one-sided
-expander for some
and
. Let
be a function which is Lipschitz with some Lipschitz constant
, thus
for all
. Let
be a median value of
(thus
for at least half of the vertices
, and
for at least half the vertices
; note that the median may be non-unique in some cases.) Show that
for all
and some constants
depending only on
.
— 3. Random walks on expanders —
We now discuss a connection between expanders and random walks, which will be of particular importance in this course as a tool for demonstrating expansion. Given a -regular graph
for some
, and an initial vertex
, we define the random walk on
starting at
to be a random sequence
of vertices in
defined recursively by setting, once
have been chosen,
to be one of the
neighbours of
, chosen at random. (The existence of such a random process can be easily justified by using the Kolmogorov extension theorem.) For each
, let
be the probability distribution of
, thus
Thus is the Dirac mass
at
, and we have the recursion
and thus
Among other things, this shows that the quantity , which measures the extent to which
is uniformly distributed, is non-increasing in
. The rate of this decrease is tied to the expansion properties of the graph:
Exercise 24 Let
, and let
be a family of finite
-regular graphs. Let
. Show that the following are equivalent:
- (i) The
are a two-sided expander family.
- (ii) There is a
independent of
, such that for all sufficiently large
one has
for all
, and all choices of initial vertex
.
Informally, the above exercise asserts that a two-sided expander on vertices is one for which random walks (from an arbitrary starting point) become very close to uniform in just
steps. (Compare with, say, the graphs in (9), in which the random walks do not come close to mixing until time well beyond
, as indicated by the central limit theorem.) This rapid mixing is useful for many applications; for instance, it can be used in computer science to generate almost perfectly uniformly distributed random elements of various interesting sets (e.g. elements of a finite group); see the survey of Hoory-Linial-Wigderson for more discussion. It is also useful in number theory to facilitate certain sieving estimates, as I hope to discuss later in this course.
Remark 25 In the above exercise, we assumed that the initial vertex
was deterministic rather than random. However, it is easy to see (from Minkowski’s inequality) that the exercise also holds if we permit
to be drawn from an arbitrary probability distribution on
, rather than being a single deterministic vertex. Thus one can view the uniform distribution in a two-sided expander to be a very strong attractor for all the other probability distributions on the vertex set.
Remark 26 The
norm is the most convenient norm to use when using the spectral theorem, but one can certainly replace this norm if desired by other norms (e.g. the
norm, which in this finite setting is the same thing as the total variation norm), after adjusting the lower bound of
slightly, since all norms on a finite-dimensional space are equivalent (though one typically has to concede some powers of
to attain this equivalency). One can also use some other norm-like quantities here to measure distance to uniformity, such as Shannon entropy, although we will not do so here.
Note that for graphs that are only one-sided expanders instead of two-sided expanders, the random walk is only partially mixing, in that the probability distribution tends to flatten out rapidly, but not converge as rapidly (or at all) to the uniform distribution. For instance, in the case of the complete bipartite graph , it is clear that the random walk simply alternates between the two vertex sets of size
in the bipartite graph (although it is uniformly distributed in each set). But this lack of rapid mixing can be dealt with by replacing the random walk with the lazy random walk
, which is defined similarly to the random walk
except that
is only set equal to a randomly chosen neighbour of
with probability
, and remains equal to
with probability
. (One can also select other probabilities here than
, as this will not significantly affect the exercise below.) Indeed, we have:
Exercise 27 Let
, and let
be a family of finite
-regular graphs. Let
. Show that the following are equivalent:
- (i) The
are a one-sided expander family.
- (ii) There is a
independent of
, such that for all sufficiently large
one has
for all
, and all choices of initial vertex
, where
is the law of the random walk
.
— 4. Random graphs as expanders —
We now turn to the task of constructing expander families of -regular graphs. The first result in this direction was by Pinsker in 1973 (with a closely related result also established by Barzdin and Kolmogorov in 1967), who showed that if one chose a
-regular graph on
vertices randomly, and then sent
to infinity along a sufficiently sparse sequence, the resulting sequence would be almost surely be an expander family. (Here, of course, one needs to avoid the parity obstruction that one cannot have a
-regular graph on
vertices if
and
are both odd.) We will not quite prove this result here (because it requires some understanding of the probability distribution of
-regular graphs, which has some subtleties as the parity obstruction already indicates), but establish a closely related result, in which
is restricted to be even (to avoid parity problems) and sufficiently large (for convenience) and the
-regular graph is drawn from a slightly non-uniform distribution.
Before we do this, though, let us perform a heuristic computation as to why, when is fixed but large, and
goes to infinity, one expects a “random”
-regular graph
on
vertices to be an expander. For simplicity, we work with the one-sided expansion condition. By Proposition 14, we would then like to say that with high probability, one has
for all with cardinality at most
, and some
independent of
. An equivalent formulation would be to say that the neighbourhood
of
has to have cardinality at least
for all
with cardinality at most
, and some
independent of
. Thus, we wish to exclude the possibility that there are sets
with
and
, for which all the edges starting from
end up in
.
To bound this failure probability, we use the union bound: we try each pair in turn, bound the probability that the claim follows for that particular value of
, and then sum in
. The goal is to obtain a total probability bound of
, that goes to zero as
for fixed
.
Accordingly, pick , and then pick
of cardinality
, and then
of cardinality
, where
for some small constant
to be chosen later. For each fixed
, there are
choices of
and
. For each
, there are
edges emenating from
. Intuitively, if we choose the graph randomly, each edge has a probability about
of landing back in
, so the probability that they all do is about
. So the failure rate should be about
We can bound somewhat crudely as
. Applying Stirling’s formula, we obtain a bound of
For small enough,
is less than
(say), and then (for
large enough) we see that this series is bounded by
as required.
Now we turn to the rigorous construction of random expander graphs. We will assume that is a large (but fixed) even integer,
. To build a
-regular graph on
vertices
, what we will do is pick
permutations
, and let
be the graph formed by connecting
to
for all
and
. This is not always a
-regular graph, but we will be able to show the following two claims (if
is large enough):
Proposition 28 (
can be
-regular) The graph
is
-regular with probability at least
, where
depends only on
.
Proposition 29 (
usually expands) There is an
depending only on
, such that the probability that
is
-regular but not a one-sided
-expander is
.
Putting these two propositions together, we conclude
Corollary 30 With probability at least
,
is a
-regular one-sided
-expander.
In particular, this allows us to construct one-sided expander families of -regular graphs for any fixed large even
.
Remark 31 If one allowed graphs to have multiple edges and loops, then it would be possible to dispense with the need for Proposition 28, and show that
(now viewed as a
-regular graph with multiple edges and loops) is a one-sided
-expander with probability
. (This requires extending results such as the weak discrete Cheeger inequality to the case when there are multiple edges and loops, but this turns out to be straightforward.) However, we will not do so here as it requires one to introduce a slight amount of additional notation.
Let us prove Proposition 29 first, which will follow the informal sketch at the beginning of this section. By Proposition 14, it suffices to show that there is a depending only on
such that the probability that
is
-regular with
is
. As in the sketch, we first bound for each
and
with
and
, where
, the probability that all the edges from
end up in
. A necessary condition for this to occur is that
for each
. For each
, and for fixed
, the probability that the random permutation
does this is
so the total failure probability can be bounded by
which is acceptable as discussed previously.
Now we turn to Proposition 28. We observe that will be
-regular unless there are distinct
and a vertex
such that either
,
,
, or
(as such cases lead to repeated edges or loops). Unfortunately, each of these events can occur with a fairly sizeable probability (e.g. for each
, the probability that
for some
is about
, by the classical theory of derangements), so the union bound is not enough here. Instead, we will proceed by an interpolant between the union bound and the inclusion-exclusion formula, known as the Bonferroni inequalities:
Exercise 32 (Bonferroni inequalities)
- (i) Show that if
are natural numbers, that
when
is even, and
when
is odd, where we adopt the convention that
when
.
- (ii) Show that if
and
are events, then
when
is even, and
when
is odd. (Note that the
case of this inequality is essentially the union bound, and the
case is the inclusion-exclusion formula.) Here we adopt the convention that the empty intersection occurs with probability
.
We return to the proof of Proposition 28. By a conditioning argument, it suffices to show the following:
Proposition 33 Let
, and suppose that the permutations
have already been chosen (and are now viewed as fixed deterministic objects). Let
be a permutation chosen uniformly at random. Then with probability at least
for some
depending only on
, one has
for all
and
.
It remains to establish Proposition 33. We modify an argument of Bollobas. Consider the set of pairs
Each pair in
gives rise to a bad event
. Each vertex
gives rise to another bad event
In all, this gives separate events for some
, which we enumerate as
. Our task is to show that
It is easy to check (by direct counting arguments) that
for each . More generally, for any fixed
, the same sort of counting arguments (which we leave as an exercise) the approximate independence
for all but of the tuples
with
, with
for the exceptional tuples. (The subscripts in the -notation indicate that the implied constant in that notation can depend on the subscripted parameters.) In particular, we have
and thus by the Bonferroni inequalities
for any odd . But from Taylor series expansion, the sum on the right-hand side converges to the positive quantity
, and the claim follows by taking
to be a sufficiently large odd number depending on
.
Exercise 35 Show that the total number
of failure events is asymptotically distributed according to the Poisson distribution of intensity
, or more precisely that
for any natural number
.
Remark 36 Another way to establish Proposition 28, via the “swapping method”, was pointed out to me by Brendan McKay here. The key observation is that if
permutations
have
problematic edges (i.e. edges that are either repeated or loops), and then one applies
random transpositions to the
(as selected at random), then with probability
(if
is sufficiently large depending on
), all problematic edges are erased and one obtains a random regular graph. Conversely, if one starts with a random regular graph and applies
random transpositions, the probability of obtaining
problematic edges as a result is
. Combining the two facts, we see that
is the probability of having
problematic edges, then
for each fixed
(and
sufficiently large depending on
). Since the expected number of problematic edges is bounded ,the desired bound
then follows from Markov’s inequality and the pigeonhole principle.
Exercise 37 Show that “one-sided” can be replaced with “two-sided” in Proposition 29 and hence in Corollary 30.
Remark 38 It turns out that the random
-regular graphs formed by taking
permutations as indicated above, and conditioning on the event that there are no “collisions” (so that one genuinely gets a
-regular graph) does not quite give a uniform distribution on the
-regular graphs. However, it is close enough to one that any property which is true with probability
for this model of random
-regular graph, is also true with probability
for uniform
-regular graphs, and conversely. This fact (known as contiguity of the two random models, and analogous to the concept of mutually absolutely continuous measures in measure theory) is established for instance in this survey of Wormald. As a consequence of this fact (and a more refined version of the above analysis), one can show that
of all
-regular graphs on
vertices are
-expanders for some
if
(assuming of course the parity requirement that
be even, otherwise there are no
-regular graphs at all).
47 comments
Comments feed for this article
3 December, 2011 at 10:58 am
Ben Wieland
Some comments on one-sided vs two-sided:
The statement of Exercise 1 seems unnecessarily complicated to me. Such an induced subgraph is graph is necessarily disconnected from the rest of the graph, so one might talk of a bipartite component. Moreover, for the final summary, where you assume it is already that it is connected, the condition is simply that the whole graph is not bipartite.
It seems to me a little misleading to say that on a one-sided expander “the random walk will not mix rapidly.” This implies that it will mix slowly, but the failure is that it will not mix. To the extent that it does mix, approaching uniformity on each the vertices of a each parity, it does so quickly. Of course, your example make this clear.
[Fair enough; I’ve edited the text accordingly. -T.]
3 December, 2011 at 8:02 pm
Nick Cook
Looking at Exercise 7, I am wondering if when we take the size of the graph to infinity (I don’t know yet which way we will do this) it will be useful to seek better control of the form
, say, where how large we can take
will be determined by the “dimension”
of the limit graph (and
depending on
). Could higher derivatives and general Sobolev inequalities be useful for studying graphs? It would make sense that we could have these on a family of graphs converging (in some sense) to the torus or to
.
3 December, 2011 at 9:11 pm
Terence Tao
Yes, one can certainly study these sorts of Sobolev inequalities for “finite-dimensional” graphs that resemble discretisations of finite-dimensional Riemannian manifolds. That’s a different regime, though, from the expander graph regime, which behaves more like an infinite-dimensional space (or like the large-scale geometry of hyperbolic space), for instance with balls that grow exponentially rather than polynomially.
3 December, 2011 at 8:29 pm
Nick Cook
Exercise 15 (where we are considering the discrete time semigroup
) makes me wonder if analogously to Exercise 7 we can characterize two-sided expander graphs as those having a log-Sobolev inequality.
3 December, 2011 at 9:23 pm
Terence Tao
There are some entropy inequalities for expander graphs that vaguely resemble log-Sobolev inequalities, but the log Sobolev constants themselves are not completely favourable; for instance, in this paper of Bobkov and Tetali it is shown that the log-Sobolev constant of a bounded degree expander tends to zero like
.
3 December, 2011 at 10:22 pm
itai
An expanders problem: Is there a family
of finite d-regular graphs, with size growing to infinity,
‘s are uniform expanders?
so that all balls in all the
Since the graphs restricted to balls may not be regular, by expanders we mean bounded degree graphs with a uniform edge expansion.
(That is, there is
, for all
and any v in any of the graphs
‘s
is a sequence of expanders with girth growing to infinity, then if r is smaller then girth then balls of radius r are trees and thus not uniformly expanders as r grows).
the ball B(v,r) is h- expander, expander with a uniform expansion constant h.
Note e.g. that if
I conjecture that there is no such family.
6 December, 2011 at 10:39 am
254B, Notes 2: Cayley graphs and Kazhdan’s property (T) « What’s new
[…] the previous set of notes we introduced the notion of expansion in arbitrary -regular graphs. For the rest of the course, we […]
6 December, 2011 at 4:35 pm
Arie Israel
In the second part of Exercise 1, I think the statement should read as: $\lambda_n=-k$ if and only if $G$ contains a non-empty bipartite graph as a connected component.
[Corrected, thanks – T.]
7 December, 2011 at 7:15 am
Gabriel
In Exercise 10, shouldn’t the inequality in (ii) be reverted? Thanks! [Actually, I believe the inequality signs are in the right direction here. -T.]
7 December, 2011 at 8:37 pm
Weekly Picks « Mathblogging.org — the Blog
[…] Terry Tao started a lecture notes series on expander graphs while E. Kowalski mused about his notes on expanders and two different Caley graphs of the group of order 2. […]
12 December, 2011 at 11:54 am
david joyner
Is there a typo in the statement of Remark 2? I think the 2 is supposed to go outside the square root in both the statement of the Alon-Boppana bound and the definition of the Ramanujan graph.
[Corrected, thanks – T.]
12 December, 2011 at 4:34 pm
Anonymous
I think the title ought to read “254B…” (rather than “245B…”). [Corrected, thanks – T.]
16 December, 2011 at 10:14 am
254B, Notes 3: Quasirandom groups, expansion, and Selberg’s 3/16 theorem « What’s new
[…] (compare with the expander mixing lemma, Exercise 9 from Notes 1). […]
17 December, 2011 at 2:30 am
Введение в теорию экспандеров « sementry blog
[…] английском (Terence Tao, UCLA): https://terrytao.wordpress.com/2011/12/02/245b-notes-1-basic-theory-of-expander-graphs/ На русском (Андрей Ромащенко, CSClub): […]
17 December, 2011 at 5:41 am
Piero Giacomelli (@pierogiacomelli)
thanks for sharing your notes on expanders, apart form the survey of Hoory do you have any other introductory paper to suggest?
17 December, 2011 at 8:20 am
Terence Tao
Some further surveys on expanders can be found at the class web page http://www.math.ucla.edu/~tao/254b.1.12w/
17 December, 2011 at 11:39 am
Jayadev Athreya
Just as a historical note, shouldn’t the name of Margulis be mentioned here?
17 December, 2011 at 12:02 pm
Terence Tao
Margulis’s contributions are discussed in Notes 2: https://terrytao.wordpress.com/2011/12/06/254b-notes-2-cayley-graphs-and-kazhdans-property-t/
18 December, 2011 at 5:39 pm
254B, Notes 1: Basic theory of expander graphs « Another Word For It
[…] 254B, Notes 1: Basic theory of expander graphs […]
11 January, 2012 at 3:17 am
Sean Eberhard
Couple of typos: There seems to be a superfluous
in Proposition 4 (discrete Cheeger) just above equation (3), and a few lines below that you say
is negative when I think you mean positive.
[Corrected, thanks – T.]
19 January, 2012 at 6:51 pm
Nick Cook
So does a Lovasz local lemma turn out not to be the right tool for Proposition 5? Our example didn’t meet the low-dependency hypothesis of the version I tried, but I don’t know if there are stronger variants.
Also some small typos: in the formula in Exercise 9 we should have
. In proofs of Props 5 and 8 should we also include the bad events
? And a few lines under Proposition 8, surely we don’t want to consider
a rare event! :)
19 January, 2012 at 8:14 pm
Terence Tao
Thanks for the corrections! I tried for a while to use the Lovasz local lemma but eventually decided that there wasn’t enough genuine independence in the problem for the lemma (or the various variants of it that I know of) to be applicable. I am still wondering if there is a “non-enumerative” proof of Proposition 5 that does not require so much exact computation; I posed this as a problem on MathOverflow but thus far none of the proposed arguments seems to give this without using at least as much computation as is given in the above post.
27 January, 2012 at 11:15 am
Choongbum Lee
It seems like there is something missing in condition (ii) of Exercise 10; a vertex disjoint union of two copies of k-regular two-sided expanders will satisfy the condition (it is a disconnected graph). Shouldn’t the condition look more similar to something like that given in Exercise 9?
27 January, 2012 at 11:19 am
Terence Tao
If a graph
is a vertex-disjoint union of two subgraphs, one of the two vertex classes, say
, will have cardinality at most
. Setting
and
to both be
, we see that (ii) will fail.
27 January, 2012 at 1:16 pm
Choongbum Lee
Aha! You are right. Thank you very much.
31 January, 2012 at 4:00 pm
Mikhail
1. I would be thankful for more detailed information on Pinsker’s paper of 1973. Have you seen it? Is it possible to download it from somewhere?
Some corrections:
2. “Bardin” should be “Barzdin” (the beginning of Section 4).
3. Before Proposition 5: $\pi_1,\dots,\pi_l$ map $\{1,\dots,n\}$ onto $\{1,\dots,n\}$.
4. Exercise 13: I think that you meant “large girth” rather than “low girth”.
5. End of the proof of Proposition 4: $k$ is lost from the right-hand side of
$$|\partial F|\ge\epsilon|F|/2$$.
6. Exercise 14: It is strange to ask for existence of $M$ since $M$ is your notation for a median.
7. Exercises 15 and 16. Possibly it is better to replace $A$ by another letter since $A$ is your notation for the adjacency matrix.
31 January, 2012 at 4:40 pm
Terence Tao
Thanks for the corrections!
I have unfortunately not been able to find an online link to Pinsker’s paper (M. Pinsker, On the complexity of a concentrator, 7th
Annual Teletraffic Conference (1973), 1-4), and have been forced to rely on secondary sources. If any reader knows of a link to the original paper, it would be greatly appreciated.
31 January, 2012 at 8:13 pm
Anonymous
There you go:
Click to access pinsker731.pdf
31 January, 2012 at 9:11 pm
Terence Tao
Thanks!
21 February, 2012 at 9:42 am
Rex
In Proposition 4 you write:
“Let
be a subset of
with
. We consider the quantity
I believe this formula should read
21 February, 2012 at 9:44 am
Rex
Oops, nevermind. I mistook it for the boundary of F.
25 February, 2012 at 7:33 pm
Abhishek Bhowmick
In the very last step of the proof of Proposition 4 (Cheeger inequality, just before example 2 starts), in the step after you reverse the order of integration of s and t, I think it should be s|F_s|ds instead of just |F_s|ds
[Corrected, thanks – T.]
3 April, 2012 at 5:08 am
Michał Kotowski
Do you know any direct applications of the concentration of measure for expanders? (i.e. results where having tight concentration for such graphs would be an important element of the proof)
3 April, 2012 at 7:13 am
Terence Tao
Well, the fact that expanders have logarithmic diameter is used all over the place, and this can be viewed as a special case of concentration of measure (applied to the distance function from some arbitrary origin). But I don’t know of a place in the literature where concentration of measure is directly used in some application.
10 July, 2012 at 6:38 pm
Anonymous
Terry,
In Remark 1, you say “in the sense that the second eigenvalue of … exceeds the first by at least…”
Shouldn’t it be reversed?
Thanks
[Corrected, thanks – T.]
26 July, 2012 at 6:27 pm
robinson
I’m a little confused by a missing factor of 2 in the proof of Proposition 6, immediately following the words “so that the total probability of failure is…” Now the preceeding sentence has bounded the probability that
sends $\latex F$ to a subset of
, and this probability is raised to the power of k in the ensuing sum. But to generate a k-regular graph, we used
permutations, so it seems to me it should be raised to the power of
; some additional argumentation is necessary to justify raising it to the power of $k$. Is this right or did I miss a key detail?
26 July, 2012 at 6:29 pm
robinson
On second thought, I guess this is glossed over because it makes no difference –
is taken be large enough anyway.
[Corrected anyway – T.]
27 September, 2012 at 2:34 pm
Matthew Kahle
It seems like starting with “Now we turn to the rigorous construction of random expander graphs.” there are several places where it says “$3K$-regular graphs. Should this say “$k$-regular” instead?
5 March, 2013 at 6:19 pm
ajthemathematician
Reblogged this on amathematician.
27 May, 2013 at 6:47 am
254B, Notes 1: Basic theory of expander graphs | What’s new | Peter's ruminations
[…] https://terrytao.wordpress.com/2011/12/02/245b-notes-1-basic-theory-of-expander-graphs/#more-5525 […]
10 September, 2013 at 8:15 am
Expansion in finite simple groups of Lie type | What's new
[…] we show that the distinction between one-sided expansion and two-sided expansion (see this set of lecture notes of mine for definitions) is erased in the context of Cayley graphs of bounded degree, in the sense […]
22 October, 2013 at 11:11 pm
Alexander Shamov
Is there a way of doing Exercise 10 without relying on the harder part of Cheeger’s inequality (or re-proving it)? Or maybe a point of view from which both become easy?
12 March, 2014 at 5:25 pm
Shivkumar Chandrasekaran
In Exercise 7 should it be
, rather than
?
[Corrected, thanks – T.]
1 March, 2015 at 9:55 am
sai
Do you know how to prove question Exercise 12 ??
6 April, 2020 at 1:22 am
ConstantinK
Proof of (i) implies (ii) of Proposition 4: In the last sentence of the proof, I believe you want to replace
by
in the two displayed equations. Moreover, I believe there is also a small argumentative inaccuracy in this last sentence of the proof. Namely, you write that there are
pairs
so that
and
. In fact, you count here ordered pairs
so this double counts the number of edges. Using your definition of
, we thus only can conclude
and not over
.
[Corrected, thanks – T.]
6 April, 2020 at 1:51 am
ConstantinK
The “problem” here is somewhat the definition of
. Namely, with the above definition it holds that $
$ as
double counts the edges, whereas
does not
10 April, 2020 at 6:02 am
ConstantinK
In Exercise 20, all the constants can be chosen to depend only on
and in particular not on
. (I don’t know if you care about this.)
[Fair enough, but given that the various measures of expansion are only equivalent up to constants that depend on
, the independence of the growth constant here on
using this specific measure of expansion
can be slightly misleading – for instance if one wishes to control
in terms of the spectral gap
instead then I think there is now a
-dependence. -T]