High Dimensional Expanders: Introduction I

Alex Lubotzky and I  are running together a year long course at HU on High Dimensional Expanders. High dimensional expanders are simplical (and more general) cell complexes which generalize expander graphs. The course is taking place in Room 110 of the mathematics building on Tuesdays 10-12. The first four hours were devoted to an introduction to the course that came with a disclaimer that some of the material is new to us as well, with a promise that the course will occasionally turn into a seminar featuring interesting speakers, and with a hope that perhaps we will be able to discover while running the course interesting questions to answer or ask. It will be too difficult for me  to follow the entire course over the blog but I would like to devote two posts to the Introduction with some remarks and backgrounds.

A brief introduction.

The introduction included the following four  parts.

Introduction to Expanders: Alex briefly described the definition of expanders, their spectral properties, the relation with random walks, the construction of expanders, the construction of Ramanujan graphs, one brief application.

Introduction to high dimensional complexes: I briefly described higher dimensional topological objects and mainly simplicial complexes, and the notions of homology and cohomology.

Introduction to high dimensional expanders: I briefly went over several possible (not equivalent) definitions: Cohomological definition; geometric and topological definitions; spectral definition;

Ramanujan graphs and complexes: Alex briefly described what they are.

In this post we will go over the first three items.  The next post will discuss the fourth item, provide credits, references and links,  and also discuss examples, connections, potential applications, and questions.

Introduction

1. Expander graphs

1.1 The definition

Let be a graph on the vertex set . is an –expander if for every set of vertices, , the number of edges of  containing one vertex from and one vertex from is at least .

The set of edges in from to its complement are sometimes called the edge-boundary of . The expansion of is defined by

.

1.2 Spectral relation

We will mainly be interested in the case where is a -regular graph with vertices and is a fixed integer. Let be the adjecency matrix of . The largest  eigenvalue of is and let be the second largest eigenvalue. 

Theorem (Alon-Boppana):

Theorem (Tanner, Alon-Milman):

Theorem (Alon):

1.3 Random walks

For regular graphs, the expansion property (through the spectral interpretation) implies that (unless the graph is bipartite) the simple random walk on the graph converges quickly to the uniform distribution on the vertices.

We will come back to examples of expander graph and to a certain application after defining high dimensional expansion.

2. High dimensional complexes and homology

We defined abstract simplicial complexes and geometric simplicial complexes . Then we defined the chain groups with coefficients in and the cochain groups and we identified between them. Thus an element in the th chain or cochain groups can be regarded as a linear combination of -dimensional faces of . The support of , is the set of -faces of with nonzero coefficient in .

We described the boundary and coboundary operations.  Briefly, if is the chain that correspond to an -face , then , the boundary operation,  is the sum of all faces of . This definition is extended by linearity to every -chain. When we think about above as an element in the th cochain group then is the sum (modulo 2) of all -faces of containing .  

Then we defined the vector spaces –  of -cocycles, of -coboundaries and the th cohomology . We also defined boundaries, cycles and homology.  

Everything we said apply to homology with other fields of coefficients except that it was easier to define the boundary/coboundary operations over Z/2Z (for other fields of coefficients we need to worry about signs). We always consider reduced homology/cohomology without saying it.

3. High dimensional expanders

We mention several different (nonequivalent) notions of high dimensional expansions. 

3.1 (co)Homological definition:

Let be a simplicial complex, define

Another way to write the same thing is this:

For write

Then .

If is a -dimensional complex we will denote .

Some remarks:

1) For graphs: When is a 1-dimensional complex, the cohomological definition of coincides with the combinatorial definition. Every is the sum of vertices in a set of vertices. is the sum of edges in . The formula reduces to over all nonempty proper subsets of .

2) if and only if .

3.2 Spectral definition

In this little sections we move to chain and cochain groups with real coefficients. Define the Laplacian by

.

Let to be the minimal eigenvalue of .

We will say that a -dimensional space is an -expander in the spectral sense, if is large. As before we are mainly interested in the case where . 

3.3 Geometric and topological definitions.

Let be a -dimensional simplicial complex. Let be an embedding of the vertices of to . Given a -dimensional face of we denote by the convex hull of the images under of the vertices of $F$.  (Alternatively we can think about as a geometric simplicial complex and about as a mao to which is an affine map on the faces of .)

The overlap number w.r.t. and a point , denoted by is the number of dimensional faces in whose image under contains . The overlap number of is defined as

.

The topological overlap number of is defined the same except that you allow to be a continuous function from (regarded as a geometric simplicial complex) into .

Note that for graphs, large expansion implies large overlap number.

Next post: Examples, relations between the various definitions, basic research questions. Ramanujan graphs and complexes. Applications: error correcting codes, qantum codes.  More remarks, credits and and links to relevant papers.

Advertisements