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 one-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).
50 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,
so that all balls in all the ‘s are uniform expanders?
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
the ball B(v,r) is h- expander, expander with a uniform expansion constant h.
Note e.g. that if 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).
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]
8 February, 2023 at 11:45 am
Mohammed Mannan
For Exercise 19, I believe we need a stronger form of the mixing lemma closer to the statement in Exercise 18 to show equivalence of (i) and (ii). This is for the following reason: In exercise 18, if we only have one-sided expansion, we can prove the inequality without the absolute value. Thus E(F_1,F_2) <= (1-epsilon)k*root(F_1 F_2)root(1-F_1/n)root(1-F_2/n) + (k/n)|F_1||F_2| <= k((1/2) + (1-epsilon)/2)root(F_1 F_2). (The second inequality holds when |F_1|, |F_2| <= n/2 = |V|/2. As is currently stated in Exercise 19, we can prove equivalence if "two-sided" is replaced with "one-sided". The converse to expander mixing proven by Bilu and Linial in their 2006 paper "Lifts, discrepancy, and nearly optimal spectral gap" uses the stronger statement of the expander mixing lemma as in exercise 18.
[“two-sided” replaced with “one-sided” in Exercise 19 – T.]
8 February, 2023 at 2:29 pm
Mohammed Mannan
For exercise 20, the inequality |B(v,r)| >= min( (1+c)^r, n/2) is straightforward induction, using estimates for the lower bound of the size of the boundary of the ball depending on the interior when the size of the ball is less than or equal to n/2. I am not sure how to sharpen this to min( (1+c)^r, n). If s is the greatest such that |B(v,s)| <= n/2, then one can show that B(v,s+t)^complement = n – C n exp(-ct) but I’m not sure if we can proceed by bounding n- C n exp(-ct) from below by (n/2)*(1 + c’)^t >= (1 + c’)^(s + t).
[If two balls both have cardinality greater than , then they intersect, hence lies in . -T]
8 February, 2023 at 3:00 pm
Mohammed Mannan
If we have a sharp bound |B(v,r)| >= min( (1+c)^r, |V(G)|), I believe if there is an epsilon-expander family G_n with vertex size going to infinity, and v_n, w_n in V(G_n) are such that d(v_n, w_n) = diam(G_n), then the number of points a distance diam(G_n) from v_n must also go to infinity. So an epsilon-expander family contradicting the previous sentence would contradict the sharp bound. If we did not require k-regular and instead required degree-bounded-by-k for our definition of expander graph, it seems like we should be able to construct such a contradictory family, so to prove a sharp bound k regularity would be crucial.