Today’s post is about a really beautiful theorem of Johannes Carmesin from late 2017. I think it was somewhat overlooked at the time due to the focus on another tremendously exciting theorem of his (a 3-dimensional analog of Kuratowski’s Theorem; see his talk at SiGMa). Hopefully this post can help rectify that. The material discussed here is from the fourth paper in his series on embedding $2$-complexes into $3$-space [I, II, III, IV, V].

Let’s begin with Whitney’s theorem.

Theorem 1 (Whitney’s planarity criterion, [W32]).  A graph is planar if and only if its dual matroid is graphic.

Furthermore, the dual matroid of a plane graph can be represented by the graph’s planar dual. As an aside, I recently learned that Theorem 1 actually predates Whitney’s introduction of matroid theory [W35]. 

If we want to move up a dimension, we should view a graph $G$ as a topological space and then glue disjoint closed disks $D_1, \ldots, D_k$ to cycles $C_1, \ldots, C_k$ of $G$ by, for each $i,$ identifying the boundary of $D_i$ with $C_i$ in the natural way. We can then ask if this new space has a topological embedding into the $3$-sphere $\mathbb{S}^3$ (aka the boundary of a ball in $\mathbb{R}^4$). This is natural since a graph is planar if and only if it embeds into the $2$-sphere; it is convenient to work with spheres because they are more symmetric than real space.

We need one more topological definition; informally, a space is simply connected if any two points can be connected by a curve and any simple closed curve can be continuously deformed to a point (while staying within the space). So a torus is not simply connected because the second condition fails for curves which “go around the donut”.

We would like to represent these spaces combinatorially. For that we can take a tuple $(G, \mathcal{C})$ where $G$ is a graph and $\mathcal{C}$ is a collection of cycles of $G$. Cycles in $\mathcal{C}$ are called faces (so each face is the boundary of a distinct disk). If $G$ is simple (has no loops or parallel edges) and $\mathcal{C}$ consists of distinct triangles, we call $(G, \mathcal{C})$ a $2$-dimensional simplicial complex. For simplicity, we won’t distinguish between $(G, \mathcal{C})$ and the corresponding topological space.

So, what is the matroid of a $2$-dimensional simplicial complex $(G, \mathcal{C})$? Well, since we’re going up a dimension, it should be a matroid on the faces. It turns out that we can just take the matroid on $\mathcal{C}$ which is represented by the signed edge/face incidence matrix over the ternary field $\textrm{GF}(3)$. This is again quite similar to the graph case; the cycle matroid of a graph could be defined via the signed vertex/edge incidence matrix.

Here’s the actual definition. First, fix an arbitrary orientation $\overrightarrow{G}$ of $G$ and an arbitrary cyclic orientation $\overrightarrow{C}$ of each face $C \in \mathcal{C}$. Then the edge-face incidence matrix is the $E(\overrightarrow{G}) \times \mathcal{C}$ matrix over $\textrm{GF}(3)$ where, for each directed edge $e$ and face $C$, if $\overrightarrow{C}$ traverses $e$ in the direction of $e$, then the corresponding entry is $1$, if $\overrightarrow{C}$ traverses $e$ in the opposite direction then the entry is $-1$, and otherwise the entry is $0$. The matroid of $(G, \mathcal{C})$ is the matroid on $\mathcal{C}$ which is represented by this matrix; it does not depend on the particular orientations chosen.

Now we are ready to state the theorem, besides a connectivity-like condition called “locality” which we’ll discuss briefly later. By “dual matroid” we just mean the matroidal dual of the matroid defined above.

Theorem 2 (Carmesin’s $\mathbb{S}^3$-embeddability criterion).  A simply connected, local, $2$-dimensional simplicial complex embeds into $\mathbb{S}^3$ if and only if its dual matroid is graphic.

Let’s just appreciate this for a moment. Wow! The theorems in this series are really amongst my favorite theorems of all time. For any students or postdocs reading this who agree, let me quickly point out that Johannes will be recruiting soon. 🙂

The Dual Graph

As in Whitney’s theorem, if the complex $(G, \mathcal{C})$ is embedded as $P \subset \mathbb{S}^3$, then its dual matroid can be represented by its dual graph. The dual graph has a vertex for each component of $\mathbb{S}^3 \setminus P$ and an edge for each face in $\mathcal{C}$; each face is incident with at most two components of $\mathbb{S}^3 \setminus P$, and these are the vertices it is incident to.

So a circuit of the matroid of $(G, \mathcal{C})$ corresponds to a bond of the dual graph. (A bond of a graph is a set of edges between two sets of vertices which partition the vertex set and each induce a connected subgraph.) So circuits roughly correspond to sets of faces whose image under the embedding is an orientable surface (this is true up to some technical modifications – for instance, we could identify two edges on the surface). Certainly such a set of faces is a circuit of the matroid, since if we take the “clockwise” orientation of each of those faces, each incident edge is traversed exactly once in each direction. This illustrates that the corresponding set of column vectors of the signed incidence matrix is minimally dependent.

The proofs in the paper work another way; Johannes considers the row space of the signed incidence matrix. The support of an edge $e$ is the set of faces which $e$ is incident to. This is also the support of the row corresponding to $e$ in the signed incidence matrix. Similarly to how the cut space of a graph is generated by the sets $\delta(v)$ of edges incident to a vertex $v$, the circuit space of the dual matroid is generated by the supports of the edges $e$ (although we work over $\textrm{GF}(3)$). If the $2$-dimensional simplicial complex $(G, \mathcal{C})$ embeds into $\mathbb{S}^3$, then we get, for each edge, a cyclic orientation of its support. This corresponds to a closed trail of the dual graph.

The Harder Direction

This is all really pretty, but of course working with the dual graph is the easier direction of Theorem 2. The other direction relies on Perelman’s proof [P02, P03, P03B] of the Poincaré Conjecture! (This states that every compact, simply-connected, $3$-dimensional manifold is homeomorphic to the $3$-sphere.)

How? Well, suppose that for each edge we have a guess as to the cyclic ordering of its support. Furthermore, suppose that at each vertex $v$, those guesses “project” to a planar embedding of the graph $H[v]$ whose vertices are the edges incident with $v$ and whose edges are the faces incident with $v$ (we can encode an embedding of a graph into an orientable surface by specifying the cyclic order of edges incident to each vertex). It turns out that, given the appropriate conditions on the $2$-dimensional simplicial complex, this is enough information to encode an embedding into a $3$-manifold to which Perelman’s theorem can be applied.

Locality

It would be nice to end with the connection to Perelman’s theorem, but let me actually conclude by quickly giving the definition of “local”. A $2$-dimensional simplicial complex is local if for each vertex $v$, the dual matroid $M$ restricted to the edges of $H[v]$ is equal to the dual matroid of $H[v]$. (The graph $H[v]$ is called the link graph.) If a $2$-dimensional simplicial complex embeds as $P \subset \mathbb{S}^3$ and the boundary of each component of $\mathbb{S}^3\setminus P$ is homeomorphic to the $2$-sphere, then it is local (Fact 3.1 from the paper). In order to make the analagous statement true for planar graphs, all we would need is $2$-connectivity.

P.S. I’d like to thank Johannes for answering some questions about the papers, especially in regards to bonds of the dual graph.

Sources

[I, II, III, IV, V] Carmesin, Johannes. Embedding simply connected 2-complexes in 3-space. arXiv: 1709.04642 (2017). (for the first paper in the series of five)

[P02] Perelman, Grisha. The entropy formula for ricci flow and its geometric applications. arXiv: 0211159 (2002).

[P03] Perelman, Grisha. Finite extinction time for the solutions to the Ricci flow on certain three-manifolds. arXiv: 0307245 (2003).

[P03B] Perelman, Grisha. Ricci flow with surgery on three-manifolds. arXiv: 0303109 (2003).

[W32] Whitney, Hassler. Non-separable and planar graphs. Trans. Amer. Math. Soc. 34 (1932), no. 2, 339–362.

[W35] Whitney, Hassler. On the Abstract Properties of Linear Dependence.Amer. J. Math. 57 (1935), no. 3, 509–533.