Research ContributionArnold Mathematical Journal

Received: 8 December 2014 / Revised: 29 June 2015 / Accepted: 5 July 2015

# Bollobás–Riordan and Relative Tutte Polynomials

Clark Butler Department of Mathematics University of Chicago 5734 University Avenue Chicago IL 60637-1514 USA, The Ohio State University – Mansfield 1760 University Drive Mansfield OH 44906 USA    Sergei Chmutov Department of Mathematics University of Chicago 5734 University Avenue Chicago IL 60637-1514 USA, The Ohio State University – Mansfield 1760 University Drive Mansfield OH 44906 USA

### Abstract

We establish a relation between the Bollobás–Riordan polynomial of a ribbon graph with the relative Tutte polynomial of a plane graph obtained from the ribbon graph using its projection to the plane in a nontrivial way. Also we give a duality formula for the relative Tutte polynomial of dual plane graphs and an expression of the Kauffman bracket of a virtual link as a specialization of the relative Tutte polynomial.

###### Keywords
Graphs on surfaces, Ribbon graphs, Bollobás-RiordanpolynomialTutte polynomial, DualityKauffman bracket

## 1 Introduction

Given a graph on a surface, we will construct a special associated plane graph which contains all of the topological information coming from the embedding of the graph into the surface. These constructed plane graphs usually have some extra (distinguished) edges and extra vertices. They are called relative plane graphs.

Definition A relative plane graph is a plane graph $G$ with a distinguished subset $H\subseteq E(G)$ of edges. The edges $H$ are called the 0-edges of $G$. Edges in $E(G)\backslash H$ will be referred to as regular edges.

The motivation of our work comes from knot theory. The classical Thistlethwaite theorem ([Thistlethwaite1987]) relates the Jones polynomial of an alternating link to the Tutte polynomial of a plane graph obtained from a checkerboard coloring of the regions of the link diagram. This theorem has two different kinds of generalizations to virtual links. One ([Chmutov2009]; [Chmutov and Pak2007]; [Chmutov and Voltz2008]; [Dasbach et al.2008]; [Moffatt2010]) involves graphs on surfaces and a topological version of the Tutte polynomial due to Bollobás and Riordan ([Bollobás and Riordan2002]). Another generalization is based on a relative version of the Tutte polynomial found by Diao and Hetyei ([Diao and Hetyei2010]). In this paper we establish a direct relation between the Bollobás–Riordan and relative Tutte polynomials that explains how these two generalizations are connected.

In Sect. 2 we explain the construction of a relative plane graph from a ribbon graph as well as how to recover a ribbon graph from a relative plane graph. Our main theorem is formulated in Sect. 3 and proved in Sect. 4. In Sect.  5 we describe the relation between the relative Tutte polynomials of dual plane graphs that generalizes the classical relation $T_{G}(x,y)=T_{G^{*}}(y,x)$. In Sect. 6 we obtain the Kauffman bracket of a virtual link in terms of the relative Tutte polynomial, improving the theorem of [Diao and Hetyei2010]. Section 7 places our relation between the Bollobás–Riordan polynomial and relative Tutte polynomial within the context of other polynomial invariants of graphs on surfaces.

This work has been done as a part of the Summer 2010 undergraduate research working group

“Knots and Graphs” at the Ohio State University. We are grateful to all participants of the group for valuable discussions and to the OSU Honors Program Research Fund for the student financial support.

## 2 Ribbon Graphs and Relative Plane Graphs

We refer to [Biggs1993], [Godsil and Royle2001], [Gross and Tucker1987], [Lando and Zvonkin2004], [Loebl2010] and [Mohar and Thomassen2001] for the standard general notions and terminology of (topological) graph theory.

### 2.1 Ribbon Graphs and Their Arrow Presentation

###### Definition 2.1.

([Bollobás and Riordan2002]) By a ribbon graph we mean an abstract (not necessarily orientable) surface with boundary decomposed into a number of closed topological discs of two types, vertex-discs and edge-ribbons, satisfying the following natural conditions: the discs of the same type are pairwise disjoint; the vertex-discs and the edge-ribbons intersect by disjoint line segments, each such line segment lies on the boundary of precisely one vertex and precisely one edge, and every edge contains exactly two such line segments, which are not adjacent.

Ribbon graphs are considered up to homeomorphisms of the underlying surfaces preserving the decomposition.

Here are three examples.

A ribbon graph may be given by an arrow presentation.

###### Definition 2.2.

([Chmutov2009]) An arrow presentation consists of a set of disjoint circles together with a collection of arrow markings on these circles. These arrows are labeled in pairs. To obtain a ribbon graph from an arrow presentation, we glue discs to each of the circles and attach edge ribbons to each pair of arrows in such a way that the arrows form part of a consistent orientation around the boundary of the edge ribbon.

Here is an example of an arrow presentation.

See more details of the arrow presentation in [Chmutov2009] and [Moffatt2010].

### 2.2 Medial Graphs

The relation between ribbon graphs and relative plane graphs is based on the standard notion of a medial graph (see, for example [Biggs1993]; [Godsil and Royle2001]; [Loebl2010]).

###### Definition 2.3.

Let $H$ be a planar graph. Its medial graph $M(H)$ is the planar graph whose vertices are the mid-points of the edges of $H$, and whose edges are given by the following procedure: whenever two edges are adjacent in some face of $H$, we connect the corresponding vertices of $M(H)$ by an edge that follows the boundary of the face. Each vertex of $M(H)$ will be 4-valent. The medial graph is embedded into the same plane as $H$; each of its faces corresponds either to a face of $H$ or to a neighborhood of a vertex of $H$.

The top figure below exemplifies the construction of the medial graph around an edge of $H$. Here we draw one pair of opposite edges of $M(H)$ by solid lines and another pair by dotted lines. The bottom figure shows an example of the entire medial graph.

Since $M(H)$ is a regular 4-valent planar graph, we may consider it as an immersion of a number of circles into the plane: if a circle goes into a vertex of $M(H)$ along some edge of $M(H)$, it continues to go out of the vertex along the opposite edge of $M(H)$. Then another pair of edges at this vertex belongs either to the same circle or to a different one. We draw the edges of one circle by solid lines and the edges of a different circle by dotted lines. The number of these circles is denoted by $\delta(H)$. In particular, for the medial graph of the bottom figure above $\delta(H)=2$. This immersion of circles has only double points as singularities, which are points in the plane at which the immersion is two-to-one, but the tangent directions at this point are distinct.

###### Construction 2.4.

In the other direction, for a regular 4-valent planar graph $B$ we can construct a graph $H:=C(B)$ for which the medial graph is equal to $B$, $M(C(B))=B$. To construct $H$ we consider a black and white checkerboard coloring of the regions of the complement to $B$ with the outer region painted white. For any planar 4-valent graph such coloring does exist. It is given by a parity of the intersection index of a path connecting a point at infinity with a point in interior of a region. Then we place a vertex into each black region and connect two vertices by an edge for each common double point on their boundaries. This edge is drawn through the corresponding double point.

#### 2.2.1 Medial Graphs of Ribbon Graphs

Let $R$ be a ribbon graph and $\widehat{R}$ be its core graph, obtained by forgetting the ribbon graph structure on the vertices and edges. $\widehat{R}$ embeds naturally into $R$, by placing each vertex of $\widehat{R}$ in the interior of the corresponding vertex disc of $R$, and connecting these vertices by edges through the corresponding edge-ribbons of $R$, in such a way that the cyclic order of the edges around each vertex of $\widehat{R}$ matches the cyclic order of the edge-ribbons around each vertex disc of $R$. In the same manner as for planar graphs, we may then construct the medial graph of $\widehat{R}$ (which we will also denote as $M(R)$ with respect to this embedding, by placing a vertex at the center of each edge of $\widehat{R}$ and connecting the vertices of $M(R)$ that belong to edges which are adjacent in the cyclic ordering around a vertex of $\widehat{R}$ by an edge that follows the boundary of $R$, and does not intersect $\widehat{R}$. The construction of $M(R)$ gives an embedding of this graph into $R$: we will require for convenience that, in this embedding, the vertex of $M(R)$ corresponding to a given edge of $\widehat{R}$ lies in the interior of the corresponding edge-ribbon of $R$. The connected components of $R-M(R)$ are disks and cylinders. The disks correspond to the vertices of $\widehat{R}$ and the cylinders correspond to the boundary components of $R.$

### 2.3 From Ribbon Graphs to Relative Plane Graphs

The manner in which we draw ribbon graphs suggests to consider a projection $\pi:R\to{\mathbb{R}}^{2}$ with singularities of two types. The first occurs when two edge-ribbons cross over each other. The second occurs when an edge ribbon twists over itself. Away from the singularities the projection is one-to-one.

The image $B$ of $M(R)$ may then be considered as a regular 4-valent planar graph whose vertices are divided into two types. The vertices which are images of vertices of $M(R)$ will be called regular vertices, and the vertices that arise from the singularities of the projection will be called 0-vertices. By applying the 2.4, we then obtain a relative planar graph $G:=C(B)$, whose 0-edges correspond to the 0-vertices of $B$.

###### Example 2.5.

In this figure the 0-edges of $G$ are drawn as dashed lines.

Of course such a projection always exists for any ribbon graph. In fact, these projections are easily constructed from an arrow presentation of a ribbon graph. We consider the circles of the arrow presentation as disjoint circles in the plane, none of which is contained in another. The vertex discs are constructed by filling in these circles. The edge ribbons are constructed in the plane by first considering arcs connecting the corresponding arrows on each circle which intersect transversally in the plane, and then taking sufficiently small neighborhoods of these arcs in the plane. If an edge ribbon must twist, we incorporate the twist in the ribbon away from any of the intersections of the arcs.

The constructed relative plane graph $G$ clearly depends on the projection $\pi$ and on the position of vertices of the medial graph on the edge-ribbons. However the invariants we will work with will not be affected by this ambiguity. The figure above shows the dependence of $G$ on the position of a vertex of the medial graph.

### 2.4 From Relative Plane Graphs to Ribbon Graphs

Conversely, from a relative plane graph $G$ we may construct a ribbon graph $R$. Consider the spanning subgraph $H$ of $G$ whose edges are the 0-edges of $G$. Construct $M(H)$ as in Sect. 2.2. Consider the medial graph as an immersion of a collection of $\delta(H)$ circles with clean double points. Each regular edge of $G$ intersects the planar graph $M(H)$ in two points. Each of these points has a neighborhood in which the immersion is an embedding. For each regular edge of $G$, take a square $I^{2}$ and identify one edge with a neighborhood of an intersection point in $M(H)$, and identify the opposing edge with a neighborhood of the second intersection point in $M(H)$, so that the counterclockwise orientation of the plane and the counterclockwise orientation of the boundary of $I^{2}$ are compatible. Via the embedding in a neighborhood of each intersection point, we may pull these identifications back to the collection of $\delta(H)$ disjoint circles. The ribbon graph $R$ is then the quotient space obtained by filling in each of these circles by a disc, and performing the constructed identifications of these circles with the collection of squares $I^{2}$ corresponding to the regular edges of $G$.

###### Example 2.6.

We do not label the pairs of arrows in this example because there is only one pair.

One can easily see that if $G$ is a relative plane graph constructed from a ribbon graph $R$ as in previous subsection, then this construction recovers $R$ from $G$. Also one may notice that there is a natural one to one correspondence between the edges of $R$ and the regular edges of $G$.

### 2.5 The Bollobás–Riordan Polynomial of Ribbon Graphs

The Bollobás–Riordan polynomial, originally defined in [Bollobás and Riordan2002], was generalized to a multivariable polynomial of weighted ribbon graphs in [Moffatt2008], [Vignes-Tourneret2009]. We will use a sightly more general doubly weighted Bollobás–Riordan polynomial of a ribbon graph $R$ with weights $(x_{e},y_{e})$ of an edge $e\in R$.

###### Definition 2.7.
 $\displaystyle B_{R}(X,Y,Z):=\sum_{F\subseteq R}\left(\prod_{e\in F}x_{e}\right )\left(\prod_{e\in R\setminus F}y_{e}\right)X^{k(F)-k(R)}Y^{n(F)}Z^{k(F)-bc(F) +n(F)},$

where the sum runs over all spanning subgraphs $F$, $k(F)$ is the number of connected components of $F$, $n(F)=|E(F)|-v(F)+k(F)$ is the nullity of $F$, and $bc(F)$ is the number of boundary components of $F$.

### 2.6 The Relative Tutte Polynomial

###### Definition 2.8.

Let $G$ be a relative plane graph with the distinguished set of 0-edges $H$. We consider spanning subgraphs $F$ of $G$ containing all 0-edges $H$. Such spanning subgraph can be identified with a subset of edges of $G\setminus H$. Summing over all such spanning subgraphs we set

 $\displaystyle T_{G,H}(G):=\sum_{F\subseteq G\setminus H}\left(\prod_{e\in F}x_ {e}\right)\left(\prod_{e\in\overline{F}}y_{e}\right)X^{k(F\cup H)-k(G)}Y^{n(F) }\psi(H_{F}),$

where $\overline{F}=G\setminus(F\cup H)$, $\psi$ is a block-invariant function on graphs, and $H_{F}$ is the plane graph obtained from $F\cup H$ by contracting all edges of $F$. Our choice of $\psi$ is

 $\displaystyle\psi(H_{F}):=d^{\delta(H_{F})-k(H_{F})}w^{v(H_{F})-k(H_{F})}{\!},$

$\delta(H_{F})$ is the number of circles that immerse to the medial graph of $H_{F}$.

Remarks.

1. 1.

The relative Tutte polynomial was introduced by Diao and Hetyei in [Diao and Hetyei2010], who used the notion of activities to produce the most general form of it. The all subset formula we use was discovered by a group of undergraduate students (Carnovale, Dong, Jeffries) at the OSU summer program “Knots and Graphs” in 2009. However, similar expressions may be traced back to Traldi ([Traldi2004]) for the non-relative case, and to Chaiken ([Chaiken1989]) for the relative case of matroids.

2. 2.

The function $\psi$ in [Diao and Hetyei2010] can be obtained from ours by substitution $w=1$.

3. 3.

Another difference with [Diao and Hetyei2010] is that we are using a doubly weighted version of the relative Tutte polynomial with weights $(x_{e},y_{e})$ of an edge $e\in G\setminus H$.

4. 4.

In the process of constructing the graph $H_{F}$ by contracting the edges of $F$ in $F\cup H$, we may come to a situation when we have to contract a loop. Then the contraction of a loop actually means its deletion. Since $G$ and $F\cup H$ are plane graphs, then the graph $H_{F}$ is also embedded into the plane.

5. 5.

While the medial graph of the planar graph $H_{F}$ depends on the embedding of $H_{F}$ into the plane, the number $\delta(H_{F})$ does not (see [Diao and Hetyei2010]). It depends only on the abstract graph $H_{F}$.

## 3 Main Theorem

###### Theorem 1.

Suppose $R$ is a ribbon graph, and $G$ is a relative plane graph associated to a projection of $R$. Or, equivalently, assume $G$ is a relative plane graph and $R$ is the ribbon graph arising from $G$. Assume that the natural bijection between the edges of $R$ and regular edges of $G$ preserves the weights.

Then under the substitution $w=\sqrt{\frac{X}{Y}},d=\sqrt{XY}$,

 $\displaystyle X^{\alpha}Y^{\beta}T_{G,H}(X,Y)=B_{R}\left(X,Y,\frac{1}{\sqrt{XY }}\right)$

where $\alpha:=k(G)-k(R)-\beta$ and $\beta:=-\frac{1}{2}(v(R)-v(G))$.

Remarks.

1. 1.

It is a remarkable consequence of the main theorem that the specialization ($w=\sqrt{\frac{X}{Y}},d=\sqrt{XY}$) of the relative Tutte polynomial does not depend on the various choices made in the construction of the relative plane graph in Sect. 2.3. It is not difficult to describe a sequence of moves on relative plane graphs relating the graphs with different choices of the regular edges. It would be interesting to find such moves for different choices of the projection $\pi$ and, more generally, the moves preserving the relative Tutte polynomial.

2. 2.

The construction of $G$ from $R$ and backward can be generalized to a wider class of projections $\pi$. We can require that only the restriction of $\pi$ to the boundary of $R$ be an immersion with only ordinary double points as singularities. The theorem holds in this topologically more general situation. However, from the point of view of graph theory it is more natural to restrict ourselves to the class of projections which we use.

## 4 Proof

Our constructions of $G$ from $R$ and $R$ from $G$ in Sects. 2.3 and 2.4 give a bijection between regular edges of $G$ and the edge-ribbons of $R$. We denote the corresponding edges by the same letter $e$ for both $e\in G\setminus H$ and for $e\in R$ since this will not lead to confusion. Moreover, in the theorem we assume that this bijection respects the weights of the doubly weighted polynomials. The bijection can be naturally extended to the bijection between spanning subgraphs $F\subseteq G\setminus H$ and $F^{\prime}\subseteq R$ so that the weights of $F$ and $F^{\prime}$ are equal to each other:

 $\displaystyle\left(\prod_{e\in F}x_{e}\right)\left(\prod_{e\in\overline{F}}y_{ e}\right)=\left(\prod_{e\in F^{\prime}}x_{e}\right)\left(\prod_{e\in R \setminus F^{\prime}}y_{e}\right)$

Thus the theorem can be checked only on monomials in $X$ and $Y$ corresponding to $F\subseteq G\setminus H$ and $F^{\prime}\subseteq R$. In other words, we have to prove that

 $\displaystyle X^{k(G)-k(R)+\frac{1}{2}(v(R)-v(G))}Y^{-\frac{1}{2}(v(R)-v(G))}X ^{k(F\cup H)-k(G)}Y^{n(F)}$ $\displaystyle\quad d^{\delta(H_{F})-k(H_{F})}w^{v(H_{F})-k(H_{F})}=X^{k(F^{ \prime})-k(R)}Y^{n(F^{\prime})}Z^{k(F^{\prime})-bc(F^{\prime})+n(F^{\prime})}$ (1)

for $d=\sqrt{XY}$, $w=\sqrt{\frac{X}{Y}}$, and $Z=\frac{1}{\sqrt{XY}}$.

We need the following combinatorial equalities:

1. (2)

$|E(F)|=|E(F^{\prime})|$

2. (3)

$k(H_{F})=k(F\cup H)$

3. (4)

$bc(F^{\prime})=n(F)+\delta(H_{F})$

4. (5)

$v(H_{F})=k(F)$

(2) is clear from the subgraph correspondence. Since contracting edges of a graph cannot disconnect it or connect disconnected components, (3) is immediate.

### 4.1 Proof of (4)

The restriction of the projection $\pi:R\to{\mathbb{R}}^{2}$ from Sect.  2.3 to the spanning ribbon subgraph $F^{\prime}$ is an immersion of $bc(F^{\prime})$ circles into the plane ${\mathbb{R}}^{2}$. We need to compare this number of the immersed circles with the number $n(F)+\delta(H_{F})$. To do this one can check how the number of immersed circles changes when edges of $F$ are contracted. It is easy to see that the contraction of a non-loop does not change the number of circles. But, the contraction of a loop, which is the same as deletion of the loop, fuses two disjoint circles together, one from the outside of the loop and one from the inside of the loop. So it reduces the number of circles by 1. The result of contracting all the edges of $F$ is the graph $H_{F}$, for which the number of circles will be $\delta(H_{F})$. Since the number of loops contracted during the process of contraction is $n(F)$, we have

 $\displaystyle bc(F^{\prime})=n(F)+\delta(H_{F}).$

### 4.2 Proof of (5)

Consider $F\cup H$ as a spanning subgraph of $G$ and remove the edges of $H$ from it. Then we get the spanning subgraph $F$. Its edges are supposed to be contracted, so each connected component of $F$ gives a vertex of the resulting graph. Now restoring the edges of $H$ does not change the number of vertices of the graph obtained by contracting $F$. Thus $v(H_{F})=k(F)$.

### 4.3 Proof of the Theorem

We deal with the exponents of $X$ and $Y$ separately. The exponent of $X$ in the left hand side of Eq. (4) is

 $\displaystyle\frac{1}{2}(v(R)-v(G))+k(G)-k(R)+k(F\cup H)-k(G)$ $\displaystyle\quad+\frac{1}{2}(\delta(H_{F})-k(H_{F})+v(H_{F})-k(H_{F}))$

Substituting the equalities above and making appropriate cancellations,

 $\displaystyle=\frac{1}{2}(v(R)-v(G))-k(R)+\frac{1}{2}(\delta(H_{F})+k(F))$ $\displaystyle=\frac{1}{2}(v(R)-v(G))-k(R)+\frac{1}{2}(bc(F^{\prime})-n(F)+k(F))$ $\displaystyle=\frac{1}{2}(v(R)-v(G))-k(R)+\frac{1}{2}(bc(F^{\prime})-|E(F^{ \prime})|+v(G))$ $\displaystyle=-k(R)+\frac{1}{2}(bc(F^{\prime})+v(R)-|E(F^{\prime})|)$ $\displaystyle=k(F^{\prime})-k(R)+\frac{1}{2}(bc(F^{\prime})-n(F^{\prime})+k(F^ {\prime}))$

which is the exponent of $X$ in $B_{R}$.

For $Y$, the exponent in the left hand side of equation (4) is

 $\displaystyle-\frac{1}{2}(v(R)-v(G))+n(F)+\frac{1}{2}(\delta(H_{F})-k(H_{F})-v (H_{F})+k(H_{F}))$

This is equival to,

 $\displaystyle=|E(F)|-v(G)+k(F)+\frac{1}{2}(bc(F^{\prime})-n(F)-v(H_{F})-v(R)+v (G))$ $\displaystyle=\frac{1}{2}(bc(F^{\prime})-|E(F)|+2v(G)-v(R)-2k(F))+|E(F)|-v(G)+ k(F)$ $\displaystyle=\frac{1}{2}(|E(F^{\prime})|-v(R)+bc(F^{\prime}))$ $\displaystyle=n(F^{\prime})+\frac{1}{2}(bc(F^{\prime})-n(F^{\prime})-k(F^{ \prime}))$

which is the exponent of $Y$ in $B_{R}$.

## 5 Dual Relative Plane Graphs

Let $G$ be a relative plane graph. The dual of $G$, denoted $G^{*}$ is formed by taking the dual of $G$ as a plane graph, and labeling the edges of $G^{*}$ which intersect 0-edges of $G$ as the 0-edges of $G^{*}$. Note that for relative plane graphs $(G^{*})^{*}=G$, as with usual planar duality.

###### Theorem 2.

Under the substitution $w=\sqrt{\frac{X}{Y}}$, $d=\sqrt{XY}$, we have

 $\displaystyle X^{a(G,H)}Y^{b(G)}T_{G,H}(X,Y)=Y^{a(G^{*},H^{*})}X^{b(G^{*})}T_{ G^{*},H^{*}}(Y,X)$

with the correspondence on the edge weights being $x_{e}$=$y_{e^{*}}$, $y_{e}$=$x_{e^{*}}$, where $e^{*}$ is the edge of $G^{*}$ that intersects $e$, and  $a(G,H)=(|E(G\setminus H)|-v(G))/2+k(G),\,\,b(G)=v(G)/2\ .$

Remarks.

1. 1.

This theorem generalizes the classical relation, $T_{G}(x,y)=T_{G^{*}}(y,x)$, for the Tutte polynomials of dual plane graphs to relative plane graphs. The duality theorem for the Bollobás–Riordan polynomial was found in [Ellis-Monaghan and Sarmiento2011] (see also [Moffatt2008] and [Chmutov2009]), and for the more general Krushkal’s polynomial in [Krushkal2011].

2. 2.

The theorem could be proved knowing that the dual of a relative plane graph corresponds to the dual ribbon graph and using the Bollobás–Riordan duality result from [Ellis-Monaghan and Sarmiento2011]. However, at this moment we do not claim this relation and give a direct proof below. In general, it would be interesting to express the partial duality of ribbon graphs from [Chmutov2009], [Moffatt2010] in terms of relative plane graphs.

###### Proof of the Theorem.

The equality is on monomials of $T_{G,H}$, $T_{G^{*},H^{*}}$ in the edge weight variables $(x_{e},y_{e})$ which establish the correspondence between spanning subgraphs $F$ of $G\setminus H$ and $F^{*}$ of $G^{*}\setminus H^{*}$. Namely, $F^{*}$ consists of those regular edges of $G^{*}$ which do not intersect the regular edges of $F$.

We prove the equality on monomials for the exponent of $X$. Equality for $Y$ then follows from duality. The exponent of X on the left is

 $\displaystyle\frac{1}{2}(|E(G\setminus H)|-v(G))+k(G)+k(F\cup H)-k(G)+\frac{1} {2}(\delta(H_{F})-k(H_{F})$ $\displaystyle\quad+v(H_{F})-k(H_{F}))$ $\displaystyle\quad=\frac{1}{2}(|E(G\setminus H)|-v(G)+bc(F_{R})-n(F)+k(F))$ $\displaystyle\quad=\frac{1}{2}(|E(G\setminus H)|+bc(F_{R})-|E(F)|)$ $\displaystyle\quad=\frac{1}{2}(|E(\overline{F})|+bc(F_{R})),$

where $F_{R}$ is the ribbon graph constructed from the relative plane graph $F\cup H$ in the manner of Sect. 2.4.

On the right, let $F^{*}$ denote the subgraph of $G^{*}$ corresponding to $F$. Then the exponent of $X$ is

 $\displaystyle n(F^{*})+\frac{1}{2}(\delta(H_{F^{*}})-k(H_{F^{*}})-v(H_{F^{*}}) +k(H_{F^{*}})+v(G^{*}))$ $\displaystyle\quad=n(F^{*})+\frac{1}{2}(bc(F_{R}^{*})-n(F^{*})-k(F^{*})+v(G^{* }))$ $\displaystyle\quad=\frac{1}{2}(bc(F_{R}^{*})+|E(F^{*})|)$

Now, $|E(F^{*})|=|E(\overline{F})|$ by the subgraph correspondence. The equality $bc(F_{R})$=$bc{}(F_{R}^{*})$ follows from the fact that the ribbon graphs $F_{R}$ and $F_{R}^{*}$ have the same boundary. It can also be seen from the following figures:

## 6 Kauffman Bracket of Virtual Links

In this section we generalize the result of [Diao and Hetyei2010] which extends the Thistlethwaite theorem to virtual links. Virtual links are represented by diagrams similar to ordinary knot diagrams, except some crossings are designated as virtual. Here are some examples of virtual knots.

Virtual link diagrams are considered up to plane isotopy, the classical Reidemeister moves:

and the virtual Reidemeister moves:

The Kauffman bracket for virtual links is defined in the same way as for classical links. Let $L$ be a virtual link diagram. Consider two ways of resolving a classical crossing. The A-splitting, is obtained by joining the two vertical angles swept out by the overcrossing arc when it is rotated counterclockwise toward the undercrossing arc. Similarly, the B-splitting, is obtained by joining the other two vertical angles. A state $s$ of a link diagram $L$ is a choice of either an $A$ or $B$-splitting at each classical crossing. Denote by $\mathcal{S}(L)$ the set of states of $L$. A diagram $L$ with $n$ crossings has $|\mathcal{S}(L)|=2^{n}$ different states.

Denote by $\alpha(s)$ and $\beta(s)$ the numbers of $A$-splittings and $B$-splittings in a state $s$, respectively, and by $\delta(s)$ the number of components of the curve obtained from the link diagram $L$ by splitting according to the state $s\in\mathcal{S}(L)$. Note that virtual crossings do not connect components.

###### Definition 6.1.

The Kauffman bracket of a diagram $L$ is a polynomial in three variables $A$, $B$, $d$ defined by the formula

 $\displaystyle[L](A,B,d)\ :=\ \sum_{s\in\mathcal{S}(L)}\,A^{\alpha(s)}\,B^{ \beta(s)}\,d^{\,\delta(s)-1}\,.$

Note that $[L]$ is not a topological invariant of the link; it depends on the link diagram and changes with Reidemeister moves. However, it determines the Jones polynomial $J_{L}(t)$ by a simple substitution:

 $\displaystyle A=t^{-1/4},\qquad B=t^{1/4},\qquad d=-t^{1/2}-t^{-1/2}\ ;$
 $\displaystyle J_{L}(t)\,:=(-1)^{w(L)}t^{3w(L)/4}[L](t^{-1/4},t^{1/4},-t^{1/2}- t^{-1/2})\ .$

In 1987 Thistlethwaite ([Thistlethwaite1987]) (see also [Kauffman1988]) proved that up to a sign and a power of $t$ the Jones polynomial $V_{L}(t)$ of an alternating link $L$ is equal to the Tutte polynomial $T_{G_{L}}(-t,-t^{-1})$ of the Tait graph $G_{L}$ obtained from a checkerboard coloring of the regions of a link diagram.

Kauffman ([Kauffman1989]) generalized the theorem to arbitrary (classical) links using signed graphs. To virtual links this theorem was extended in [Chmutov2009], [Chmutov and Pak2007], [Chmutov and Voltz2008] using ribbon graphs. Another extension, using the relative Tutte polynomial, is due Diao and Hetyei ([Diao and Hetyei2010]). In their construction the relative plane graph is the Tait graph of a virtual link diagram whose 0-edges correspond to virtual crossings. They expressed $[L](A,A^{-1},-A^{2}-A^{-2})$ as a specialization of the relative Tutte polynomial. The whole Kauffman bracket $[L](A,B,d)$, although not a link invariant, is of interest as a pure combinatorial invariant of link diagrams. It turns out that it also can be expressed as a specialization of the relative Tutte polynomial.

Following [Diao and Hetyei2010], we assign signs to the edges of the Tait graph $G$ depending on whether the edge connects $A$- or $B$-splitting regions:

###### Theorem 3.

Let L be a virtual link diagram, and G the relative plane Tait graph of Then, under the substitution

 $\displaystyle X=\frac{Bd}{A},\qquad Y=\frac{Ad}{B},\qquad w=\frac{B}{A},\qquad x _{+}=y_{+}=1,$ $\displaystyle\quad x_{-}=\sqrt{\frac{X}{Y}}\!=\!\frac{B}{A},\qquad y_{-}=\sqrt {\frac{Y}{X}}\!=\!\frac{A}{B}$

we have,

 $\displaystyle[L](A,B,d)=A^{v(G)-k(G)}B^{|E(G\backslash H)|-v(G)+k(G)}d^{k(G)-1 }T_{G,H}{\!}.$
###### Proof.

The equality is on monomials, with the correspondence between subgraphs $F$ and states $S$ being the natural one:

Let $|E_{-}(F)|$ (resp. $|E_{+}(F)|$) be the number of negative (resp. positive) edges in the graph $F$. The power of $B$ on the right is

 $\displaystyle|E(G\setminus H)|-v(G)+k(G)+|E_{-}(F)|-|E_{-}(\overline{F})|$ $\displaystyle\qquad+k(F\cup H)-k(G)-n(F)+v(H_{F})-k(H_{F})$ $\displaystyle\quad=|E_{-}(F)|-|E_{-}(\overline{F})|+|E(G\setminus H)|-|E(F)|$ $\displaystyle\quad=|E_{-}(F)|-|E_{-}(\overline{F})|+|E(\overline{F})|\ =\ |E_{ -}(F)|+|E_{+}(\overline{F})|\ =\ \beta(S),$

as it can be easily seen from the picture above. The proof of equality on the exponent of $A$ is similar. For $d$, the exponent on the right is

 $\displaystyle k(G)-1+k(F\cup H)-k(G)+n(F)+\delta(H_{F})-k(H_{F})$ $\displaystyle\quad=n(F)+\delta(H_{F})-1=bc(F_{R})-1=\delta(S)-1.$

$\square$

## 7 Polynomials of Graphs on Surfaces

There are several other polynomial invariants of graphs on surfaces. This section is intended to be a guide for the interested reader to understand how these polynomial invariants are related to each other, and how our work on the Bollobás–Riordan polynomial and relative Tutte polynomial fits within this more general context.

One of the most general such polynomials $P_{R}(X,Y,A,B)$ was defined by Krushkal in [Krushkal2011] in terms of the topology of the embedding. It generalizes the Bollobás–Riordan polynomial:

 $\displaystyle B_{R}(X,Y,Z)=Y^{g}P_{R}(X,Y,YZ^{2},Y^{-1}),$

where $g$ is the genus of the ribbon graph.

A combinatorial polynomial $LV_{R}(x,y,z)$ was defined by Las Vergnas in [Las1980], [Las Vergnas1999] using matroids of the graph and its dual. It turns out to be a specialization of the Krushkal polynomial [Askanazi et al.2013]:

 $\displaystyle LV_{R}(x,y,z)=z^{g}P_{R}(x-1,y-1,z^{-1},z).$

The Bollobás–Riordan polynomial was extended to ribbon graphs with additional structure, arrow structure, in [Bradford et al.2012]. It would be interesting to define this structure for relative planar graphs and extend our main theorem to it. Some other polynomial invariants may be found in [Ellis-Monaghan and Moffatt2015].

The next diagram represents various relations between these polynomials.

Both the relative Tutte polynomial of [Diao and Hetyei2010] and the Las Vergnas polynomial of [Las1980], [Las Vergnas1999] may be formulated for matroids. But the results of [Askanazi et al.2013] (see also the substitutions in the diagram above) indicate that the Las Vergnas and the Bollobás–Riordan polynomials are independent. Since the latter polynomial specializes to the relative Tutte polynomial one should expect that the relative Tutte and the Las Vergnas polynomials are also independent. This may signify the existence of a more general matroid polynomial which would be a matroidal counterpart of the Krushkal polynomial. Recently this sort of polynomial was found in [Chun et al.2014].

## References

• [Askanazi et al.2013] Askanazi, R., Chmutov, S., Estill, C., Michel, J., Stollenwerk, P.: Polynomial invariants of graphs on surfaces. Quantum Topol. 3, 77–90 (2013); preprint [math.CO]
• [Biggs1993] Biggs, N.: Algebraic Graph Theory. Cambridge University Press, Cambridge (1993)
• [Bollobás1998] Bollobás, B.: Modern Graph Theory, Graduate Texts in Mathematics, vol. 184. Springer, New York (1998)
• [Bollobás and Riordan2002] Bollobás, B., Riordan, O.: A polynomial of graphs on surfaces. Math. Ann. 323, 81–96 (2002)
• [Bradford et al.2012] Bradford, R., Butler, C., Chmutov, S.: Arrow ribbon graphs. J. Knot Theory Ramif. 21(13), 1240002 (2012); preprint [math.CO]
• [Chaiken1989] Chaiken, S.: The Tutte polynomial of a ported matroid. J. Comb. Theory Ser. B 46, 96–117 (1989)
• [Chmutov2009] Chmutov, S.: Generalized duality for graphs on surfaces and the signed Bollobás-Riordan polynomial. J. Comb. Theory Ser. B 99(3), 617–638 (2009); preprint [math.CO]
• [Chmutov and Pak2007] Chmutov, S., Pak, I.: The Kauffman bracket of virtual links and the Bollobás–Riordan polynomial. Mosc. Math. J.  7(3), 409–418 (2007); preprint
• [Chmutov and Voltz2008] Chmutov, S., Voltz, J.: Thistlethwaite’s theorem for virtual links. J. Knot Theory Ramif. 17(10), 1189–1198 (2008); preprint [math.GT]
• [Chun et al.2014] Chun, C., Moffatt, I., Noble, S., Rueckriemen, R.: Matroids, delta-matroids and embedded graphs (2014); preprint [math.CO]
• [Dasbach et al.2008] Dasbach, O., Futer, D., Kalfagianni, E., Lin, X.-S., Stoltzfus, N.: The Jones polynomial and graphs on surfaces. J. Comb. Theory Ser. B 98, 384–399 (2008); preprint
• [Diao and Hetyei2010] Diao, Y., Hetyei, G.: Relative Tutte polynomials for colored graphs and virtual knot theory. Comb. Probab. Comput. 19, 343–369 (2010); preprint [math.CO]
• [Ellis-Monaghan and Sarmiento2011] Ellis-Monaghan, J.A., Sarmiento, I.: A recipe theorem for the topological Tutte polynomial of Bollobás and Riordan. Eur. J. Combin. 32, 782–794 (2011); preprint [math.CO]
• [Ellis-Monaghan and Moffatt2015] Ellis-Monaghan, J.A., Moffatt, I.: Evaluations of topological Tutte polynomials. Comb. Probab. Comput. 24, 556–583 (2015); preprint [math.CO]
• [Godsil and Royle2001] Godsil, C., Royle, G.: Algebraic Graph Theory, Graduate Texts in Mathematics, vol. 207. Springer, New York (2001)
• [Gross and Tucker1987] Gross, J.L., Tucker, T.W.: Topological Graph Theory. Wiley, New York (1987)
• [Kauffman1988] Kauffman, L.H.: New invariants in knot theory. Am. Math. Monthly 95, 195–242 (1988)
• [Kauffman1989] Kauffman, L.H.: A Tutte polynomial for signed graphs. Discret. Appl. Math. 25, 105–127 (1989)
• [Kauffman1999] Kauffman, L.H.: Virtual knot theory. Eur. J. Comb. 20, 663–690 (1999)
• [Krushkal2011] Krushkal, V.: Graphs, links, and duality on surfaces. Comb. Probab. Comput. 20, 267–287 (2011); preprint [math.CO]
• [Lando and Zvonkin2004] Lando, S.K., Zvonkin, A.K.: Graphs on Surfaces and Their Applications. Springer, New York (2004)
• [Las1980] Las Vergnas, M.: Ann. Discret. Math. On the Tutte polynomial of a morphism of matroids 8, 7–20 (1980)
• [Las Vergnas1999] Las Vergnas, M.: The Tutte polynomial of a morphism of matroids. I. Set-pointed matroids and matroid perspectives. Symposium à la Mémoire de François Jaeger (Grenoble, 1998). Ann. Inst. Fourier (Grenoble) 49(3), 973–1015 (1999)
• [Loebl2010] Loebl, M.: Discrete Mathematics in Statistical Physics. Vieweg and Teubner, Wiesbaden (2010)
• [Moffatt2008] Moffatt, I.: Knot invariants and the Bollobás–Riordan polynomial of embedded graphs. Eur. J. Comb. 29, 95–107 (2008); preprint
• [Moffatt2010] Moffatt, I.: Partial duality and Bollobás and Riordan’s ribbon graph polynomial. Discret. Math. 310, 174–183 (2010); preprint [math.CO]
• [Mohar and Thomassen2001] Mohar, B., Thomassen, C.: Graphs on Surfaces. The Johns Hopkins University Press, Baltimore (2001)
• [Thistlethwaite1987] Thistlethwaite, M.: A spanning tree expansion for the Jones polynomial. Topology 26, 297–309 (1987)
• [Traldi2004] Traldi, L.: A subset expansion of the coloured Tutte polynomial. Comb. Probab. Comput. 13, 269–275 (2004)
• [Vignes-Tourneret2009] Vignes-Tourneret, F.: The multivariate signed Bollobás-Riordan polynomial. Discret. Math. 309, 5968–5981 (2009); preprint [math.CO]