Links in Surfaces and Laplacian Modules

The Laplacian matrix of a signed graph is a discrete version of the well-studied Laplacian operator of physics. Its spectrum yields insights about the structure of the graph. (For a survey see [12]). For signed graphs embedded in a closed oriented surface $S$, information about how the graph winds about $S$ can be used to define a Laplacian matrix $L_{G}$ with homology coefficients (see, for example, [9]). We introduce the module ${\cal L}_{G}$ presented by $L_{G}$. Its module order is a polynomial $\Delta_{G}$ over the Laurent polynomial ring ${\Lambda}=\mathbb{Z}[x_{1}^{\pm 1},y_{1}^{\pm 1},\ldots,x_{g}^{\pm 1},y_{g}^{\pm 1}]$, where $g$ is the genus of $S$. The polynomial is the determinant of $L_{G}$, but we will see that it can also be computed using a simple skein relation.

When the graph $G$ is embedded in $S$ the well-known medial construction associates a checkerboard colored diagram $D\subset S$ for a link $\ell$ in the thickened surface $S\times[0,1]$. In [7] the authors showed that signature, nullity and determinant, classical link invariants, can be defined for $\ell$ using the usual Laplacian matrix, which can be viewed as a generalization of the Goeritz matrix of a link. Here we consider the Laplacian matrix with homological coefficients. We show that the module ${\cal L}_{G}$ it presents is unaffected by Reidemeister moves. Invariants of links in the thickened surface $S\times[0,1]$ are described.

Any link $\ell$ in $S\times[0,1]$ can be described by a diagram in $S$. Adding or deleting “hollow handles” to $S$, avoiding $D$, might produce a surface of smaller genus. The minimum possible genus is the virtual genus of $\ell$. In many cases the polynomial $\Delta_{G}$ can be used to establish that a surface achieves the minimum possible genus.

The authors are grateful to Seiichi Kamada, Louis H. Kauffman and Christine Ruey Shan Lee for helpful comments.

A graph $G$ in a closed, connected oriented surface $S$ with edge and vertex sets $V_{G},E_{G}$, respectively, is signed if every edge $e\in E_{G}$ is labeled with $\sigma_{e}=+1$ or $-1$. In order to avoid visual clutter, unlabeled edges will be assumed to have sign $+1$.

Let $\tilde{S}$ denote the universal abelian covering space of $S$. We regard the deck transformation group $A(\tilde{S})$ multiplicatively. It is isomorphic to $H_{1}(\tilde{S};\mathbb{Z})$. We fix a symplectic homology basis ${\cal B}=\{x_{1},y_{1},\ldots,x_{g},y_{g}\}$, and represent its members by oriented closed curves. Each closed curve in $S$ is labeled by the element of $A(\tilde{S})$ that it determines, a monomial in the variables $x_{i},y_{i}$.

Although we work with undirected graphs, it is convenient for the following definition to regard $G$ as directed. There is a standard way to do this: replace each edge $e\in E_{G}$ (including loops) with a pair of edges joining the same endpoints, each with the same weight as $e$ but with opposite directions. Any directed path in $S$ determines an element $\phi_{P}\in A(\tilde{S})$, read by traveling along the path in the preferred direction, recording $y_{k}^{\pm 1}$ (resp. $x_{k}^{\pm 1}$) as we cross the homology basis curve that is labeled $x_{k}$ (resp. $y_{k}$), the exponent determined as in Figure 1. In particular, each directed edge $e\in E_{G}$ determines a monomial $\phi_{e}$.

Assume that $G$ is a signed directed graph with vertex set $V_{G}=\{v_{1},\ldots,v_{n}\}$. The adjacency matrix $A_{G}=(a_{i,j})$ of $G$ (with respect to ${\cal B}$) is the $n\times n$ matrix with non-diagonal entries $a_{i,j}$ equal to $\sum\sigma_{e}\phi_{e}$, where the summation ranges over all edges from $v_{i}$ to $v_{j}$. Diagonal entries of $A_{G}$ are zero. Denote by ${\delta}_{g}=({\delta}_{i,j})$ the $n\times n$ diagonal matrix with ${\delta}_{i,i}=\sum_{j}a_{i,j}$.

Henceforth the graphs that we consider will be weighted but undirected.

The entries of $L_{G}$ are elements of the Laurent polynomial ring ${\Lambda}=\mathbb{Z}[x_{1}^{\pm 1},y_{1}^{\pm 1},\ldots,x_{g}^{\pm 1},y_{g}^{\pm 1}]$. The graph $G$ determines a line bundle with a copy of ${\Lambda}$ at each vertex. Adopting the terminology of [9], we call $\phi_{e}$ the connection of the edge $e$.

Proposition 2.2 enables us to compute $\Delta_{G}$ using a skein computation tree. Leaves of the tree are disjoint unions of 1-vertex graphs. The following are easily proved and useful for computation.

• •

  If $G$ is the union of two disjoint subgraphs $G_{1}$ and $G_{2}$, then $\Delta_{G}=\Delta_{G_{1}}\Delta_{G_{2}}$.

• •

  If $G$ has no edges, then $\Delta_{G}=0$.

• •

  If $G$ is a cyclic graph, then $\Delta_{G}=\sigma(2-\phi-\phi^{-1})$, where $\sigma$ is the product of the signs $\sigma_{e}$ of edges of $G$, and $\phi$ is the connection of the cycle (with either orientation).

The Laplacian matrix $L_{G}$ determines a homomorphism of the free module ${\Lambda}^{n}$ generated by the vertices of $G$. The cokernel ${\Lambda}^{n}/{\Lambda}^{n}L_{G}$ is a ${\Lambda}$-module ${\cal L}_{G}$, the Laplacian module of $G$. Its module order is the Laplacian polynomial $\Delta_{G}$. In this context it is well defined only up to multiplication by units in ${\Lambda}$. However, Forman’s equation (2.3) provides a normal form that is preserved by equation 2.2. (Definition 2.2 also gives the normalized form since it agrees with Forman’s formula.) We will henceforth assume that $\Delta_{G}$ is normalized in this way, well defined up to multiplication by $-1$.

A thickened surface is a product $S\times[0,1]$, where $S$ is a closed, connected oriented surface. For $p\in S$, we think of the point $(p,1)$ as lying above $(p,0)$. A link $\ell\subset S\times[0,1]$ is a pairwise disjoint collection of finitely many embedded closed curves. It can be described by a link diagram $D$: a 4-valent graph $|D|$ embedded in $S$, called a universe, with hidden-line effect in a neighborhood of each vertex indicating how one strand of $\ell$ passes over another.

R-equivalence of link diagrams in $S$ is the equivalence relation generated by Reidemeister moves (See Figure 4.) It is well known that Reidemeister’s original proof in [13] for planar links shows generally that two links in $S\times[0,1]$ are isotopic if and only if their diagrams are R-equivalent.

A region of a link diagram is a connected component of $S\setminus|D|$. A link diagram is cellular if all of its regions are contractible. We can turn any diagram into a cellular diagram with Reidemeister moves of type II. Less obvious is the following.

A link diagram $D$ is checkerboard colorable if it is possible to shade certain regions of $D$ so that whenever two regions share a boundary, exactly one of them is shaded. A diagram with such a shading is checkerboard colored. (We will denote it also by $D$ in order to avoid excessive notation.) Any checkerboard colorable diagram admits exactly two such shadings. The proof of the following is easy and left to the reader.

A checkerboard colored cellular link diagram $D\subset S$ determines a signed embedded graph $G\subset S$, unique up to isotopy, via the “medial graph” construction (see Figure 6). Vertices of $G$ correspond to shaded regions of $D$, while each pair of vertices corresponding to shaded regions meeting at a crossing of $D$ are joined by an edge $e$ with weight $w_{e}$ determined as in Figure 6. From the graph we can reconstruct $D$. The other checkerboard coloring of $D$ determines a dual signed graph $G^{*}$. If $e^{*}$ is an edge of $G^{*}$ dual to $e$, then $w_{e^{*}}=-w_{e}$.

Recall that we take the normalized Laplacian polynomial $\Delta_{G}$ is well defined up to multiplication by $-1$.

Let $D\subset{\mathbb{S}}^{2}$ be a checkerboard colored link diagram, and let $D^{*}$ denote the dual checkerboard colored diagram. By stretching an outer arc of $D$ and pulling over the rest of the diagram and then around the sphere to its original position, we see that $D$ and $D^{*}$ are equivalent under Reidemeister moves. (This fact was first observed in [11], where a more formal argument appears.) Hence ${\cal L}_{G}$ and ${\cal L}_{G^{*}}$ are isomorphic.

The following example shows that for diagrams in surfaces of higher genus, ${\cal L}_{G}$ and ${\cal L}_{G^{*}}$ need not be isomorphic.

The Laplacian polynomials $\Delta_{G}$ and $\Delta_{G^{*}}$ in Example 3.8 are the same. This holds generally for signed graphs in the torus [15], a consequence of the fact that null-homologous curves in the torus are contractible. The following example shows that equality does not hold for surfaces of higher genus.

A virtual link $\ell$ can be regarded as a link diagram $D$ defined up to Reidemeister moves, surface automorphisms and addition or deletion of hollow handles. Handle addition is 0-surgery, replacing ${\mathbb{S}}^{0}\times\mathbb{D}^{2}\subset S\setminus D$ with $\mathbb{D}^{1}\times{\mathbb{S}}^{1}$, thereby increasing the genus of the surface. The handle deletion is 1-surgery along a simple closed curve $C\subset S\setminus D$, replacing $C\times\mathbb{D}^{1}$ with $\mathbb{D}^{2}\times{\mathbb{S}}^{0}$; when $C$ is essential and nonseparating, the surgery decreases the genus of the surface. The virtual genus $vg\ (\ell)$ is the minimum possible genus $g\ (S)$ a surface $S$ that can be obtained in this way.

The information in the polynomial $\Delta_{G}$ can often establish that $g(S)=vg(\ell)$. Our approach is similar to that of [2]. Assume that $g(S)>vg(\ell)$. Then a theorem of G. Kuperberg [10] implies that after Reidemeister moves $S\setminus|D|$ contains an essential nonseparating simple closed curve $C$ upon which we can perform surgey to reduce the genus of $S$. If we orient $C$ and extend its homology class to a symplectic basis for $H(S;\mathbb{R})$, then this basis element will not appear among the coefficients of $\Delta_{G}$. Contrapositively, if the coefficients of $\Delta_{G}$ span $H_{1}(S;\mathbb{R})$, then $g(S)=vg(\ell)$. We make this more precise in the following. The same conclusion holds for the dual graph $G^{*}$.