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 $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 $i$ th 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 $i$ th 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 $i$ th 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.

About these ads

4 Responses to High Dimensional Expanders: Introduction I

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

Pingback: Weekly Picks « Mathblogging.org — the Blog
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?

- Gil Kalai says:
  
  December 12, 2011 at 12:43 am
  
  Dear Michal, yes I hope so.

	Gil Kalai on זה הזמן לשינוי
	Yiftach on זה הזמן לשינוי
	Gil Kalai on זה הזמן לשינוי
	Yiftach on זה הזמן לשינוי
	Gil Kalai on זה הזמן לשינוי
	קוסמופוליט on זה הזמן לשינוי
	Gil Kalai on זה הזמן לשינוי
	Eli_B on זה הזמן לשינוי
	Michael Elkin on זה הזמן לשינוי
	Gil Kalai on זה הזמן לשינוי
	Eli_B on זה הזמן לשינוי
	Gil Kalai on זה הזמן לשינוי

High Dimensional Expanders: Introduction I

A brief introduction.