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

# Tag Archive

## The spectrum of the infinite tree

August 20, 2014 in math, theory | Tags: Expanders, infinite tree, Joel Friedman, spectral norm | Leave a comment

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 | 3 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.*

## CS359G Lecture 17: The Zig-Zag Product

March 7, 2011 in CS359G | Tags: Expanders, zig-zag product | 1 comment

*In which we define and analyze the zig-zag graph product.*

## CS359G Lecture 16: Constructions of Expanders

February 28, 2011 in CS359G | Tags: Expanders, zig-zag product | 2 comments

*In which we give an explicit construction of expander graphs of polylogarithmic degree, state the properties of the **zig-zag product* of graphs, and provide an explicit construction of a family of constant-degree expanders using the zig-zag product and the polylogarithmic-degree construction.

A *family of expanders* is a family of graphs , , such that each graph is -regular, and the edge-expansion of each graph is at least , for an absolute constant independent of . Ideally, we would like to have such a construction for each , although it is usually enough for most applications that, for some constant and every , there is an for which the construction applies in the interval , or even the interval . We would also like the degree to be slowly growing in and, ideally, to be bounded above by an explicit constant. Today we will see a simple construction in which and a more complicated one in which .

An *explicit construction* of a family of expanders is a construction in which is “efficiently computable” given . The weakest sense in which a construction is said to be explicit is when, given , the (adjacency matrix of the) graph can be constructed in time polynomial in . A stronger requirement, which is necessary for several applications, is that given and , the list of neighbors of the -th vertex of can be computed in time polynomial in .

In many explicit constructions of constant-degree expanders, the construction is extremely simple, and besides satisfying the stricter definition of “explicit” above, it is also such that the adjacency list of a vertex is given by a “closed-form formula.” The analysis of such constructions, however, usually requires very sophisticated mathematical tools.

Example 1Let be a prime, and define the graph in which , and, for , the vertex is connected to , to and to its multiplicative inverse . The vertex is connected to , to , and has a self-loop. Counting self-loops, the graph is 3-regular: it is the union of a cycle over and of a matching over the vertices ; the vertices , , have a self-loop each. There is a constant such that, for each , the graph has edge expansion at least . Unfortunately, no elementary proof of this fact is known. The graph is shown in the picture below.

Constructions based on the *zig-zag graph product*, which we shall see next, are more complicated to describe, but much simpler to analyze.

We begin by describing a building block in the construction, which is also an independently interesting construction: a family of expanders with polylogarithmic degree, which have both a very simple description and a very simple analysis.

## CS359G Lecture 3: Cheeger’s inequality

January 19, 2011 in CS359G | Tags: Cheeger inequality, Expanders | 4 comments

*In which we prove the easy case of Cheeger’s inequality.*

**1. Expansion and The Second Eigenvalue **

Let be an undirected -regular graph, its adjacency matrix, its normalized adjacency matrix, and be the eigenvalues of .

Recall that we defined the *edge expansion* of a cut of the vertices of as

and that the edge expansion of is .

We also defined the related notion of the *sparsity* of a cut as

and ; the *sparsest cut* problem is to find a cut of minimal sparsity.

Recall also that in the last lecture we proved that if and only if is disconnected. This is equivalent to saying that if and only if . In this lecture and the next we will see that this statement admits an *approximate version* that, qualitatively, says that is small if and only if is small. Quantitatively, we have

Theorem 1 (Cheeger’s Inequalities)

## Recent Comments