Bollobás–Riordan and Relative Tutte Polynomials

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

http://www.math.ohio-state.edu/~chmutov/wor-gr-su10/wor-gr.htm

“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.

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.

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.

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:

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

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.

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.

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.

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.

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:

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:

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:

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]:

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].