# Colored Tutte polynomials and composite knots

Gábor Hetyei¹†, Yuanan Diao¹‡ and Kenneth Hinson¹

¹ Department of Mathematics and Statistics, UNC Charlotte, Charlotte, NC 28223

**Abstract.** Surveying the results of three recent papers and some currently ongoing research, we show how a generalization of Brylawski's tensor product formula to colored graphs may be used to compute the Jones polynomial of some fairly complicated knots and, in the future, even virtual knots.

**Résumé.** En faisant une revue de trois articles récents et de la recherche en cours, nous montrons comment une généralisation aux graphes colorés de la formule de Brylawski sur le produit tensoriel peut être utilisée à calculer le polynôme de Jones de quelques nœuds et, dans la future, même de quelques nœuds virtuels, bien compliqués.

**Keywords:** knots, Jones polynomial, Tutte polynomial, signed graphs, tensor product of matroids

## Introduction

Tutte polynomials are known to be useful in the computation of the Jones polynomials of alternating knots. One of the most famous applications may be found in the work of Jaeger, Vertigan, and Welsh (11), where they use Brylawski's (3) tensor product formula to show that computing the Jones polynomial of even an alternating knot is NP-complete. The technique used also indicates the existence of large knots whose composite structure (their face graph being the tensor product of "manageable" graphs) allows the computation of their Jones polynomials using Brylawski's formula.

This presentation will take through the main results of three recent papers by the presenting authors which show how Brylawski's formula may be generalized to colored graphs, using a notion of a Tutte polynomial whose existence follows from the work of Bollobás and Riordan (1). The proof of the resulting formula indicates a new, Tutte-style proof of Brylawski's original result, and has many potential applications outside knot theory. As an example we indicate the application to the random-cluster model introduced by Fortuin and Kasteleyn (10).

The result should be generalizable to calculating the Jones polynomial of virtual knots (16) arising as a tensor product, however, for the moment, we only believe to have a suitable notion of a relative Tutte polynomial that allows to compute the Jones polynomial. Our research indicates that the theory of Tutte polynomials of morphisms of matroids, developed by Las Vergnas (17) is worth revisiting from the point of view of colored generalizations.

<footnote>†supported by NSA grant H98230-07-10073</footnote>

<footnote>‡supported by NSF grant DMS-0712958</footnote>
# 1 The Tutte polynomial of a colored graph

In this section we review our implementation of the colored Tutte polynomial, introduced by Bollobás and Riordan (1).

**Definition 1.1** Let $G$ be a connected graph with $n$ edges whose edges are labeled $1, 2, \dots, n$, and let $T$ be a spanning tree of $G$. An edge $e$ of $T$ is internally active if for any edge $f \neq e$ in $G$ such that $(T \setminus e) \cup f$ is a spanning tree of $G$, the label of $e$ is less than the label of $f$. Otherwise $e$ is internally inactive. An edge $f$ of $G \setminus T$ is externally active if $f$ has the smallest label among the edges in the unique cycle contained in $T \cup f$. Otherwise, $f$ is externally inactive.

Bollobás and Riordan (1) use Tutte's notion of activities but generalize Tutte's variable assignments as follows. Let $G$ be a colored and connected graph and $T$ a spanning tree of $G$. For each edge $e$ in $G$ with color $\lambda$, we assign one of the variables $X_\lambda, Y_\lambda, x_\lambda$ and $y_\lambda$ to it according to the activities of $e$ as shown below (with respect to the tree $T$):

<table><caption>**Tab. 1:** The variable assignment of an edge with respect to a spanning tree $T$.</caption><tr><td>internally active</td><td>$X_\lambda$</td><td>externally active</td><td>$Y_\lambda$</td></tr><tr><td>internally inactive</td><td>$x_\lambda$</td><td>externally inactive</td><td>$y_\lambda$</td></tr></table>

**Definition 1.2** Let $G$ be a connected colored graph (whose edges are labeled as in Definition 1.1). For a spanning tree $T$ of $G$, let $C(T)$ be the product of the variable contributions from each edge of $G$ according to the variable assignment above. The Tutte polynomial $T(G)$ is defined as the sum of $C(T)$ over all spanning trees $T$ of $G$.

Tutte's original variable assignment may be recovered by setting all $X_\lambda = x$, $Y_\lambda = y$, $x_\lambda = 1$ and $y_\lambda = 1$ for $\lambda \in \Lambda$. It is Tutte's main result (18) is that the total contribution of all spanning trees is labeling independent in the non-colored case. In the colored case, labeling independence is preserved only if the polynomial ring $\mathbb{Z}[\Lambda] := \mathbb{Z}[X_\lambda, Y_\lambda, x_\lambda, y_\lambda : \lambda \in \Lambda]$ is factored with an appropriate ideal $I$. The following theorem by Bollobás and Riordan (1) gives the exact description of all such ideals.

**Theorem 1.3 (Bollobás-Riordan)** Assume $I$ is an ideal of $\mathbb{Z}[\Lambda]$. Then the homomorphic image of $T(G)$ in $\mathbb{Z}[\Lambda]/I$ is independent of the labeling of the edges of $G$ if and only if for all $\lambda, \mu, \nu \in \Lambda$ the polynomials

$$ \det \begin{pmatrix} X_\lambda & y_\lambda \\ X_\mu & y_\mu \end{pmatrix} - \det \begin{pmatrix} x_\lambda & Y_\lambda \\ x_\mu & Y_\mu \end{pmatrix}, \quad Y_\nu \left( \det \begin{pmatrix} x_\lambda & Y_\lambda \\ x_\mu & Y_\mu \end{pmatrix} - \det \begin{pmatrix} x_\lambda & y_\lambda \\ x_\mu & y_\mu \end{pmatrix} \right), \\ \text{and } X_\nu \left( \det \begin{pmatrix} x_\lambda & Y_\lambda \\ x_\mu & Y_\mu \end{pmatrix} - \det \begin{pmatrix} x_\lambda & y_\lambda \\ x_\mu & y_\mu \end{pmatrix} \right) \text{ belong to } I. $$

Let $I_0$ be the ideal generated by the polynomials listed in Theorem 1.3. The image of $T(G)$ in $\mathbb{Z}[\Lambda]/I_0$ is the most general colored Tutte polynomial whose definition is independent of the labeling. Many important polynomials may be obtained from this polynomial by substitution, and most such substitutions, including all those we want to consider, map $\mathbb{Z}[\Lambda]/I_0$ into an integral domain in such a way that the images of the variables $x_\lambda, X_\lambda, y_\lambda$ and $Y_\lambda$ are nonzero. All such maps factor through the canonical map $\mathbb{Z}[\Lambda]/I_0 \to \mathbb{Z}[\Lambda]/I_1$, where $I_1 \supset I_0$ is the ideal generated by all polynomials of the forms
$\det \begin{pmatrix} X_\lambda & y_\lambda \\ X_\mu & y_\mu \end{pmatrix} - \det \begin{pmatrix} x_\lambda & y_\lambda \\ x_\mu & y_\mu \end{pmatrix}$ and $\det \begin{pmatrix} x_\lambda & y_\lambda \\ x_\mu & y_\mu \end{pmatrix} - \det \begin{pmatrix} x_\lambda & Y_\lambda \\ x_\mu & Y_\mu \end{pmatrix}$. This role of $I_1$ is implicitly noted in (1, Corollary 3). Thus we will consider the colored Tutte polynomial to be an element of $\mathbb{Z}[\Lambda]/I_1$. Let us highlight the following algebraic observation, making (1, Corollary 3) truly useful.

**Lemma 1.4 (Diao-Hetyei-Hinson)** *The ideal $I_1$ is a prime ideal. More generally, given any integral domain $R$, the ideal $I_1$ in $R[\Lambda]$ is prime.*

The proof of this lemma uses (2, Theorem (2.10)) stating that given any integral domain $R$ and a matrix $X$ of variables, the ideal generated by the maximal minors of $X$ in the polynomial ring $R[X]$ is prime.

As noted in (1, Remark 3), our definitions and statements may be generalized to *matroids* by modifying the definitions of activities using “matroid basis” instead of “spanning tree” and interpreting a “cycle” as a “minimal dependent set”. By replacing the phrase “spanning tree” with “spanning forest”, one can easily generalize our Tutte polynomial to *disconnected graphs*. Given a disconnected graph $G$ with connected components $G_1, \dots, G_k$, the Tutte polynomial $T(G)$ obtained via this generalization is simply the product of the Tutte polynomials of its components: $T(G) = \prod_{i=1}^k T(G_i)$. On the other hand, Bollobás and Riordan (1) introduced a different generalized form of a Tutte polynomial by multiplying a variable $\alpha_{k(G)}$ (that only depends on the number $k(G)$ of connected components in $G$) with $T(G)$. This allows one to keep track of the number of connected components. For details we refer the reader to (1, Corollary 4). Here we only highlight the following consequence.

**Corollary 1.5** Let $\mathbb{Z}_{\Lambda,\alpha}$ be the polynomial ring $\mathbb{Z}_{\Lambda}[\alpha_i : i = 1, 2, \dots]$, then the polynomial $\alpha_{k(G)}T(G)$, considered as an element of $\mathbb{Z}_{\Lambda,\alpha}/I_1$ is labeling independent.

To avoid confusion, we will refer to $T(G)$ as the *ordinary* Tutte polynomial of the colored graph, and to $\alpha_{k(G)}T(G)$ as the *enriched* Tutte polynomial of $G$. The ordinary Tutte polynomial may be obtained from the enriched Tutte polynomial by sending all variables $\alpha_i$ to 1. Using the same $I_1$ to denote the ideal generated by the same elements in different rings will not cause confusion.

## 2 The signed Tutte polynomial and the Jones polynomial

The special case when the color set has two colors, referred to as *signs*, the resulting signed Tutte polynomial may be used to compute the Kauffman bracket and the Jones polynomial of a knot. Here we only outline this well-known construction, the details may be found in (1), (14), and (15). Kauffman's uses different letters to denote his variables, inactive edges correspond to variables $A_+$, $A_-$, $B_+$, $B_-$, active edges correspond to $x_+$, $x_-$, $y_+$, and $y_-$.

A full concordance between Kauffman's (14), (15) and the Bollobás-Riordan notation (1) is given in Table 2.

<table><caption>**Tab. 2:** Concordance between the Kauffman and the Bollobás-Riordan notations</caption><tr><td>Kauffman</td><td>ε</td><td>ε<sub>i</sub></td><td>x<sub>ε</sub></td><td>y<sub>ε</sub></td><td>A<sub>ε</sub></td><td>B<sub>ε</sub></td></tr><tr><td>Bollobás-Riordan</td><td>λ</td><td>λ<sub>i</sub></td><td>X<sub>λ</sub></td><td>Y<sub>λ</sub></td><td>x<sub>λ</sub></td><td>y<sub>λ</sub></td></tr></table>

Consider a regular projection $D$ of a knot $K$. We shade the regions of $D$ either “white” or “dark” in a checkerboard fashion, so that no two regions of the same color are adjacent. We usually consider the infinite region surrounding the knot projection to be white. Next we construct a dual graph of $D$ by converting the dark regions in $D$ into vertices in a graph $G$ and converting the crossings in $D$ between
two dark regions into edges incident to the corresponding vertices in G. We look at each crossing in the knot projection. If, after the upper strand passes over the lower, the dark region is to the left of the upper strand, then we denote this as a positive crossing, otherwise we denote it as a negative crossing. Then our signed graph is obtained by marking each edge of G with the same sign as the crossing of K to which it corresponds. See Figure 1 below and Figure 2 in Section 4.

<figure><img src="image_1.png" /><figcaption>Fig. 1: The assignment of signs at a crossing (vertex) for the graph G.</figcaption></figure>

The following theorem is due to Kauffman (14; 15).

**Theorem 2.1** Let G be the (signed) dual graph of a regular knot projection D of K as described above, then T(G) equals the Kauffman bracket polynomial $\langle K \rangle$ under the following variable substitutions:

$$ 
\begin{aligned}
x_+ &\mapsto -A^{-3}, & x_- &\mapsto -A^3, & y_+ &\mapsto -A^3, & y_- &\mapsto -A^{-3} \\
A_+ &\mapsto A, & A_- &\mapsto A^{-1}, & B_+ &\mapsto A^{-1}, & B_- &\mapsto A.
\end{aligned}
$$

Furthermore, the Jones polynomial $V_K(t)$ of K can be obtained from

$$ V_K(t) = (-A^{-3})^{w(K)} \langle K \rangle \quad (1) $$

by setting $A = t^{-1/4}$, where $w(K)$ is the writhe of the projection D.

A regular projection D of a knot is alternating if all edges of the corresponding graph G have the same sign (w.l.o.g positive). A regular knot projection is alternating if and only if each “overcorssing” is followed by an “undercrossing” and vice versa, motivating the choice of the name. As a consequence of Theorem 2.1, the Jones polynomial of an alternating knot may be computed from the (original) Tutte polynomial of a (non-colored) graph.

## 3 Brylawski's tensor product formula and its signed generalization

The tensor product of colored graphs we introduce in this section is a colored generalization of the tensor product operation introduced by Brylawski (3) for (non-colored) matroids. The matroid generalization of the definition below is obvious.

**Definition 3.1** Let M and N be two graphs colored with the set $\Lambda$, $\lambda \in \Lambda$ a fixed color, and e a distinguished edge of N that is neither a loop nor a bridge. The $\lambda$-tensor product of M and N, denoted by $M \otimes_{\lambda} N$ is the colored graph obtained by replacing each edge in M of color $\lambda$ with a copy of N \ e, where the distinguished edge e is to be identified with the replaced edge of M.

We may recover Brylawski's original definition for $M \otimes N$ by setting $|\Lambda| = 1$. Brylawski's formula (3) was rephrased in the famous paper of Jaeger, Vertigan and Welsh (11) as follows.
**Theorem 3.2 (Brylawski)** *The Tutte polynomial of $M \otimes N$ is given by*

$$T(M \otimes N; x, y) = T_C(N; x, y)^{|S|-\mathrm{rank}(S)} T_L(N; x, y)^{\mathrm{rank}(S)} T(M; X, Y) \quad \text{where}$$

$$X = \frac{(x-1)T_C(N; x, y) + T_L(N; x, y)}{T_L(N; x, y)}, \quad Y = \frac{T_C(N; x, y) + (y-1)T_L(N; x, y)}{T_C(N; x, y)},$$

and the polynomials $T_C$ and $T_L$ are defined by the equations

$$\begin{aligned} (x-1)T_C(N; x, y) + T_L(N; x, y) &= T(N \setminus e; x, y), \\ T_C(N; x, y) + (y-1)T_L(N; x, y) &= T(N/e; x, y). \end{aligned} \qquad (2)$$

Here, and from now on, $N \setminus e$ resp. $N/e$ stands for the graph or matroid obtained after the deletion resp. contraction of $e$.

Brylawski's result was used by Jaeger, Vertigan and Welsh (11) to show that the computation of the Tutte polynomial and of the Jones polynomial of an alternating knot is NP-complete. Finding a generalization of the tensor product formula stated in Theorem 3.2 allows to compute the Jones polynomials of large non-alternating knots that have a regular projection whose associated graph arises as a tensor product of signed graphs of "manageable size".

For this purpose we first define a colored generalization of the polynomials $T_C$ and $T_L$ that appear in Theorem 3.2.

**Definition 3.3** Let $N$ be a colored connected graph with a distinguished edge $e$ that is neither a loop nor a bridge. Then $T_L(N, e)$ is the polynomial defined by the same rule that defines the ordinary colored Tutte polynomial $T(N \setminus e)$ except that internally active edges on a cycle closed by $e$ will be considered as internally inactive instead. Similarly, $T_C(N, e)$ is the polynomial defined by the same rule that defines the ordinary colored Tutte polynomial $T(N/e)$ except that externally active edges that would close a cycle containing $e$ will be considered as externally inactive instead.

To interpret the second part of the definition, note that the spanning trees of $N/e$ are identifiable with those spanning trees of $N$ which contain $e$. We say that an external edge closes a cycle containing $e$ with a spanning tree $T$ of $N/e$, if the same holds for the corresponding spanning tree $T \cup \{e\}$ of $N$.

Definition 3.3 appears to depend on the labeling of the edges, but it is not, because of the following result (7):

**Theorem 3.4 (Diao-Hetyei-Hinson)** Let $N$ be a colored graph with a distinguished edge $e$ that is neither a loop nor a bridge and let $\lambda \in \Lambda$ be any color. Then the following two equalities hold:

$$x_{\lambda}(T(N/e) - T_C(N, e)) = (Y_{\lambda} - y_{\lambda})T_L(N, e), \qquad (3)$$

$$y_{\lambda}(T(N \setminus e) - T_L(N, e)) = (X_{\lambda} - x_{\lambda})T_C(N, e). \qquad (4)$$

As a consequence of Theorem 3.4 the pair of polynomials $z_C = T_C(N, e)$ and $z_L = T_L(N, e)$ provides a solution of the linear system of equations

$$\begin{aligned} (Y_{\lambda} - y_{\lambda})z_{L} + x_{\lambda}z_{C} &= x_{\lambda}T(N/e) \\ y_{\lambda}z_{L} + (X_{\lambda} - x_{\lambda})z_{C} &= y_{\lambda}T(N \setminus e) \end{aligned} \qquad (5)$$
for the unknowns $z_L$ and $z_C$. The givens belong to $\mathbb{Z}[\Lambda]/I_1$, an integral domain by Lemma 1.4. Cramer's rule is applicable in the quotient field of $\mathbb{Z}[\Lambda]/I_1$, and we have

$$ \det \begin{pmatrix} Y_{\lambda} - y_{\lambda} & x_{\lambda} \\ y_{\lambda} & X_{\lambda} - x_{\lambda} \end{pmatrix} = X_{\lambda}Y_{\lambda} - X_{\lambda}y_{\lambda} - y_{\lambda}X_{\lambda} $$

which is a nonzero element of $\mathbb{Z}[\Lambda]/I_1$, independent of the choice of $\lambda$, since each element of $I_1$ is a $\mathbb{Z}$-linear combination of monomials involving at least two colors from $\Lambda$. Thus the solution of (5) is unique and definition of $T_C(N, e)$ and $T_L(N, e)$ is in deed independent of the labeling. The proof of Theorem 3.4 greatly depends on the following algebraic formula (7):

**Lemma 3.5** The following identities hold in the ring $\mathbb{Z}[\Lambda]/I_1$ for all $k \ge 1$ and all $\lambda, \lambda_1, \dots, \lambda_k \in \Lambda$ (all empty products are treated as 1):

$$ x_{\lambda} \left( \prod_{i=1}^{k} Y_{\lambda_i} - \prod_{i=1}^{k} y_{\lambda_i} \right) = (Y_{\lambda} - y_{\lambda}) \sum_{i=1}^{k} x_{\lambda_i} \prod_{j=1}^{i-1} Y_{\lambda_j} \prod_{t=i+1}^{k} y_{\lambda_t} \quad (6) $$

$$ y_{\lambda} \left( \prod_{i=1}^{k} X_{\lambda_i} - \prod_{i=1}^{k} x_{\lambda_i} \right) = (X_{\lambda} - x_{\lambda}) \sum_{i=1}^{k} y_{\lambda_i} \prod_{j=1}^{i-1} X_{\lambda_j} \prod_{t=i+1}^{k} x_{\lambda_t}. \quad (7) $$

Note that the second equation in Lemma 3.5 follows from the first by exchanging each $x_{\lambda}$ with $y_{\lambda}$ and each $X_{\lambda}$ with $Y_{\lambda}$. The equations in Theorem 3.4 may be rephrased as follows.

$$ \det \begin{pmatrix} T_L(N, e) & T_C(N, e) \\ x_{\lambda} & y_{\lambda} \end{pmatrix} = \det \begin{pmatrix} T_L(N, e) & T(N/e) \\ x_{\lambda} & Y_{\lambda} \end{pmatrix} \quad (8) $$

and

$$ \det \begin{pmatrix} T_L(N, e) & T_C(N, e) \\ x_{\lambda} & y_{\lambda} \end{pmatrix} = \det \begin{pmatrix} T(N \setminus e) & T_C(N, e) \\ X_{\lambda} & y_{\lambda} \end{pmatrix} \quad (9) $$

Using this determinantal form it is easy to show the following (7):

**Lemma 3.6 (Diao-Hetyei-Hinson)** The endomorphism of $\mathbb{Z}[\Lambda]$, given by $X_{\lambda} \mapsto T(N \setminus e)$, $x_{\lambda} \mapsto T_L(N, e)$, $Y_{\lambda} \mapsto T(N/e)$, $y_{\lambda} \mapsto T_C(N, e)$ and by $X_{\mu} \mapsto X_{\mu}$, $x_{\mu} \mapsto x_{\mu}$, $Y_{\mu} \mapsto Y_{\mu}$, $y_{\mu} \mapsto y_{\mu}$ for all $\mu \ne \lambda$, sends $I_1$ into itself.

This lemma allows us to state our main result on the tensor product of colored graphs (and matroids) as follows (7):

**Theorem 3.7** Let $M$ be a colored graph and $N$ a colored graph with a distinguished edge $e$ that is neither a loop nor a bridge. Then the ordinary Tutte polynomial $T(M \otimes_{\lambda} N)$ can be computed from $T(M)$ by keeping all variables of color $\mu \ne \lambda$ unchanged, and using the substitutions $X_{\lambda} \mapsto T(N \setminus e)$, $x_{\lambda} \mapsto T_L(N, e)$, $Y_{\lambda} \mapsto T(N/e)$, $y_{\lambda} \mapsto T_C(N, e)$.

**Remark 3.8** For non-colored graphs and matroids our reasoning may be substantially simplified. Thus, in (9), we obtained a new, “Tutte-style” proof of Brylawski’s original result (3).
# 4 Applications and non-connected generalizations of the colored tensor product formula

The first important specialization of Theorem 3.7 is the case of signed graphs. Using Kauffman’s notation, in this special case Theorem 3.7 may be restated as follows (6):

**Theorem 4.1** Let $M$ be a signed graph and $N$ a signed graph with a distinguished edge $e$. Then $T(M \otimes_+ N)$ can be computed from $T(M)$ by keeping the negative variables unchanged and using the substitutions

$$x_+ \mapsto T(N\setminus e) \quad A_+ \mapsto T_L(N, e) \quad y_+ \mapsto T(N/e) \quad B_+ \mapsto T_C(N, e).$$

Similarly, $T(M \otimes_- N)$ can be computed from $T(M)$ by keeping the positive variables unchanged and using the substitutions

$$x_- \mapsto T(N\setminus e) \quad A_- \mapsto T_L(N, e) \quad y_- \mapsto T(N/e) \quad B_- \mapsto T_C(N, e).$$

Theorem 4.1 allowed us to compute the Jones polynomial of the non-alternating knot shown in Figure 2 in (6). “Historically,” the computation of this Jones polynomial was the challenge that motivated all our results presented here.

<figure><img src="image_2.png" /><figcaption>**Fig. 2:** A 19 crossing knot diagram and its corresponding signed graph.</figcaption></figure>

The generalization of Theorem 3.7 to enriched Tutte polynomials of disconnected graphs is discussed in (7). The number $k(M \otimes_\lambda N)$ of connected components of $M \otimes_\lambda N$ satisfies the equation

$$k(M \otimes_\lambda N) = k(M) + |E_\lambda(M)| \cdot (k(N \setminus e) - 1). \quad (10)$$

Here $E_\lambda(M)$ is the set of edges of color $\lambda$ in $M$. The enriched Tutte polynomial of $M \otimes_\lambda N$ is thus equal to

$$\alpha_{k(M)+|E_\lambda(M)| \cdot (k(N\setminus e)-1)} \cdot T(M \otimes_\lambda N),$$

where $T(M \otimes_\lambda N)$ is the ordinary colored Tutte polynomial, to which Theorem 3.7 is applicable. In particular, substituting $k(N \setminus e) = 1$ into (10) yields $k(M \otimes_\lambda N) = k(M)$ thus we have the following consequence.
**Corollary 4.2** Let $M$ be a colored graph and $N$ a colored graph with a distinguished edge $e$ that is neither a loop nor a bridge. Assume that $N \setminus e$ is connected. Then the enriched Tutte polynomial of $M \otimes_{\lambda} N$ can be computed from the enriched Tutte polynomial of $M$ by keeping all variables of color $\mu \neq \lambda$ and the variables $\alpha_n$ ($n \ge 1$) unchanged, and using the substitutions

$$X_{\lambda} \mapsto T(N \setminus e) \quad x_{\lambda} \mapsto T_{L}(N, e) \quad Y_{\lambda} \mapsto T(N/e) \quad y_{\lambda} \mapsto T_{C}(N, e).$$

Corollary 4.2 may be applied to the random-cluster model introduced by Fortuin and Kasteleyn (10) in 1972 as a generalization of various models such as the percolation model, the two-state Ising model and the Potts model. This model can be thought of as a graph $G(V, E)$ that is associated with a function $p: E \to [0, 1]$. We may think of $p_e$ as the probability that the edge $e \in E$ “survives” an accident, and $q_e = 1 - p_e$ as the probability that the edge $e$ “breaks” in an accident. Fortuin and Kasteleyn (10) introduced the following polynomial of the variable $\kappa$ as a cluster-generating function $Z(G; p, \kappa)$:

$$Z(G; p, \kappa) = \sum_{C \subseteq E} p^C q^{E \setminus C} \kappa^{k(C)}. \qquad (11)$$

Here $p^C$ is a shorthand for the product $\prod_{e \in C} p_e$, $q^{E \setminus C}$ is a shorthand for the product $\prod_{e \in E \setminus C} q_e$, and $k(C)$ is the number of connected components in the subgraph consisting of the edges of $C$ and the vertices incident to these edges. Bollobás and Riordan (1) have shown that the polynomial $Z(G; p, \kappa)$ can be computed from the enriched Tutte polynomial of a colored graph. We may think of the colors as different “materials” and assume that edges of the same color have the same probability to “break” in an accident. After computing the Tutte polynomial of the colored graph, we have to make the following substitutions (as directed in (1)):

$$x_{\lambda} \mapsto p_{\lambda} \quad y_{\lambda} \mapsto q_{\lambda} \quad X_{\lambda} \mapsto p_{\lambda} + \kappa q_{\lambda} \quad Y_{\lambda} \mapsto 1. \qquad (12)$$

Corollary 4.2 becomes applicable when our network is a “network of networks” $M \otimes_{\lambda} N$, i.e. when the edges of color $\lambda$ of a network $M$ are networks themselves, associated to the same colored graph $N$ with a distinguished edge $e$ indicating how $N \setminus e$ should be inserted as a substitute of $e \in M$.

**Definition 4.3** Let $N$ be a colored graph with a distinguished edge $e$ that is neither a loop nor a bridge, such that each color $\lambda$ has an associated probability $p_{\lambda}$. We define the pointed random-cluster-generating functions $Z_C(N, e; p, \kappa)$ and $Z_L(N, e; p, \kappa)$ as the homomorphic images of $T_C(N, e)$ and $T_L(N, e)$ respectively under the homomorphism induced by the substitutions given in (12).

As a consequence of Corollary 4.2 and the substitution rule (12) we have the following result.

**Theorem 4.4** Let $M$ and $N$ be colored graphs and $p$ a function associating to each color a probability. Assume $N$ has a distinguished edge $e$ that is neither a loop nor a bridge, and that $N \setminus e$ is connected. Let $\lambda$ be a fixed color. Then the cluster-generating function $Z(M \otimes_{\lambda} N; p, \kappa)$ may be obtained from the enriched colored Tutte polynomial $\alpha_{k(M)} T(M)$ by sending $\alpha_n$ into $\kappa^n$ and making the following substitutions:

$$X_{\lambda} \mapsto Z(N \setminus e; p, \kappa) \quad x_{\lambda} \mapsto Z_{L}(N, e; p, \kappa) \quad Y_{\lambda} \mapsto Z(N/e; p, \kappa) \quad y_{\lambda} \mapsto Z_{C}(N, e; p, \kappa).$$

For all other colors $\mu$ we apply the substitutions given in (12).

It was shown in (7) that the pointed random cluster generating functions $Z_C(N, e; p, \kappa)$ and $Z_L(N, e; p, \kappa)$ may be equivalently given by

$$Z_C(N, e; p, \kappa) = \frac{Z(N \setminus e; p, \kappa) - Z(N/e; p, \kappa)}{\kappa - 1} \quad \text{and} \qquad (13)$$
$$Z_L(N, e; p, \kappa) = \frac{\kappa Z(N/e; p, \kappa) - Z(N \setminus e; p, \kappa)}{\kappa - 1} \qquad (14)$$

# 5 Relative Tutte polynomials and virtual knots

Kauffman (16) has generalized the Jones polynomial to virtual knot diagrams which may be thought of as knot diagrams drawn on nontrivial surfaces. These drawings may be represented in the plane by allowing a few “virtual” crossings: crossings that do not exist on the surface only in the plane, due to two distinct points of the surface being represented by the same point in the plane. We may then apply the process of associating a signed graph as outlined in Section 2 with the additional rule that “virtual crossings” correspond to zero colored edges. An example is shown in Figure 3. If we wanted to extend Theorem 3.7

<figure><img src="image_3.png" /><figcaption>Fig. 3: The virtual trefoil knot (which is not checkerboard colorable) and its face graph.</figcaption></figure>

to virtual knots, we would first need some computational rule expressing the Jones polynomial of a virtual knot (as defined by Kauffman (16)) in terms of the Tutte polynomial of the 3-colored graph associated to the virtual knot diagram. Unfortunately, the “zero” edges do not abide to the same deletion-contraction rules as the other edges. There have been some efforts to overcome this difficulty. These efforts so far seem to concentrate on changing the underlying graph to a “ribbon graph” so that the “zero edges” would go away (5; 12; 13). This approach only applies to those virtual link diagrams that are “checkerboard colorable”. Figure 3 shows the virtual trefoil, which is not checkerboard colorable.

To overcome the difficulty, a theory of relative Tutte polynomials was developed in (8).

**Definition 5.1** Let $G$ be a connected graph and $\mathcal{H}$ a subset of its edge set $E(G)$. A subset $C$ of the edge set $E(G) \setminus \mathcal{H}$ is called a contracting set of $G$ with respect to $\mathcal{H}$ if $C$ contains no cycles and $\mathcal{D} := E(G) \setminus (C \cup \mathcal{H})$ contains no cocycles (and $\mathcal{D}$ is called a deleting set).

**Lemma 5.2 (Diao-Hetyei)** In the above definition, if $\mathcal{H} = \emptyset$, then $C \subseteq E(G)$ is a contracting set if and only if the subgraph $C$ is a spanning tree of $E(G)$.

For the sake of matroid-theoretic generalizations, the following observation is useful.

**Lemma 5.3 (Diao-Hetyei)** $C$ is a contracting set with respect to $\mathcal{H}$ if and only if there is a basis $B \subset C \cup \mathcal{H}$ that contains $C$.

**Lemma 5.4 (Diao-Hetyei)** Let $G$ be a connected graph and $\mathcal{H}$ a subset of $E(G)$. Let $C$ be a contracting set of $G$ with respect to $\mathcal{H}$, $\mathcal{D}$ be the corresponding deleting set and $e \in C$ be any edge in $C$. Then for any $f \in \mathcal{D}$, $C' = \{f\} \cup (C \setminus \{e\})$ is also a contracting set with respect to $\mathcal{H}$ if the triplet $(C, e, f)$ has either of the following properties:

(i) $C \cup \{f\}$ contains a cycle containing $\{e\}$.
(ii) $\mathcal{D} \cup \{e\}$ contains a cocycle containing $\{f\}$.

Moreover, if the triplet $(C, e, f)$ satisfies (i) or (ii) then the triplet $(C', f, e)$ has the same properties.

**Definition 5.5** Let $G$ be a connected graph and $\mathcal{H}$ be a subset of $E(G)$. Let us assume that a labeling of $G$ is given in such a way that all edges in $\mathcal{H}$ are labeled with number 0 and all other edges are labeled with distinct positive integers. Such a labeling is called a proper labeling or a relative labeling (with respect to $\mathcal{H}$). In other words, a proper labeling of the edges of $G$ with respect to $\mathcal{H}$ is a mapping $\phi: E(G) \to \mathbb{Z}$ such that $\phi(e) = 0$ for any $e \in \mathcal{H}$ and $\phi$ is an injective map from $E(G) \setminus \mathcal{H}$ to $\mathbb{Z}^+$. We say that $e_1$ is larger than $e_2$ if $\phi(e_1) > \phi(e_2)$. Let $\mathcal{C}$ be a contracting set of $G$ with respect to $\mathcal{H}$, then

a) an edge $e \in \mathcal{C}$ is called internally active if $\mathcal{D} \cup \{e\}$ contains a cocycle $D_0$ in which $e$ is the smallest edge, otherwise it is internally inactive.

b) an edge $f \in \mathcal{D}$ is called externally active if $\mathcal{C} \cup \{f\}$ contains a cycle $C_0$ in which $f$ is the smallest edge, otherwise it is externally inactive.

**Definition 5.6** Let $\psi$ be a mapping defined on the isomorphism classes of finite connected graphs with values in a ring $\mathcal{R}$. We say that $\psi$ is a block invariant if for all positive integer $n$ there is a function $f_n: \mathcal{R}^n \to \mathcal{R}$ that is symmetric under permuting its input variables such that for any connected graph $G$ having $n$ blocks $G_1, \dots, G_n$ we have

$$ \psi(G) = f_n(\psi(G_1), \dots, \psi(G_n)). $$

In other words, we require the ability to compute $\psi(G)$ from the value of $\psi$ on the blocks of $G$, and this computation should not depend on the order in which the blocks are listed.

**Lemma 5.7 (Diao-Hetyei)** Let $G$ be a connected graph and $\mathcal{H}$ be a subset of $E(G)$. Assume that $\mathcal{C}$ is a contracting set with respect to $\mathcal{H}$ and that the triplet $(C, e, f)$ has at least one of the properties listed in Lemma 5.4. Let $\mathcal{C}' := (\mathcal{C} \cup \{f\}) \setminus \{e\}$. Then the multiset of blocks of $\mathcal{H}_\mathcal{C}$ is the same as the multiset of blocks of $\mathcal{H}_{\mathcal{C}'}$.

Similarly, for matroids we have:

**Lemma 5.8 (Diao-Hetyei)** Let $M$ be a matroid and $\mathcal{H}$ a subset of its elements. Assume that $\mathcal{C}$ is a contracting set with respect to $\mathcal{H}$ and that the triplet $(C, e, f)$ has at least one of the properties listed in Lemma 5.4. Let $\mathcal{C}' := (\mathcal{C} \cup \{f\}) \setminus \{e\}$. Then the cycle matroid of the graph $\mathcal{H}_\mathcal{C}$ is the same as the cycle matroid of the graph $\mathcal{H}_{\mathcal{C}'}$.

Let $G$ be a connected graph and $\mathcal{H} \subseteq E(G)$. Assume we are given a mapping $c$ from $E(G) \setminus \mathcal{H}$ to a color set $\Lambda$. Assume further that $\psi$ is a block invariant associating an element of a fixed integral domain $\mathcal{R}$ to each connected graph. For any contracting set $\mathcal{C}$ of $G$ with respect to $\mathcal{H}$, let $\mathcal{H}_\mathcal{C}$ be the graph obtained by deleting all edges in $\mathcal{D}$ and contracting all edges in $\mathcal{C}$ (so that the only edges left in $\mathcal{H}_\mathcal{C}$ are the zero edges). Finally, we will assign a proper labeling to the edges of $G$. We now define the relative Tutte polynomial of $G$ with respect to $\mathcal{H}$ and $\psi$ as

$$ T_{\mathcal{H}}^{\psi}(G) = \sum_{\mathcal{C}} \left( \prod_{e \in G \setminus \mathcal{H}} w(G, c, \phi, \mathcal{C}, e) \right) \psi(\mathcal{H}_{\mathcal{C}}) \in \mathcal{R}[\Lambda], \qquad (15) $$

where the summation is taken over all contracting sets $\mathcal{C}$ and $w(G, c, \phi, \mathcal{C}, e)$ is the weight of the edge $e$ with respect to the contracting set $\mathcal{C}$, which is defined as (assume that $e$ has color $\lambda$):
$$w(G, c, \phi, \mathcal{C}, e) = \begin{cases} X_{\lambda} & \text{if } e \text{ is internally active;} \\ Y_{\lambda} & \text{if } e \text{ is externally active;} \\ x_{\lambda} & \text{if } e \text{ is internally inactive;} \\ y_{\lambda} & \text{if } e \text{ is externally inactive.} \end{cases} \qquad (16)$$

To simplify the notation somewhat, we will be using $T_H(G)$ for $T_H^\psi(G)$, with the understanding that some $\psi$ has been chosen, unless there is a need to stress what $\psi$ really is. Following (1), we then write

$$W(G, c, \phi, \mathcal{C}) = \prod_{e \in G \setminus \mathcal{H}} w(G, c, \phi, \mathcal{C}, e)$$

so that

$$T_{\mathcal{H}}(G, \phi) = \sum_{\mathcal{C}} W(G, c, \phi, \mathcal{C}) \psi(\mathcal{H}_{\mathcal{C}}). \qquad (17)$$

We may now extend Theorem 1.3 of Bollobás and Riordan (1) to $T_H$ as follows.

**Theorem 5.9 (Diao-Hetyei)** Assume $I$ is an ideal of $\mathcal{R}[\Lambda]$. Then the homomorphic image of $T_H(G, \phi)$ in $\mathcal{R}[\Lambda]/I$ is independent of $\phi$ (for any $G$ and $\psi$) if and only if for all $\lambda, \mu \in \Lambda$ the polynomials $\det \begin{pmatrix} X_{\lambda} & y_{\lambda} \\ X_{\mu} & y_{\mu} \end{pmatrix} - \det \begin{pmatrix} x_{\lambda} & Y_{\lambda} \\ x_{\mu} & Y_{\mu} \end{pmatrix}$ and $\det \begin{pmatrix} x_{\lambda} & Y_{\lambda} \\ x_{\mu} & Y_{\mu} \end{pmatrix} - \det \begin{pmatrix} x_{\lambda} & y_{\lambda} \\ x_{\mu} & y_{\mu} \end{pmatrix}$ belong to $I$.

Using Theorem 5.9 it is possible to define a relative Tutte polynomial that may be used to compute the Jones polynomial of a virtual knot. For details see (8, Section 5).

# 6 Concluding remarks

The immediate goal prompted by Theorem 5.9 is to extend the tensor product formula for colored graphs to relative Tutte polynomials and we are currently working on such an extension. It is worth observing that for graphs, our relative Tutte polynomial generalizes the *set-pointed* Tutte polynomial of matroids introduced and discussed in (17). Looking into results on that invariant with the purpose of further signed generalizations seems a worthwhile project. The ideal $I_1$ introduced in Section 1 is a *determinantal ideal*, and Gröbner basis theory is known to be useful in the theory of such ideals. Thus it is conceivable that Gröbner basis theory may be used to develop new or improve on existing algorithms to compute the Jones polynomial.

# Acknowledgements

The authors wish to thank Professor Thomas G. Lucas for providing the main idea behind Lemma 1.4 and to Professor Douglas West for useful information on graph operations.

# References

[1] B. Bollobás and O. Riordan, *A Tutte polynomial for coloured graph*, Combinatorics, Probability and Computing **8** (1999), 45–93.
[2] W. Bruns, U. Wetter, *Determinantal rings*, Springer Lecture Notes in Mathematics # 1327, Springer-Verlag Berlin-Heidelberg 1988.

[3] T. Brylawski, *The Tutte polynomial I: general theory*, in: Matroid Theory and its Applications, ed. A. Barlotti, Liguori Editore, S.r.l, 1982, 125-275.

[4] Brylawski and Oxley, *The Tutte polynomial and its applications*, Matroid Applications (ed. N. White), Cambridge University Press (1992), 123-225.

[5] S. Chmutov and I. Pak, *The Kauffman Bracket of Virtual Links and the Bolloás-Riordan Polynomial*, to appear in the Moscow Mathematical Journal. Preprint arXiv:math.GT/0609012.

[6] Y. Diao, G. Hetyei and K. Hinson, *Tutte polynomials of tensor products of signed graphs and their applications in knot theory*, to appear in J. Knot Theory Ramification. Preprint ArXiv:math/0702328.

[7] Y. Diao, G. Hetyei and K. Hinson, *Invariants of composite networks arising as a tensor product*, to appear in Graphs and Combinatorics. Preprint http://www.math.uncc.edu/preprint/2007/2007_08.pdf.

[8] Y. Diao and G. Hetyei, *Relative Tutte Polynomials for Colored Graphs and Virtual Knot Theory*. Preprint http://www.math.uncc.edu/preprint/2008/2008_06.pdf.

[9] Y. Diao, G. Hetyei and K. Hinson, *A Tutte-style proof of Brylawski's tensor product formula*, preprint, to appear in special issue of the European Journal of Combinatorics, honoring Thomas Brylawski. Preprint http://www.math.uncc.edu/preprint/2008/2008_15.pdf.

[10] C. M. Fortuin and P. W. Kasteleyn, *On the random-cluster model I*. Introduction and Relation to Other Models, Physica 57 (1972), 536-564.

[11] F. Jaeger, D.L. Vertigan and D.J.A. Welsh, *On the computational complexity of the Jones and Tutte polynomials*, Mathematical Proceedings of the Cambridge Philosophical Society 108 (1990), 35-53.

[12] N. Kamada, *On the Jones polynomials of checkerboard colorable virtual links*, Osaka J. Math. 39 (2002), 325-333.

[13] N. Kamada, *Span of the Jones polynomial of an alternating virtual link*, Algebraic & Geometric Topology 4 (2004), 1083-1101.

[14] L.H. Kauffman, *New invariants in the theory of knots*, American Mathematical Monthly 95 (3) (1988), 195-242.

[15] L.H. Kauffman, *A Tutte polynomial for signed graphs*, Discrete Applied Mathematics 25 (1989), 105-127.

[16] L.H. Kauffman, *Virtual knot theory*, European J. Combin. 20 (7) (1999), 663-690.

[17] M. Las Vergnas, *The Tutte polynomial of a morphism of matroids I. Set-pointed matroids and matroid perspectives*, Ann. Inst. Fourier 49 (3) (1999), 973-1015.

[18] W.T. Tutte, *A contribution to the theory of chromatic polynomials*, Canadian Journal of Mathematics 6 (1954), 80-91.