Graph Complexity and Link Colorings

Consider a locally finite graph without multiple edges or isolated vertices. Let $p$ be an odd prime. We can attempt to form a “$p$-coloring” of the graph, assigning elements (“colors”) of $\mathbb{Z}/p$ to the vertices in such a way that the color of any vertex is the average of the colors of the adjacent vertices. Obviously, the graph can be colored trivially or “monochromatically,” that is, with any single color. But nontrivial $p$-colorings might exist as well. It is clear that the set of all $p$-colorings of the graph is a vector space under vertex-wise addition and scalar multiplication.

Now consider a plane diagram of a knot or link. (As a knot is a link with only one component, henceforth we will use the more general term.) We can try to form a “$p$-coloring,” assigning colors to the arcs in such a way that the color of any overcrossing arc is the average of the colors of its two undercrossing arcs (see Section 4). Again we can color trivially, but nontrivial $p$-colorings can exist too. The set of the all $p$-colorings of the diagram is a vector space under arc-wise addition and scalar multiplication.

There is a strong relationship between $p$-colorings of plane graphs and $p$-colorings of link diagrams [27, 33]. We review the relationship in Section 3. By substituting the continuous palette ${\mathbb{T}}=\mathbb{R}/\mathbb{Z}$, which contains $\mathbb{Z}/p$ as a subgroup, and replacing the plane with a compact orientable surface $S$, we enter the world of algebraic dynamical systems [28]. When $S$ is an annulus, we obtain a version of Lehmer’s unanswered question about roots of monic integral polynomials, which we formulate in terms of signed graphs.

Let $G$ be a graph, not necessarily planar, with vertex set $V(G)=\{v_{1},\ldots,v_{n}\}$ and edge set $E(G)=\{e_{1},\ldots,e_{m}\}$. The graph is allowed to have loops and multiple edges, but no isolated vertices. Each edge $e\in E(G)$ is labeled with a sign $\sigma_{e}=\pm 1$. All graphs that we consider are assumed to have signed edges. The graph is unsigned if every $\sigma_{e}=+1$.

The signed adjacency matrix of $G$ is the $n\times n$ matrix $A=(a_{i,j})$ such that $a_{i,j}$ is the sum of the signs of all edges between $v_{i}$ and $v_{j}$, with loops counted twice. Define the signed degree matrix ${\delta}=({\delta}_{i,j})$ to be the $n\times n$ diagonal matrix with ${\delta}_{i,i}$ equal to the sum of signs of edges incident on $v_{i}$. Again, loops contribute twice.

An integer matrix presents an abelian group in which columns (resp. rows) correspond to the generators (resp. relations) of the group. Equivalently, the group is the cokernel of the matrix when regarded as a linear transformation of free abelian groups.

We note that in computing the integer matrix $L_{G}$ we may ignore loops, since they contribute equally to $A$ and ${\delta}$. However, this will not be the case for the extended definition we make in Section 5.

When we regard the entries of $L_{G}$ modulo $p$, the rows represent the relations needed to $p$-color the graph. (Here we are extending the notion of $p$-coloring to signed graphs.) Hence the space of $p$-colorings of $G$ is isomorphic to the null space of $L_{G}$. Nontrivial $p$-colorings exist precisely when its dimension is greater than 1. Note that the abelian group of $p$-colorings of $G$ is isomorphic to ${\cal L}_{G}\otimes\mathbb{Z}/p$.

Returning to integer coefficients, the nullity of the Laplacian matrix $L_{G}$ is equal to 1 whenever $G$ is connected and unsigned (see, for example, Lemma 13.1.1 of [12]). In this case the Laplacian group ${\cal L}_{G}$ decomposes as the direct sum of $\mathbb{Z}$ and the torsion subgroup $T{\cal L}_{G}$. The Matrix Tree Theorem (c.f. [35]) implies that ${\kappa}_{G}=|T{\cal L}_{G}|$ is equal to the number of spanning trees of $G$.

More generally, we define tree complexity $\tau_{G}$ of a connected graph $G$ by

where the summation is taken over all spanning trees of $G$. If $G$ not connected, then we define $\tau_{G}$ to be the product of the tree complexities of its connected components. Again by [35], we have $\tau_{G}={\kappa}_{G}$ if and only if $\tau_{G}$ is nonzero; for connected $G$ this common value is equal to the absolute value of any $(n-1)\times(n-1)$ principal minor of $L_{G}$. However, the following example shows that $\tau_{G}$ can vanish, whereas ${\kappa}_{G}$ is positive by definition.

A link $\ell$ in $\mathbb{R}^{3}$ (or equivalently ${\mathbb{S}}^{3}$) is a set of smoothly embedded, pairwise disjoint simple closed curves. Any link can be described by a diagram $D$, a 4-valent plane graph with a hidden-line device in a neighborhood of each vertex indicating how one strand of the link passes over another.

We will make use of a few other related terms. An arc of $D$ is a maximal connected subset. Following [14], we refer to the underlying graph of $D$ as a universe of $\ell$, denoted here by $|D|$. Finally, a region of $D$ is a connected component of $\mathbb{R}^{2}\setminus|D|$.

As usual, isotopic links are regarded as the same. It is well known that two links are isotopic if and only if a diagram of one can be transformed into a diagram of the other by a finite sequence of local “Reidemeister moves” as in Figure 2 (see [5] or [18] for details). Consequently, any quantity that is determined by a diagram and is unchanged by Reidemeister moves is a link invariant.

We can obtain a plane graph $G$ from a link diagram $D$ by the following familiar procedure. First we checkerboard shade $D$, shading some of the regions so that every edge meets a single shaded region. There are two checkerboard shadings of $D$, but for the sake of definiteness we will choose the one in which the unbounded region is unshaded. We construct a graph $G$ with a vertex in each shaded region of $D$ and an edge through each crossing, joining the vertices of the regions on both sides. The sign of the edge is determined by the type of crossing, as in Figure 3. Such a graph is often called a “Tait graph,” in honor of Peter Guthrie Tait, a 19th century pioneer of knot theory.

For some link diagrams it can happen that the Tait graph has isolated vertices. We avoid this by always assuming that $|D|$ is connected, a condition that we can assume without loss of generality by applying Reidemeister moves to $D$.

For a plane graph $G$ we can reverse the above procedure to obtain a link digram $D$. For this we use the medial construction, replacing each edge of $G$ by a pair of arc segments that run parallel to the edge except at the middle, where they cross, as in Figure 4. We join the segments near vertices in the obvious way without creating any additional crossings.

Figure 7 shows the diagram of a 3-component link $\ell$ obtained from the graph of Example 2.2. According to [8] the link was introduced by J. Milnor. Original interest in the link came from the fact that it was the first non-alternating boundary link discovered with zero Alexander polynomial, a fact that we will not use here. We will return to the link in the next section.

Assume that $D$ is a diagram of a link $\ell$. Let $p$ be a prime. A (Fox) $p$-coloring of $D$ is an assignment of elements of $\mathbb{Z}/p$, called colors, to the arcs of $D$ such that twice the color of any overcrossing arc is equal to the sum of the colors of its undercrossing arcs, as in Figure 5. A $p$-coloring is trivial if all assigned colors are the same.

We denote the vector space of $p$-colorings of $D$ by ${\rm Col}_{p}(D)$ and refer to it as the $p$-coloring space of the diagram. It is a vector space over $\mathbb{Z}/p$, with addition and scalar multiplication performed arc-wise. A routine exercise shows that diagrams differing by a Reidemeister move have isomorphic $p$-coloring spaces. Hence ${\rm Col}_{p}(D)$ is an invariant of the link $\ell$, and so we write ${\rm Col}_{p}(\ell)$ and speak of the vector space as the $p$-coloring space of the link. (For more information about this popular construction of knot theory, there are many excellent expositions such as [20].)

Fox envisioned $p$-colorings as homomorphisms from the link group $\pi_{\ell}=\pi_{1}(\mathbb{R}^{3}\setminus\ell)$ onto the dihedral group

He described the correspondence using the Wirtinger presentation of $\pi_{\ell}$, in which generators (resp. relations) are identified with arcs (resp. crossings) of a diagram $D$. Given a $p$-coloring of $D$ we obtain a homomorphism from $\pi_{\ell}$ to $D_{2p}$ by sending a Wirtinger generator of an arc colored by $k\in\mathbb{Z}/p$ to the element $\tau\alpha^{k}$ of $D_{2p}$.

If instead of the Wirtinger presentation, we use the Dehn presentation of $\pi_{\ell}$, a presentation in which generators (resp. relations) are identified with bounded regions (resp. crossings), then a $p$-coloring becomes an assignment of colors to the bounded regions of $D$. We assign $0$ to the unbounded region. The condition at each crossing that corresponds to the Fox $p$-coloring condition appears in Figure 6. Details can be found in [32]. We will call such an assignment of colors to the regions a Dehn $p$-coloring of the diagram. The collection of all Dehn $p$-colorings of a diagram is vector space under region-wise addition and scalar multiplication, isomorphic to the space of Fox $p$-colorings.

Assume that $D$ is a link diagram arising from a plane graph $G$ by the medial construction. Any $p$-coloring of $G$ determines Dehn and Fox $p$-colorings of $D$. To see this, first assign the colors of the vertices of $G$ to the associated shaded regions of the link diagram. Then use the Dehn coloring relations to determine uniquely the colors of the unshaded regions. This is possible since the unbounded region is already labeled (with $0$). Uniqueness follows from the observation that if we determine the color of some unshaded region and then follow a simple closed path around a vertex, determining the colors of successive unshaded regions along the way, then when we return to the initial unshaded region, the Laplace relation forces us to arrive at the same color with which we began. (More details can be found in [32].) Finally, assign to each arc of $D$ the sum of the colors of the regions on both sides. It is easy to verify that we obtain in this way is well defined Fox $p$-coloring of the diagram.

Conversely, any Fox $p$-coloring of a link diagram determines a $p$-coloring of the associated Tait graph. The Dehn color of any region is the sum of the colors of the arcs that we cross traveling along any path to the unbounded region. The graph coloring is simply a restriction to the shaded regions.

The two processes above are inverses of each other. Hence the vector spaces of $p$-colorings of $G$ and $D$ are isomorphic.

As an example, consider the diagram of Milnor’s boundary link as in appears in Figure 7. The Fox 3-coloring displayed corresponds to the 3-coloring of the graph G in Figure 1.

Every finite cyclic group is contained in the compact abelian “circle group” ${\mathbb{T}}=\mathbb{R}/\mathbb{Z}$ as a subgroup. If we replace $\mathbb{Z}/p$ by ${\mathbb{T}}$, then the coloring vector spaces for graphs and link diagrams become compact abelian groups. (This extension of Fox $p$-coloring was introduced in [29].) The Laplace group ${\cal L}_{G}$ tensored with ${\mathbb{T}}$ consists of $|T{\cal L}_{G}|$ tori each of dimension equal to the nullity of $L_{G}$. A similar description of the circle-coloring group ${\rm Col}_{\mathbb{T}}(\ell)$ applies. In the following sections we will explore this idea for infinite graphs and links with symmetries. The result is a rich structure that brings algebraic dynamics into our story.

A (signed) graph $G$ is $d$-periodic if it admits a cofinite free $\mathbb{Z}^{d}$-action by automorphisms that preserves the signs of edges. By cofinite we mean the quotient graph $\overline{G}$ is finite, while an action is free if the stabilizer of any edge or vertex is trivial. Such a graph $G$ is locally finite, and finite if and only if $d=0$.

We regard $\mathbb{Z}^{d},d\geq 1,$ as the multiplicative abelian group freely generated by $x_{1},\ldots,x_{d}$. We denote the Laurent polynomial ring $\mathbb{Z}[\mathbb{Z}^{d}]=\mathbb{Z}[x_{1}^{\pm 1},\ldots,x_{d}^{\pm 1}]$ by ${\cal R}_{d}$. As an abelian group ${\cal R}_{d}$ is generated freely by monomials $x^{\bf n}=x_{1}^{n_{1}}\ldots x_{d}^{n_{d}}$, where ${\bf n}=(n_{1},\cdots,n_{d})\in\mathbb{Z}^{d}$. We represent $(0,\ldots,0)$ by ${\bf 0}$. For notational convenience, when $d=1$, we replace $x_{1}$ by $x$.

The vertex set $V(G)$ and the edge set $E(G)$ consist of finitely many vertex orbits $\{v_{1,{\bf n}}\mid{\bf n}\in\mathbb{Z}^{d}\},\ldots,\{v_{n,{\bf n}}\mid{\bf n}\in\mathbb{Z}^{d}\}$ and signed edge orbits $\{e_{1,{\bf n}}\mid{\bf n}\in\mathbb{Z}^{d}\},\ldots,\{e_{m,{\bf n}}\mid{\bf n}\in\mathbb{Z}^{d}\}$, respectively. The $\mathbb{Z}^{d}$-action is determined by

where $1\leq i\leq n,\ 1\leq j\leq m$ and ${\bf n},{\bf n}^{\prime}\in\mathbb{Z}^{d}$. (When $G$ is embedded in some Euclidean space with $\mathbb{Z}^{d}$ acting by translation, it is usually called a lattice graph. Such graphs arise frequently in physics, for example in studying crystal structures.)

When $d>1$ we can think of $G$ as covering a finite graph $\overline{G}$ in the $d$-torus ${\mathbb{T}}^{d}=\mathbb{R}^{d}/\mathbb{Z}^{d}$. When $d=1$, $G$ covers a finite graph $\overline{G}$ in the annulus $\mathbb{A}=I\times{\mathbb{S}}^{1}$. In either case the cardinality $|V(\overline{G})|$ is equal to the number $n$ of vertex orbits of $G$, while $|E(\overline{G})|$ is the number $m$ of edge orbits. The projection map is given by $v_{i,{\bf n}}\mapsto v_{i}$ and $e_{j,{\bf n}}\mapsto e_{j}$.

The Laplacian matrix of a $d$-periodic graph $G$ is defined to be the $n\times n$-matrix $L_{G}={\delta}-A$, where now $A=(a_{i,j})$ is the adjacency ${\cal R}_{d}$-matrix with each entry $a_{i,j}$ equal to the sum of monomials $\sigma_{e}x^{\bf n}$ for each edge $e\in E(\overline{G})$ between $v_{i,\bf{0}}$ and $v_{j,{\bf n}}$. Loops contribute two diagonal terms that are inverse monomials. The signed degree matrix ${\delta}=({\delta}_{i,j})$ is defined as in Section 2.

The matrix $L_{G}$ presents a finitely generated ${\cal R}_{d}$-module, the Laplacian module of $G$, denoted by ${\cal L}_{G}$. The Laplacian (determinant) polynomial $\Delta_{G}$ is the determinant of $L_{G}$. When $d=0$, ${\cal R}_{d}=\mathbb{Z}$ and these definitions reduce to the ones in Section 2. Examples appear below; additional examples can be found in [16, 32]. The reader should be aware that in graph theory literature the term “Laplacian polynomial” is often used for the characteristic polynomial of the integral Laplacian matrix.

Let $G$ be a $d$-periodic graph. The collection of all ${\mathbb{T}}$-colorings of $G$ is the Pontryagin dual group $\widehat{\cal L}_{G}={\rm Hom}({\cal L}_{G},{\mathbb{T}})$. Elements are functions $f:V(G)\to{\mathbb{T}}$ that assign to each vertex $v_{i,{\bf n}}\in V(G)$ a color $f(v_{i,{\bf n}})\in{\mathbb{T}}$ such that the Laplacian condition (corresponding to the $i$th row of $L_{G}$) is satisfied:

where ${\delta}_{i,i}$ is the signed degree of $v_{i,{\bf n}}$, and the summation is taken over all edges $e$ that connect $v_{i,{\bf n}}$ with some $v_{i^{\prime},{\bf n}^{\prime}}\in V(G)$, loops contributing twice.

We regard ${\cal L}_{G}$ with the discrete topology. Endowed with the compact-open topology, $\widehat{\cal L}_{G}$ is a compact space (see, for example, Section 2 of [19]). It admits a $\mathbb{Z}^{d}$-action by automorphisms. Such an action is a homomorphism ${\bf s}:{\bf n}\mapsto{\bf s}_{{\bf n}}$ from $\mathbb{Z}^{d}$ to the automorphism group of $\widehat{\cal L}_{G}$.

We denote $\widehat{\cal L}_{G}$ with its $\mathbb{Z}^{d}$-action by ${\rm Col}_{{\mathbb{T}},\mathbb{Z}^{d}}(G)$. It is an example of a dynamical system known as a $\mathbb{Z}^{d}$-shift. By the Pontryagin Duality Theorem we recover the Laplace module by taking the dual of ${\rm Col}_{{\mathbb{T}},\mathbb{Z}^{d}}(G)$. We will say more about the dynamical properties of $\widehat{\cal L}_{G}$ in Section 9.

In the case of a finite plane graph and its associated link diagram ($d=0$), their isomorphic groups of ${\mathbb{T}}$-colorings are dual respectively to the Laplacian group of the graph and the abelian core group of the link. The latter group is generated by the arcs of the diagram with relations given by the Fox coloring condition of Figure 5; it is well known to be isomorphic to the direct sum of the first homology group of the 2-fold branched cover of the link and an infinite cyclic group. (For more about such dynamical systems see [26, 19] or [29]. Information about the core group can be found in [30].)

A cycle-rooted spanning forest (CRSF) of $\overline{G}$ is a subgraph of $\overline{G}$ containing all of $\overline{V}$ such that each connected component has exactly as many vertices as edges and therefore has a unique cycle. The connection $\phi$ of an oriented cycle is its homology class in $H_{1}({\mathbb{T}}^{d};\mathbb{Z})\cong\mathbb{Z}^{d}$. See [15] for details.

The following is a consequence of the main theorem of [11]. It is made explicit in Theorem 5.2 of [15].

A $d$-periodic graph need not be connected. In fact, it can have countably many connected components. Nevertheless, the number of $\mathbb{Z}^{d}$-orbits of components, henceforth called component orbits, is necessarily finite.

When a plane graph $G$ is 1- or 2-periodic, the medial construction in Section 4 produces a diagram $D$ of an infinite link $\ell$. It has a finite quotient diagram $\overline{D}$ modulo the $\mathbb{Z}$- or $\mathbb{Z}^{2}$-action induced by the action on $G$.

For $d=1$ we regard $\overline{D}$ in an annulus $\mathbb{A}$. It describes a link $\overline{\ell}=\overline{\ell}_{1}\cup\cdots\cup\overline{\ell}_{\mu}$ in a solid unknotted torus $V$. The complement $({\rm int}\ V)\setminus\overline{\ell}$ is homeomorphic to ${\mathbb{S}}^{3}\setminus\hat{\ell}$, where $\hat{\ell}=\overline{\ell}\cup C$ is the link formed by the union of $\overline{\ell}$ with a meridian $C$ of $V$. The meridian acquires an orientation induced by the infinite cyclic action on $D$. It is easy to see that every link with an unknotted component that has even linking number with the rest of the link arises in this way.

The following result relates the Laplacian polynomial $\Delta_{G}$ to the Alexander polynomial $\Delta_{\hat{\ell}}$.

The next proposition characterizes the leading coefficient of the Laplacian polynomial of a plane 1-periodic graph in terms of ${\mathbb{T}}$-colorings of its associated link. We will use the notation in the proof of Theorem 8.1. Note that $\Delta_{G}(x)=\Delta_{G}(x^{-1})$, by Theorem 7.1.

The following corollary follows form Propositions 8.4 and 8.5.

When $G$ is a $d$-periodic graph with quotient $\overline{G}$, we can consider the intermediate covering graphs $G_{\Lambda}$ in $\mathbb{R}^{d}/{\Lambda}$, where ${\Lambda}\subset\mathbb{Z}^{d}$ is a subgroup of ${\Lambda}$ having finite index. In this section we see that the growth of the torsion complexity ${\kappa}_{G_{\Lambda}}$ as the index of ${\Lambda}$ goes to infinity is determined by the Mahler measure of the Laplacian polynomial $\Delta_{G}$.

We begin by reviewing the Mahler measure of polynomials.

We call this limit the complexity growth rate of $G$, and denote it by $\gamma_{G}$. Its relationship to the thermodynamic limit or bulk limit defined for a wide class of unsigned lattice graphs is discussed in [16], and also below in Section 11.

Before proving Theorem 9.3 we give an example that demonstrates the need for defining graph complexity as we do.

We proceed with the proof of Theorem 9.3.

In [17] D.H. Lehmer asked the following question.

Lehmer discovered the polynomial $x^{10}+x^{9}-x^{7}-x^{6}-x^{5}-x^{4}-x^{3}+x+1,$ which has Mahler measure equal to $1.17628...$. Despite great effort including extensive computer-aided searches [3, 4, 22, 23, 25], no smaller value greater than 1 has been found, and Lehmer’s question remains unanswered.

Topological and geometric perspectives of Lehmer’s question have been found [13]. In [31] we showed that Lehmer’s question is equivalent to a question about Alexander polynomials of fibered hyperbolic knots in the lens spaces $L(n,1),n>0$. (Lens spaces arose from the need to consider polynomials $f(x)$ with $f(1)=n\neq 1$.) Here we present another, more elementary equivalence, in terms of graph complexity.

An integer polynomial $f(x)$ is reciprocal if $x^{{\deg}f}f(x^{-1})=f(x)$. We will say that a Laurent polynomial $f(x)\in{\cal R}_{1}$ is palindromic if $f(x^{-1})=f(x)$. Any reciprocal polynomial becomes palindromic after it is multiplied by $x^{j}$ or $x^{j}(x+1)$, for suitable $j$. In [34] C. Smyth proved that any irreducible integral non-reciprocal polynomial other than $x$ or $x-1$ has Mahler measure at least as large as the real root of $x^{3}-x-1$ (approximately 1.324). Since Mahler measure is multiplicative, it suffices to restrict our attention to palindromic Laurent polynomials when investigating Lehmer’s question.

The cyclic 5-fold cover of the graph in Example 10.3 contains the complete graph on 5 vertices, and hence it is nonplanar. If the answer to the following question is yes, then Lehmer’s question is equivalent to a question about determinant density of links (see Remark 11.3(3)).

We conclude this section with a result that will be used in the next section, but holds for signed as well as unsigned graphs. It concerns complexity growth of a $d$-periodic graph that is a union of disjoint $d^{\prime}$-periodic graphs for some $d^{\prime}<d$.

Suppose $H$ is a subgraph of a $d$-periodic graph $G$ consisting of one or more connected components of $G$, such that the orbit of $H$ under $\mathbb{Z}^{d}$ is all of $G$. Let $\Gamma<\mathbb{Z}^{d}$ be the stabilizer of $H$. Then $\Gamma\cong\mathbb{Z}^{d^{\prime}}$ for some $d^{\prime}<d$, and its action on $H$ can be regarded as a cofinite free action of $\mathbb{Z}^{d^{\prime}}$. Consider the limit

where ${\Lambda}$ ranges over finite-index subgroups of $\Gamma$.