Carmesin’s 3-dimensional version of Whitney’s planarity criterion

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.

Online talk: Marthe Bonamy

Mon, July 6, 3pm ET (8pm BST, 7am Tue NZST)
Marthe Bonamy, Univ. Bordeaux, CNRS
Graph classes and their Asymptotic Dimension
Youtube

Abstract:
Introduced in 1993 by Gromov in the context of geometric group theory, the asymptotic dimension of a graph class measures how much “contact” is necessary between balls of “bounded” diameter covering a graph in that class. This concept has connections with clustered coloring or weak diameter network decompositions. While it seems surprisingly fundamental, much remains unknown about this parameter and it displays intriguing behaviours. We will provide a gentle exposition to the area: from the state of the art to the main tools and questions, including some answers.

This is joint work with Nicolas Bousquet, Louis Esperet, Carla Groenland, François Pirot and Alex Scott.

Online talks: announcement

Hello everyone.

As you have likely already noticed, there is no talk in the seminar series today. As several other seminars have paused talks over these summer months, we are expanding the focus of the series to “Graphs and Matroids”.

We’re excited to have Marthe Bonamy giving the first talk next Monday under the new name, and Federico Ardila speaking the following week. As usual, more details will follow. See you next Monday!

Online talk: Matthew Kwan

Mon, June 22, 3pm ET (8pm BST, 7am Tue NZST)
Matthew Kwan, Stanford University
Halfway to Rota’s basis conjecture
Youtube

Abstract:
In 1989, Rota made the following conjecture. Given $n$ bases $B_1,\ldots,B_n$ in an $n$-dimensional vector space $V$, one can always find $n$ disjoint bases of $V$, each containing exactly one element from each $B_i$ (we call such bases transversal bases). Rota’s basis conjecture remains wide open despite its apparent simplicity and the efforts of many researchers. In this talk we introduce the conjecture and its generalisation to matroids, and we outline a proof of the result that one can always find $(1/2−o(1))n$ disjoint transversal bases (improving on the previous record of $\Omega(n/\log{n})$). This talk will be accessible to non-matroid theorists.

Joint work with Matija Bucic, Alexey Pokrovskiy, and Benny Sudakov.