Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

August 6, 2016

Topological Crystals (Part 3)

Posted by John Baez

Last time I explained how to build the ‘maximal abelian cover’ of a connected graph. Now I’ll say more about a systematic procedure for embedding this into a vector space. That will give us a topological crystal, like this:


Some remarkably symmetrical patterns arise this way!

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:

The homology of graphs

I’ll start with some standard stuff that’s good to know. Let XX be a graph. Remember from last time that we’re working in a setup where every edge ee goes from a vertex called its source s(e)s(e) to a vertex called its target t(e)t(e). We write e:xye: x \to y to indicate that ee is going from xx to yy. 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:yxe^{-1}: y \to x. Also, e 1ee^{-1} \ne e.

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

:C 1(X,)C 0(X,) \partial : C_1(X,\mathbb{Z}) \to C_0(X,\mathbb{Z})

such that

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

for each edge ee, and

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

is the group of integral 1-cycles on XX.

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

c γ=e 1++e n c_\gamma = e_1 + \cdots + e_n

For any path γ\gamma we have

c γ 1=c γ, c_{\gamma^{-1}} = -c_{\gamma},

and if γ\gamma and δ\delta are composable then

c γδ=c γ+c δ 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 XX, where the objects are the vertices of XX and the morphisms are freely generated by the edges except for relations saying that the inverse of e:xye: x \to y really is e 1:yxe^{-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 γ:xy\gamma : x \to y gives a morphism which I’ll call [[γ]]:xy[[\gamma]] : x \to y in the abelianized fundamental groupoid. We say two paths γ,γ:xy\gamma, \gamma' : x \to y are homologous if [[γ]]=[[γ]][[\gamma]] = [[\gamma']].

Here’s a nice thing:

Lemma A. Let XX be a graph. Two paths γ,δ:xy\gamma, \delta : x \to y in XX are homologous if and only if they give the same 1-chain: c γ=c δ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,)=C 0(X,),C 1(X,)=C 1(X,),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

:C 1(X,)C 0(X,) \partial : C_1(X,\mathbb{R}) \to C_0(X,\mathbb{R})

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

Z 1(X,)=Z 0(X,), 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,)Z_1(X,\mathbb{Z}) is a free abelian group, it forms a lattice in the space of 1-cycles. Any edge of XX can be seen as a 1-chain, and there is a unique inner product on C 1(X,)C_1(X,\mathbb{R}) such that edges form an orthonormal basis (with each edge e 1e^{-1} counting as the negative of ee.) There is thus an orthogonal projection

π:C 1(X,)Z 1(X,). \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 XX with a chosen basepoint x 0x_0. We define an atom to be a homology class of paths starting at the basepoint, like

[[α]]:x 0x [[\alpha]] : x_0 \to x

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

Definition. Let XX be a connected graph with a chosen basepoint. Let AA be its set of atoms. Define the map

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


i([[α]])=π(c α). i([[ \alpha ]]) = \pi(c_\alpha) .

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

Theorem A. The following are equivalent:

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

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

π(c γ)=π(c αc β)=i([[α]])i([[β]]). \pi(c_\gamma) = \pi(c_{\alpha} - c_\beta) = i([[ \alpha ]]) - i([[ \beta ]]) .

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

c γisorthogonaltoevery1cyclei([[α]])=i([[β]]). c_{\gamma} \; is \; orthogonal \; to \; every \; 1-cycle \; \iff \; i([[ \alpha ]]) = i([[ \beta ]]) .

On the other hand, Lemma A says

c γ=0[[α]]=[[β]]. c_\gamma = 0 \; \iff \; [[ \alpha ]]= [[ \beta ]].

Thus, to prove (1)\iff(2), it suffices to that show that XX has no bridges if and only if every 1-chain c γc_\gamma orthogonal to every 1-cycle has c γ=0c_\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 XX has no bridges, we can extend i:AZ 1(X,) i : A \to Z_1(X,\mathbb{R}) to an embedding of the whole maximal abelian cover of XX.

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 γ:xx\gamma : x \to x in which each vertex except xx appears at most once, while xx appears exactly twice, as the starting point and ending point. Let the support of a 1-chain cc, denoted supp(c)\supp(c), be the set of edges ee such that c,e>0\langle c, e\rangle &gt; 0. This excludes edges with c,e=0\langle c, e \rangle= 0 , but also those with c,e<0\langle c , e \rangle &lt; 0, which are inverses of edges in the support. Note that

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

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

Okay, here are the lemmas!

Lemma B. Let XX be any graph and let cc be an integral 1-cycle on XX. Then for some nn we can write

c=c σ 1++c σ n c = c_{\sigma_1} + \cdots + c_{\sigma_n}

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

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

Lemma C. Let γ:xy\gamma: x \to y be a path in a graph XX. Then for some n0n \ge 0 we can write

c γ=c δ+c σ 1++c σ n c_\gamma = c_\delta + c_{\sigma_1} + \cdots + c_{\sigma_n}

where δ:xy\delta: x \to y is a simple path and σ i\sigma_i are simple loops with supp(c δ),supp(c σ i)supp(c γ)\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 σ ic_{\sigma_i}’s we show what’s left is c δc_\delta for a simple path δ:xy\delta: x \to y.   █

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

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

Proof. It’s easy to show a bridge ee gives a nonzero 1-chain c ec_e that’s orthogonal to all 1-cycles, so the hard part is showing that for a bridgeless graph, if c γc_\gamma is orthogonal to every 1-cycle then c γ=0c_\gamma = 0. The idea is to start with a path for which c γ0c_\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 XX has no bridges, we use Ilya Bogdanov’s idea to build a 1-cycle that’s not orthogonal to c δc_\delta. The basic idea is to take the path δ:xy\delta : x \to y and write it out as δ=e 1e n\delta = e_1 \cdots e_n. Since the last edge e ne_n is not a bridge, there must be a path from yy back to xx that does not use the edge latexe nlatex 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 δc_\delta and thus with c γ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 XX and embedded its atoms into the space of 1-cycles via a map

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

These atoms are the vertices of the maximal abelian cover X¯\overline{X}. Now we’ll extend ii to an embedding of the whole graph X¯\overline{X} — or to be precise, its geometric realization |X¯||\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 ii maps each atom to a point in the vector space Z 1(X,)Z_1(X,\mathbb{R}), jj maps each edge of |X¯||\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 XX is a connected graph with basepoint, the map i:AZ 1(X,)i : A \to Z_1(X,\mathbb{R}) extends to a continuous map

j:|X¯|Z 1(X,) j : |\overline{X}| \to Z_1(X,\mathbb{R})

sending each edge of |X¯||\overline{X}| to a straight line segment in Z 1(X,)Z_1(X,\mathbb{R}). If XX has no bridges, then jj 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(Σ,)/H 1(Σ,)H_1(\Sigma,\mathbb{R})/H_1(\Sigma,\mathbb{Z}). We can similarly define the Jacobian of a graph XX to be H 1(X,)/H 1(X,)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||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:

This says that the vertices of a bridgeless graph XX 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!

Posted at August 6, 2016 10:09 AM UTC

TrackBack URL for this Entry:

1 Comment & 0 Trackbacks

Re: Topological Crystals (Part 3)

This looks like fun stuff! The remarks about the Laves graph on p.2 of the paper are especially cool. It also seems vaguely related to a paper that I wrote a couple of years ago with a general rigorous version of Weyl’s tile argument against the idea that space may be discrete.

One starts with a periodic graph as a mathematical model for discrete space. One then writes it as a cover of a finite graph with a free abelian group of deck transformations. The difference to topological crystals here is that the “base” graph comes equipped with edge weights in d\mathbb{Z}^d which assign to every edge the number of unit cells that one has to translate in the covering space. The one can recover the original periodic graph via the Grothendieck construction. The edge weights also span the unit ball of a norm on homology which governs the large-scale geometry of the graph, and this is how the discreteness of space could become manifest macroscopically. The green hexagon in your figure from Part 1 may be a scaled-up version of this unit ball:

graphene example

Unfortunately, I learned of the closely related work of Kotani and Sunada only after the paper had appeared. They have more results and the better abstract perspective!

Posted by: Tobias Fritz on August 6, 2016 7:15 PM | Permalink | Reply to this

Post a New Comment