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.
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
Hi,
is there any chance of the rest of the notes appearing on this blog anytime soon?
Dear Michal, yes I hope so.