The n-Category Café

For example, starting from this graph:

we get this:

Nature uses this pattern for crystals of graphene.

Starting from this graph:

we get this:

Nature uses this for crystals of diamond! Since the construction depends only on the topology of the graph we start with, we call this embedded copy of its maximal abelian cover a topological crystal.

Today I’ll remind you how this construction works. I’ll also outline a proof that it gives an embedding of the maximal abelian cover if and only if the graph has no bridges: that is, edges that disconnect the graph when removed. I’ll skip all the hard steps of the proof, but they can all be found here:

• John Baez, Topological crystals.

The homology of graphs

I’ll start with some standard stuff that’s good to know. Let $X$ be a graph. Remember from last time that we’re working in a setup where every edge $e$ goes from a vertex called its source $s(e)$ to a vertex called its target $t(e)$. We write $e: x \to y$ to indicate that $e$ is going from $x$ to $y$. You can think of the edge as having an arrow on it, and if you turn the arrow around you get the inverse edge, $e^{-1}: y \to x$. Also, $e^{-1} \ne e$.

The group of integral 0-chains on $X$, $C_0(X,\mathbb{Z})$, is the free abelian group on the set of vertices of $X$. The group of integral 1-chains on $X$, $C_1(X,\mathbb{Z})$, is the quotient of the free abelian group on the set of edges of $X$ by relations $e^{-1} = -e$ for every edge $e$. The boundary map is the homomorphism

$$\partial : C_1(X,\mathbb{Z}) \to C_0(X,\mathbb{Z})$$

such that

$$\partial e = t(e) - s(e)$$

for each edge $e$, and

$$Z_1(X,\mathbb{Z}) = \ker \partial$$

is the group of integral 1-cycles on $X$.

Remember, a path in a graph is a sequence of edges, the target of each one being the source of the next. Any path $\gamma = e_1 \cdots e_n$ in $X$ determines an integral 1-chain:

$$c_\gamma = e_1 + \cdots + e_n$$

For any path $\gamma$ we have

$$c_{\gamma^{-1}} = -c_{\gamma},$$

and if $\gamma$ and $\delta$ are composable then

$$c_{\gamma \delta} = c_\gamma + c_\delta$$

Last time I explained what it means for two paths to be ‘homologous’. Here’s the quick way to say it. There’s groupoid called the fundamental groupoid of $X$, where the objects are the vertices of $X$ and the morphisms are freely generated by the edges except for relations saying that the inverse of $e: x \to y$ really is $e^{-1}: y \to x$. We can abelianize the fundamental groupoid by imposing relations saying that $\gamma \delta = \delta \gamma$ whenever this equation makes sense. Each path $\gamma : x \to y$ gives a morphism which I’ll call $[[\gamma]] : x \to y$ in the abelianized fundamental groupoid. We say two paths $\gamma, \gamma' : x \to y$ are homologous if $[[\gamma]] = [[\gamma']]$.

Here’s a nice thing:

Lemma A. Let $X$ be a graph. Two paths $\gamma, \delta : x \to y$ in $X$ are homologous if and only if they give the same 1-chain: $c_\gamma = c_\delta$.

Proof. See the paper. You could say they give ‘homologous’ 1-chains, too, but for graphs that’s the same as being equal.   █

We define vector spaces of 0-chains and 1-chains by

$$C_0(X,\mathbb{R}) = C_0(X,\mathbb{Z}) \otimes \mathbb{R}, \qquad C_1(X,\mathbb{R}) = C_1(X,\mathbb{Z}) \otimes \mathbb{R},$$

respectively. We extend the boundary map to a linear map

$$\partial : C_1(X,\mathbb{R}) \to C_0(X,\mathbb{R})$$

We let $Z_1(X,\mathbb{R})$ be the kernel of this linear map, or equivalently,

$$Z_1(X,\mathbb{R}) = Z_0(X,\mathbb{Z}) \otimes \mathbb{R} ,$$

and we call elements of this vector space 1-cycles. Since $Z_1(X,\mathbb{Z})$ is a free abelian group, it forms a lattice in the space of 1-cycles. Any edge of $X$ can be seen as a 1-chain, and there is a unique inner product on $C_1(X,\mathbb{R})$ such that edges form an orthonormal basis (with each edge $e^{-1}$ counting as the negative of $e$.) There is thus an orthogonal projection

$$\pi : C_1(X,\mathbb{R}) \to Z_1(X,\mathbb{R}) .$$

This is the key to building topological crystals!

The embedding of atoms

We now come to the main construction, first introduced by Kotani and Sunada. To build a topological crystal, we start with a connected graph $X$ with a chosen basepoint $x_0$. We define an atom to be a homology class of paths starting at the basepoint, like

$$[[\alpha]] : x_0 \to x$$

Last time I showed that these atoms are the vertices of the maximal abelian cover of $X$. Now let’s embed these atoms in a vector space!

Definition. Let $X$ be a connected graph with a chosen basepoint. Let $A$ be its set of atoms. Define the map

$$i : A \to Z_1(X,\mathbb{R})$$

by

$$i([[ \alpha ]]) = \pi(c_\alpha) .$$

That $i$ is well-defined follows from Lemma A. The interesting part is this:

Theorem A. The following are equivalent:

• The graph $X$ has no bridges.
• The map $i : A \to Z_1(X,\mathbb{R})$ is one-to-one.

Proof. The map $i$ is one-to-one if and only if for any atoms $[[ \alpha ]]$ and $[[ \beta ]]$, $i([[ \alpha ]]) = i([[ \beta ]])$ implies $[[ \alpha ]]= [[ \beta ]]$. Note that $\gamma = \beta^{-1} \alpha$ is a path in $X$ with $c_\gamma = c_{\alpha} - c_\beta$, so

$$\pi(c_\gamma) = \pi(c_{\alpha} - c_\beta) = i([[ \alpha ]]) - i([[ \beta ]]) .$$

Since $\pi(c_\gamma)$ vanishes if and only if $c_\gamma$ is orthogonal to every 1-cycle, we have

$$c_{\gamma} \; is \; orthogonal \; to \; every \; 1-cycle \; \iff \; i([[ \alpha ]]) = i([[ \beta ]]) .$$

On the other hand, Lemma A says

$$c_\gamma = 0 \; \iff \; [[ \alpha ]]= [[ \beta ]].$$

Thus, to prove (1)$\iff$(2), it suffices to that show that $X$ has no bridges if and only if every 1-chain $c_\gamma$ orthogonal to every 1-cycle has $c_\gamma =0$. This is Lemma D below.   █

The following lemmas are the key to the theorem above — and also a deeper one saying that if $X$ has no bridges, we can extend $i : A \to Z_1(X,\mathbb{R})$ to an embedding of the whole maximal abelian cover of $X$.

For now, we just need to show that any nonzero 1-chain coming from a path in a bridgeless graph has nonzero inner product with some 1-cycle. The following lemmas, inspired by an idea of Ilya Bogdanov, yield an algorithm for actually constructing such a 1-cycle. This 1-cycle also has other desirable properties, which will come in handy later.

To state these, let a simple path be one in which each vertex appears at most once. Let a simple loop be a loop $\gamma : x \to x$ in which each vertex except $x$ appears at most once, while $x$ appears exactly twice, as the starting point and ending point. Let the support of a 1-chain $c$, denoted $\supp(c)$, be the set of edges $e$ such that $\langle c, e\rangle > 0$. This excludes edges with $\langle c, e \rangle= 0$, but also those with $\langle c , e \rangle < 0$, which are inverses of edges in the support. Note that

$$c = \sum_{e \in \supp(c)} \langle c, e \rangle .$$

So, $\supp(c)$ is the smallest set of edges such that $c$ can be written as a positive linear combination of edges in this set.

Okay, here are the lemmas!

Lemma B. Let $X$ be any graph and let $c$ be an integral 1-cycle on $X$. Then for some $n$ we can write

$$c = c_{\sigma_1} + \cdots + c_{\sigma_n}$$

where $\sigma_i$ are simple loops with $\supp(c_{\sigma_i}) \subseteq \supp(c)$.

Proof. See the paper. The proof is an algorithm that builds a simple loop $\sigma_1$ with $\supp(c_{\sigma_1}) \subseteq \supp(c)$. We subtract this from $c$, and if the result isn’t zero we repeat the algorithm, continuing to subtract off 1-cycles $c_{\sigma_i}$ until there’s nothing left.   █

Lemma C. Let $\gamma: x \to y$ be a path in a graph $X$. Then for some $n \ge 0$ we can write

$$c_\gamma = c_\delta + c_{\sigma_1} + \cdots + c_{\sigma_n}$$

where $\delta: x \to y$ is a simple path and $\sigma_i$ are simple loops with $\supp(c_\delta), \supp(c_{\sigma_i}) \subseteq \supp(c_\gamma)$.

Proof. This relies on the previous lemma, and the proof is similar — but when we can’t subtract off any more $c_{\sigma_i}$’s we show what’s left is $c_\delta$ for a simple path $\delta: x \to y$.   █

Lemma D. Let $X$ be a graph. Then the following are equivalent:

• $X$ has no bridges.
• For any path $\gamma$ in $X$, if $c_\gamma$ is orthogonal to every 1-cycle then $c_\gamma = 0$.

Proof. It’s easy to show a bridge $e$ gives a nonzero 1-chain $c_e$ that’s orthogonal to all 1-cycles, so the hard part is showing that for a bridgeless graph, if $c_\gamma$ is orthogonal to every 1-cycle then $c_\gamma = 0$. The idea is to start with a path for which $c_\gamma \ne 0$. We hit this path with Lemma C, which lets us replace $\gamma$ by a simple path $\delta$. The point is that a simple path is a lot easier to deal with than a general path: a general path could wind around crazily, passing over every edge of our graph multiple times.

Then, assuming $X$ has no bridges, we use Ilya Bogdanov’s idea to build a 1-cycle that’s not orthogonal to $c_\delta$. The basic idea is to take the path $\delta : x \to y$ and write it out as $\delta = e_1 \cdots e_n$. Since the last edge $e_n$ is not a bridge, there must be a path from $y$ back to $x$ that does not use the edge $latex e_n$ or its inverse. Combining this path with $\delta$ we can construct a loop which gives a cycle having nonzero inner product with $c_\delta$ and thus with $c_\gamma$.

I’m deliberately glossing over some difficulties that can arise, so see the paper for details!   █

Embedding the whole crystal

Okay: so far, we’ve taken a connected bridgeless graph $X$ and embedded its atoms into the space of 1-cycles via a map

$$i : A \to Z_1(X,\mathbb{R}) .$$

These atoms are the vertices of the maximal abelian cover $\overline{X}$. Now we’ll extend $i$ to an embedding of the whole graph $\overline{X}$ — or to be precise, its geometric realization $|\overline{X}|$. Remember, for us a graph is an abstract combinatorial gadget; its geometric realization is a topological space where the edges become closed intervals.

The idea is that just as $i$ maps each atom to a point in the vector space $Z_1(X,\mathbb{R})$, $j$ maps each edge of $|\overline{X}|$ to a straight line segment between such points. These line segments serve as the ‘bonds’ of a topological crystal. The only challenge is to show that these bonds do not cross each other.

Theorem B. If $X$ is a connected graph with basepoint, the map $i : A \to Z_1(X,\mathbb{R})$ extends to a continuous map

$$j : |\overline{X}| \to Z_1(X,\mathbb{R})$$

sending each edge of $|\overline{X}|$ to a straight line segment in $Z_1(X,\mathbb{R})$. If $X$ has no bridges, then $j$ is one-to-one.

Proof. The first part is easy; the second part takes real work! The problem is to show the edges don’t cross. Greg Egan and I couldn’t do it using just Lemma D above. However, there’s a nice argument that goes back and uses Lemma C — read the paper for details.

As usual, history is different than what you read in math papers: David Speyer gave us a nice proof of Lemma D, and that was good enough to prove that atoms are mapped into the space of 1-cycles in a one-to-one way, but we only came up with Lemma C after weeks of struggling to prove the edges don’t cross.   █

Connections to tropical geometry

Tropical geometry sets up a nice analogy between Riemann surfaces and graphs. The Abel–Jacobi map embeds any Riemann surface $\Sigma$ in its Jacobian, which is the torus $H_1(\Sigma,\mathbb{R})/H_1(\Sigma,\mathbb{Z})$. We can similarly define the Jacobian of a graph $X$ to be $H_1(X,\mathbb{R})/H_1(X,\mathbb{Z})$. Theorem B yields a way to embed a graph, or more precisely its geometric realization $|X|$, into its Jacobian. This is the analogue, for graphs, of the Abel–Jacobi map.

After I put this paper on the arXiv, I got an email from Matt Baker saying that he had already proved Theorem A — or to be precise, something that’s clearly equivalent. It’s Theorem 1.8 here:

• Matthew Baker and Serguei Norine, Riemann–Roch and Abel–Jacobi theory on a finite graph.

This says that the vertices of a bridgeless graph $X$ are embedded in its Jacobian by means of the graph-theoretic analogue of the Abel–Jacobi map.

What I really want to know is whether someone’s written up a proof that this map embeds the whole graph, not just its vertices, into its Jacobian in a one-to-one way. That would imply Theorem B. For more on this, try my conversation with David Speyer.

Anyway, there’s a nice connection between topological crystallography and tropical geometry, and not enough communication between the two communities. Once I figure out what the tropical folks have proved, I will revise my paper to take that into account.

Next time I’ll talk about more examples of topological crystals!