High Dimensional Expanders: Introduction I

Posted on November 12, 2011 by Gil Kalai

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 G be a graph on the vertex set V. G is an \epsilon–expander if for every set U of vertices, |U| \le |V|/2, the number of edges of G containing one vertex from U and one vertex from V \backslash U is at least \epsilon|U|.

The set of edges E_G(U,\bar U) in G from U to its complement are sometimes called the edge-boundary of U. The expansion h(G) of G is defined by

h(G)= \min\{E_G(U,\bar U): U \subset V, U \ne \emptyset, |U| \le |V|/2\}.

1.2 Spectral relation

We will mainly be interested in the case where G is a k-regular graph with n vertices and k is a fixed integer. Let A be the adjecency matrix of G. The largest  eigenvalue of A is k and let \lambda=\lambda_2 be the second largest eigenvalue.

Theorem (Alon-Boppana): \lambda\ge 2\sqrt {k-1}-o_n(1)

Theorem (Tanner, Alon-Milman): h(G)\ge (k-\lambda)/2

Theorem (Alon): h(G) \le \sqrt {2k(k-\lambda)}

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 G 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 K. Then we defined the chain groups C_i(K): i\ge -1 with coefficients in Z/2Z and the cochain groups C^i(K) and we identified between them. Thus an element x in the ith chain or cochain groups can be regarded as a linear combination of i-dimensional faces of K. The support of x, supp(x) is the set of i-faces of K with nonzero coefficient in x.

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

Then we defined the vector spaces – Z^i(K) of i-cocycles, B^i(K) of i-coboundaries and the ith cohomology H^i(K)=Z^i(K)/B^i(K). 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 K be a simplicial complex, define

h_i(K)=\min_y \max _x~\{~{\frac{|supp(y)|}{|supp(x)|}}: y \in B^{i+1}(K),~x\in (C^i(K)\backslash B^i(K)), \delta (x)=y\}

Another way to write the same thing is this:

For x\in C^i(K)\backslash B^i(K) write

h(x)=\min\{|supp(\delta x)|/(|supp(x+\delta z)|: z \in C^{i-1}(K)\}.

Then h_i(K)=\min\{~h(x): x\in C^i(K)\backslash B^i(K)\}.

If K is a d-dimensional complex we will denote h(K)=h_{d-1}(K).

Some remarks:

1) For graphs: When K is a 1-dimensional complex, the cohomological definition of h_0(K) coincides with the combinatorial definition. Every x \in C^{0}(K) is the sum of vertices in a set U \subset V of vertices. \delta (x) is the sum of edges in E(U,\bar U). The formula reduces to h(G)=\min |E(U,\bar U)/(\min |U|, |V|-|U|) over all nonempty proper subsets U of V.

2) h_i(K)=0 if and only if H_i(K)\ne 0.

3.2 Spectral definition

In this little sections we move to chain and cochain groups with real coefficients. Define the Laplacian L_i(K): C^i(K)\to C^i(K) by

L_i = \delta \partial +\partial\delta.

Let \lambda^i(K) to be the minimal eigenvalue of L_i(K).

We will say that a d-dimensional space is an i-expander in the spectral sense, if \lambda^{i}(K) is large. As before we are mainly interested in the case where i=\dim (K)-1.

3.3 Geometric and topological definitions.

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

The overlap number w.r.t. \phi and a point x \in R^d, denoted by overlap(K,\phi,x) is the number of d dimensional faces in K whose image under \phi contains x. The overlap number of K is defined as

overlap(K) = \min_{\phi} \max_{x \in R^d} overlap (K,\phi,x).

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

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.

This entry was posted in Combinatorics, Teaching and tagged . Bookmark the permalink.

5 Responses to High Dimensional Expanders: Introduction I

  1. Joseph Malkevitch says:
    November 15, 2011 at 6:29 pm

    For a nice account of connections between some of these ideas look at: math.mit.edu/~fox/MAT307-lecture22.pdf

    Reply

  2. Pingback: Weekly Picks « Mathblogging.org — the Blog

  3. Michał Kotowski says:
    December 10, 2011 at 4:45 am

    Hi,
    is there any chance of the rest of the notes appearing on this blog anytime soon?

    Reply

  4. Pingback: A High-Dimensional Diameter Problems for Polytopes | Combinatorics and more

Leave a reply to Gil Kalai Cancel reply