You are currently browsing the tag archive for the ‘Expanders’ tag.

# Tag Archive

## The expansion of the Payley graph

September 10, 2014 in Expanders, math, theory | Tags: Expanders | 1 comment

Suppose that we want to construct a very good family of -regular expander graphs. The Alon-Boppana theorem says that the best we can hope for, from the point of view of spectral expansion, is to have , and we would certainly be very happy with a family of graphs in which .

Known constructions of expanders produce Cayley graphs (or sometimes Schreier graphs, which is a related notion), because it is easier to analyze the spectra of such graphs. If is a group with operation and is the inverse of element , and is a symmetric set of generators, then the Cayley graph is the graph whose vertices are the elements of and whose edges are the pairs such that .

When the group is Abelian, there is good news and bad news. The good news is that the eigenvectors of the graphs are completely characterized (they are the characters of ) and the eigenvalues are given by a nice formula. (See here and here.) The bad news is that constant-degree Cayley graphs of Abelian groups cannot be expanders.

That’s very bad news, but it is still possible to get highly expanding graphs of polylogarithmic degree as Cayley graphs of Abelian groups.

Here we will look at the extreme case of a family of graphs of degree , where is the number of vertices. Even with such high degree, the weak version of the Alon-Boppana theorem still implies that we must have , and so we will be happy if we get a graph in which . Highly expanding graphs of degree are interesting because they have some of the properties of random graphs from the distribution. In turn, graphs from have all kind of interesting properties with high probabilities, including being essentially the best known *Ramsey graphs* and having the kind of *discrepancy* property that gives *seedless extractors for two independent sources.* Unfortunately, these properties cannot be certified by spectral methods. The graph that we will study today is believed to have such stronger properties, but there is no known promising approach to prove such conjectures, so we will content ourselves with proving strong spectral expansion.

The graph is the Payely graph. If is a prime, is the group of addition modulo , and is the set of elements of of the form , then the graph is just . That is, the graph has a vertex for each , and two vertices are adjacent if and only if there is an such that .

## The Alon-Boppana Theorem

September 1, 2014 in Expanders, math | Tags: Boppana, Expanders, Joel Friedman, Noga Alon, trace method | 4 comments

Let be a -regular graph, and let

be the eigenvalues of the adjacency matrix of counted with multiplicities and sorted in descending order.

How good can the spectral expansion of be?

**1. Simple Bounds **

The simplest bound comes from a trace method. We have

by using one definition of the trace and

using the other definition and observing that counts the paths that go from to in two steps, of which there are at least : follow an edge to a neighbor of , then follow the same edge back. (There could be more if has multiple edges or self-loops.)

So we have

and so

The condition is necessary to get lower bounds of ; in the clique, for example, we have and .

A trace argument does not give us a lower bound on , and in fact it is possible to have and , for example in the bipartite complete graph.

If the diameter of is at least 4, it is easy to see that . Let be two vertices at distance 4. Define a vector as follows: , if is a neighbor of , and if is a neighbor of . Note that there cannot be any edge between a neighbor of and a neighbor of . Then we see that , that (because there are edges, each counted twice, that give a contribution of to ) and that is orthogonal to .

**2. Nilli’s Proof of the Alon-Boppana Theorem **

Nilli’s proof of the Alon-Boppana theorem gives

where is the diameter of . This means that if one has a family of (constant) degree- graphs, and every graph in the family satisfies , then one must have . This is why families of *Ramanujan* graphs, in which , are special, and so hard to construct, or even to prove existence of.

Friedman proves a stronger bound, in which the error term goes down with the square of the diameter. Friedman’s proof is the one presented in the Hoory-Linial-Wigderson survey. I like Nilli’s proof, even if it is a bit messier than Friedman’s, because it starts off with something that *clearly* is going to work, but the first two or three ways you try to establish the bound don’t work (believe me, I tried, because I didn’t see why some steps in the proof had to be that way), but eventually you find the right way to break up the estimate and it works.

So here is Nilli’s proof. Read the rest of this entry »

## The Expander Mixing Lemma in Irregular Graphs

August 26, 2014 in math, theory | Tags: expander mixing lemma, Expanders | Leave a comment

Today, after a lecture in the spectral graph theory boot camp at the Simons institute, I was asked what the *expander mixing lemma* is like in graphs that are not regular.

I don’t know if I will have time to return to this tomorrow, so here is a quick answer.

First, for context, the expander mixing lemma in regular graph. Say that is a -regular undirected graph, and is its adjacency matrix. Then let the eigenvalues of the normalized matrix be

We are interested in graphs for which all the eigenvalues are small in absolute value, except , that is, if we define

we are interested in graphs for which is small. The expander mixing lemma is the fact that for every two disjoint sets and of vertices we have

The inequality (1) says that, if is small, then the number of edges between every two large sets of vertices is almost determined just by the size of the sets, and it is equal to the expected number of edges between the two sets in a random -regular graph, up to an error term that depends on .

For the proof, we observe that, if we call the matrix that has ones everywhere, then

and then we substitute and in the above expression and do the calculations.

In the case of an irregular undirected graph , we are going to consider the normalized adjacency matrix , where is the adjacency matrix of and is the diagonal matrix such that , where is the degree of . As in the regular case, the eigenvalues of the normalized adjacency matrix satisfy

Let us define

the second largest eigenvalue in absolute value of .

We will need two more definitions: for a set of vertices , its volume is defined as

the sum of the degrees and the average degree, so that . Now we have

Lemma 1 (Expander Mixing Lemma)For every two disjoint sets of vertices , , we have

So, once again, we have that the number of edges between and is what one would expect in a random graph in which the edge exists with probability , up to an error that depends on .

## The spectrum of the infinite tree

August 20, 2014 in math, theory | Tags: Expanders, infinite tree, Joel Friedman, spectral norm | 2 comments

The spectral norm of the infinite -regular tree is . We will see what this means and how to prove it.

When talking about the expansion of random graphs, abobut the construction of Ramanujan expanders, as well as about sparsifiers, community detection, and several other problems, the number comes up often, where is the degree of the graph, for reasons that tend to be related to properties of the infinite -regular tree.

## The Riemann hypothesis for graphs

August 18, 2014 in math | Tags: Expanders, Riemann Hypothesis | 4 comments

A regular connected graph is Ramanujan if and only if its Ihara zeta function satisfies a Riemann hypothesis.

The purpose of this post is to explain all the words in the previous sentence, and to show the proof, except for the major step of proving a certain identity.

There are at least a couple of reasons why more computer scientists should know about this result. One is that it is nice to see a connection, even if just at a syntactic level, between analytic facts that imply that the primes are pseudorandom and analytic facts that imply that good expanders are pseudorandom (the connection is deeper in the case of the Ramanujan Cayley graphs constructed by Lubotzky, Phillips and Sarnak). The other is that the argument looks at eigenvalues of the adjacency matrix of a graph as roots of a characteristic polynomial, a view that is usually not very helpful in achieving quantitative result, with the important exception of the work of Marcus, Spielman and Srivastava on interlacing polynomials.

## applications of the notion of non-expanding sets in undirected graphs

May 19, 2014 in math, theory | Tags: Expanders | 2 comments

Where you least expect them:

a common [definiton] for “population” is a geographical cluster of people who mate more within the cluster than outside of it

## The Cheeger inequality in manifolds

March 20, 2013 in math, theory | Tags: Cheeger inequality, Expanders, Laplacian, manifolds, spectral graph theory | 1 comment

Readers of *in theory* have heard about Cheeger’s inequality a lot. It is a relation between the edge expansion (or, in graphs that are not regular, the conductance) of a graph and the second smallest eigenvalue of its Laplacian (a normalized version of the adjacency matrix). The inequality gives a worst-case analysis of the “sweep” algorithm for finding sparse cuts, it shows a necessary and sufficient for a graph to be an expander, and it relates the mixing time of a graph to its conductance.

Readers who have heard this story before will recall that a version of this result for vertex expansion was first proved by Alon and Milman, and the result for edge expansion appeared in a paper of Dodzuik, all from the mid-1980s. The result, however, is not called *Cheeger’s inequality* just because of Stigler’s rule: Cheeger proved in the 1970s a very related result on manifolds, of which the result on graphs is the discrete analog.

So, what is the *actual* Cheeger’s inequality?

Theorem 1 (Cheeger’s inequality)Let be an -dimensional smooth, compact, Riemann manifold without boundary with metric , let be the Laplace-Beltrami operator on , let be the eigenvalues of , and define theCheeger constantof to bewhere the is the boundary of , is the -dimensional measure, and is -th dimensional measure defined using . Then

The purpose of this post is to describe to the reader who knows nothing about differential geometry and who does not remember much multivariate calculus (that is, the reader who is in the position I was in a few weeks ago) what the above statement means, to describe the proof, and to see that it is in fact the *same proof* as the proof of the statement about graphs.

In this post we will define the terms appearing in the above theorem, and see their relation with analogous notions in graphs. In the next post we will see the proof.

## Hello, and Welcome to Fun with Expanders

March 8, 2013 in CS366, math, theory | Tags: ExpanderCourse, Expanders, random walks, spectral graph theory | 6 comments

Long in the planning, my online course on graph partitioning algorithms, expanders, and random walks, will start next month.

The course page is up for people to sign up. A friend of mine has compared my camera presence to Sheldon Cooper’s in “Fun with Flags,” which is sadly apt, but hopefully the material will speak for itself.

Meanwhile, I will be posting about some material that I have finally understood for the first time: the analysis of the Arora-Rao-Vazirani approximation algorithm, the Cheeger inequality in manifolds, and the use of the Selberg “3/16 theorem” to analyze expander constructions.

If you are not a fan of recorded performances, there will be a live show in Princeton at the end of June.

## Holiday Readings

December 16, 2011 in math, theory | Tags: Expanders, matrix multiplication, Ryan O'Donnell, Terence Tao, things that are excellent | 16 comments

Now that the Winter break is coming, what to read in between decorating, cooking, eating, drinking and being merry?

The most exciting theoretical computer science development of the year was the improved efficiency of matrix multiplication by Stother and Vassilevska-Williams. Virginia’s 72-page write-up will certainly keep many people occupied.

Terence Tao is teaching a class on expanders, and posting the lecture notes, of exceptional high quality. It is hard to imagine something that would a more awesome combination, to me, than Terry Tao writing about expanders. Maybe a biopic on Turing’s life, starring Joseph Gordon-Levitt, written by Dustin Lance Black and directed by Clint Eastwood.

Meanwhile, Ryan O’Donnell has been writing a book on analysis of boolean function, by “serializing” it on a blog platform.

Now that I have done my part, you do yours. If I wanted to read a couple of books (no math, no theory) during the winter, what would you recommend. Don’t recommend what you think I would like, recommend what you like best, and why.

## CS359G Lecture 18: Properties of Expanders

March 16, 2011 in CS359G | Tags: Chernoff bounds, Expanders, random walks | 3 comments

*In which we prove properties of expander graphs.*

## Recent Comments