Topological Tutte Polynomial
Sergei Chmutov



Topological Tutte Polynomial]
  Topological Tutte Polynomial



Ohio State University - Mansfield, 
1760 University Drive, 
Mansfield, OH 44906, USA chmutov@math.ohio-state.edu




This is a survey of recent works on topological extensions of the Tutte polynomial. 




[
    SERGEI CHMUTOV
    
==================

Mathematics Subject Classifications: 05C31, 05C22, 05C10, 57M15, 57M25, 57M30



§ INTRODUCTION
  
We survey recent works on topological extensions of the Tutte polynomial. 

The extensions deal with graphs on surfaces. Graphs embedded into surfaces are the main objects of the topological graph theory. There are several books devoted to this subject <cit.>.
Cellular embeddings of graphs can be described as ribbon graphs. Oriented ribbon graphs appear under different names such as rotation systems <cit.>, maps, fat graphs, cyclic graphs, dessins d'enfants <cit.>. 
Since the pioneering paper of L. Heffter in 1891 <cit.> they occur in various parts of mathematics ranging from graph theory, combinatorics, and topology to representation theory, Galois theory, algebraic geometry, and quantum field theory <cit.>. 
For example, ribbon graphs are used to enumerate cells in the cell decomposition of the moduli spaces of complex algebraic curves
<cit.>. The absolute Galois group 
Aut(ℚ/ℚ) faithfully acts on the set of ribbon graphs (see <cit.> 
and references therein). Ribbon graphs are the main combinatorial objects of the Vassiliev knot invariant theory 
<cit.>. 
They are very useful for Hamiltonicity of the Cayley graphs <cit.>.

M. Las Vergnas <cit.> found a generalization of the Tutte polynomial to cellularly embedded graphs as an application of his matroid perspectives. Recently his polynomial was extended to not necessarily cellularly embedded graphs <cit.>.

In 2001 B. Bollobás and O. Riordan <cit.>, motivated by some problems of knot theory, introduced a different generalization of the Tutte polynomial for ribbon graphs. For non-planar graphs, there is no duality relation for the Tutte polynomial but there is one for the Bollobás-Riordan polynomial. In <cit.>, this was proved for a one-variable specialization. 
J. Ellis-Monaghan and I. Sarmiento <cit.> extended it to a two-variable relation. 
Independently the duality formula was discovered in <cit.>. 


In knot theory the classical Thistlethwaite's theorem relates the Jones polynomial and the Tutte 
polynomial of a corresponding planar graph <cit.>. 
Igor Pak suggested using the Bollobás-Riordan polynomial for Thistlethwaite type theorems. This idea was first realized in <cit.> for a special class of (checkerboard colorable) virtual links. Then it was realized for classical links in <cit.>, and for arbitrary virtual links in <cit.>. 
Formally all three theorems from <cit.> were different. They used different constructions of a ribbon graph from a link diagram and different substitutions in the Bollobás-Riordan polynomials of these graphs. An attempt to understand and unify these theorems led to the discovery of partial duality in <cit.> (called there generalized duality) and to a proof of an invariance of a certain specializations of the 
Bollobás-Riordan polynomial under it.

A different generalization of Thistlethwaite theorem for virtual
links was found in <cit.> based on the relative Tutte polynomial of plane graphs. The equivalence of this approach to that of <cit.> was clarified in <cit.>.

In 2011 V. Krushkal <cit.> found a four variable generalization of the Tutte polynomial. It can be reduced to the Bollobás-Riordan polynomial under a certain substitution. It turns out <cit.> that it also can be reduced to the Las Vergnas polynomial under a different substitution, while the Las Vergnas and the Bollobás-Riordan polynomials are essentially independent of each other. Generalizing the classical spanning tree expansion of the Tutte polynomial, Clark Butler found <cit.> an elegant quasi-tree expansion of the Krushkal polynomial.

The next diagram represents various relations between these polynomials.

    [               ; K_G,Σ(X,Y,A,B) ][d]^[ A:=YZ^2; B:=Y^-1 ][rd]^(.7)[ X:=x-1, Y:=y-1,;   A:=z^-1, B:=z ]   
    [             ; T_G,H(X,Y,ψ) ]@/_1.5pc/[rd]^[   ψ (H_F):≡ 1,; X:=x-1, Y:=y-1 ]   [            ; BR_G(X,Y,Z) ]@/_2.5pc/[l]_-18ptZ:=(XY)^-1/2[d]_[ X:=x-1, Y:=y-1,;            Z:=1 ]   [            ; LV_G(x,y,z) ][ld]^ z:=1/y-1
       [        ; T(;x,y) ]


Both the relative Tutte polynomial of <cit.> and the
Las Vergnas polynomial of <cit.> may be formulated for matroids. 
Since the Bollobás-Riordan polynomial specializes to the relative Tutte polynomial one may 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. 

Very recently I. Moffatt and B. Smith found such a polynomial. 




The Tutte polynomial has also been extended to higher dimensional cell complexes. We do not pursue this connection here, but the interested reader may see  <cit.>. 
In <cit.> this polynomial was related to the cellular spanning trees of 
<cit.>,
the arithmeric matroids of <cit.> and the simplicial chromatic polynomial 
<cit.>. 




§ RIBBON GRAPHS.


The topological objects we are dealing with are graphs embedded into a surface. The embedding is assumed to be cellular, that means each connected component of the complement of the graph, a face, is homeomorphic to a disc.
cellular embeddingembedding!cellular 

Considering a small regular neighborhood of the graph on a surface we come to the equivalent notion of ribbon graphs.



A ribbon graphribbon graph 
is an abstract (not necessarily orientable) compact 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 in 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.

We consider ribbon graphs up to a homeomorphism of the corresponding surfaces preserving the decomposition into vertex-discs and edge-ribbons.
It is important to note that a ribbon graph is an abstract two-dimensional surface with boundary; its embedding into the 3-space shown in pictures is irrelevant.

Here are three examples.

    -35rg-ex14000  -30rg-ex24000  -30rg-ex3180045


Gluing a disc to each boundary component of a ribbon graph G we get a closed surface without boundary. Placing a vertex at the center of each vertex-disc and connecting the vertices by edges along the edge-ribbons we get a graph, the core graph of G, cellularly embedded into the surface. Thus ribbon graphs and cellularly embedded graphs are the same objects.

In this paper we will use the following notation for the major parameters of a ribbon graph.



  ∙ v(G) := |V(G)| denotes the number of vertices of a ribbon graph G;

  ∙ e(G) := |E(G)| denotes the number of edges of G;

  ∙ k(G) denotes the number of connected components of G;

  ∙ r(G):=v(G)-k(G) denotes the rank of G;

  ∙ n(G):=e(G)-r(G) denotes the nullity of G;

  ∙ bc(G) denotes the number of connected components of the boundary of the surface of G.
 

Only the last parameter bc(G) is a topological one. All the others parameters are standard in graph theory.

A spanning subgraph F of a ribbon graph G is 
a ribbon graph consisting of all the vertices of G and a subset of the edges of G.





§ THE BOLLOBÁS–RIORDAN POLYNOMIAL.
 

The Bollobás–Riordan polynomial, originally defined in <cit.>, was generalized to a multivariable polynomial of weighted ribbon graphs in
<cit.>. 

We will use a slightly more general doubly weighted 
Bollobás–Riordan polynomial of a ribbon graph G with weights (x_e,y_e) of an edge e∈ G.
The doubly weighted Tutte polynomial is useful in connection with the knot theory 
<cit.>. Double weights also allow to specialize the Bollobás–Riordan polynomial to different signed versions of the Tutte polynomial, see the Section <ref>.

Bollobás–Riordan polynomial

    BR_G(X,Y,Z):=∑_F⊆ G (∏_e∈ Fx_e) 
    (∏_e∉Fy_e) X^r(G)-r(F)Y^n(F)Z^k(F)-bc(F)+n(F),

where the sum runs over all spanning subgraphs F. 


The original Bollobás–Riordan polynomial of <cit.> used an
additional variable w responsible for orientability of the ribbon subgraph F. We set w=1 and replace their x-1 by our X, but we introduce weights of edges.

Note that the exponent k(F)-bc(F)+n(F) of the variable Z is equal to
2k(F)-χ(F), where χ(F) is the Euler characteristic of the surface F obtained by gluing a disc to each boundary component of F.
For orientable F, it is twice the genus of F. For non-orientable F, according to the  classical classification theorem for surfaces, F can be represented by a connected sum of several real projective planes; the number of them is equal to the exponent of Z. In particular, for a planar ribbon graph G (i.e. when the surface G has genus zero) the 
Bollobás-Riordan polynomial BR_G does not contain Z. 
In this case, and if all weights are equal to 1, it is equal to the classical Tutte polynomial 
T(;x,y) of the core graph  of G with shifted variables X=x-1, Y=y-1:

    BR_G(x-1,y-1,Z) = T(;x,y) .

Similarly, a specialization Z=1 (and x_e=1, y_e=1 for all edges e) of the Bollobás-Riordan polynomial
of an arbitrary ribbon graph G gives the Tutte polynomial of the core graph:

    BR_G(x-1,y-1,1) = T(;x,y) .

So one may think of the Bollobás-Riordan polynomial as a generalization of the Tutte polynomial to graphs cellularly embedded into a surface and capturing topological information of the embedding.


Let the following ribbon graph G have all weights equal to 1.

    [     8rg-ex32(7,-5)G50305               8rgBBB4500               8rgBBA4500              13rgBAB4500              13rgBAA4500; (k,r,n,bc) term of  BR_G              (1,1,1,2) Y              (1,1,0,1) 1              (1,1,0,1) 1   (2,0,0,2) X-10pt(0,25);                                     8rg-ex3248405               8rgABA4800              13rgAAB4800              13rgAAA4800;                      2-5         (1,1,2,1) Y^2Z^2             (1,1,1,1) YZ             (1,1,1,1) YZ (2,0,1,2) XYZ-10pt(0,25) ]


    BR_G(X,Y,Z) = Y+2+X+Y^2Z^2+2YZ+XYZ





 §.§ Properties.

One can easily prove


    BR_G={[  x_e· BR_G/e + y_e· BR_G-e                           ;                                                      ; x_e· BR_G/e + y_eX· BR_G-e                           ;   x_eY· BR_G/e+y_e· BR_G-e                           ;  x_eYZ· BR_G/e+y_e· BR_G-e                            ].


    BR_G_1⊔ G_2 = BR_G_1· BR_G_2,


Here a trivial loop means a loop such that the deleting it and cutting its vertex-disc along a chord connecting the endpoints of the loop separates the the ribbon graph.



 §.§ A signed version of the Bollobás-Riordan polynomial.

Signed graphs are weighted graphs with single weights of ±1 on their edges. They are very important in particular in knot theory. There is a vast literature on signed graphs 
<cit.>. 

In <cit.> 
L. Kauffman introduced a generalization of the Tutte polynomial to signed graphs. The signed version of the Bollobás-Riordan polynomial was introduced in <cit.> 
and used in <cit.> 
(a version of it was also used in <cit.>). 
This signed version can be obtained by changing the sign weights to double weights and using the Bollobás-Riordan polynomial above. We set the weights of positive edges to 1, x_+:=y_+:=1, and the weights of negative edges to x_-:=(X/Y)^1/2, y_-:=(Y/X)^1/2. Thus the signed version becomes

    BR_G(x,y,z) = ∑_F ∈ G X^r(G)-r(F)+s(F) Y^n(F)-s(F)
       Z^k(F)-bc(F)+n(F) , 
       Bollobás–Riordan polynomial!signed version

where
s(F) := e_-(F)-e_-( F)/2,
e_-(F) denotes the number of negative edges in F, and 
F = G-F is the complement to F in G, i.e.
the spanning subgraph of G with exactly those (signed) edges of G that do not belong to F.

As above, specializing to Z=1 gives Kauffman's Tutte polynomial of signed graphs <cit.>. 

The book of C. Godsil and G. Royle   <cit.> 
introduced a slightly different signed version of the Tutte polynomial,
R(M;α,β,x,y), following a result of K. Murasugi <cit.>. It is formulated in terms of signed matroids. Its application to the cycle matroid of a ribbon graph also can be obtained as a specialization Z:=1, X:=x, Y:=y of our double weighted Bollobás-Riordan polynomial with weights of positive edges  x_+:=β, y_+:=α, and weights of negative edges  x_-:=α, y_-:=β.



 §.§ The dichromatic version of the Bollobás-Riordan polynomial.


𝐛
The dichromatic version of the Tutte polynomial Z_G(a,b) (see for example 
<cit.>), 
also known as the partition function of the Potts model in statistical mechanics, can be defined as a generating function of vertex colorings of a graph G into a colors:

    Z_G(a,b) := ∑_c∈ Col(G) 
    (1+b)^ ,

where Col(G):={c:V(G)→{1,…,a}} is the set of colorings, and an edge e is colored properly by c if its endpoints are colored in different colors. Also, it can be expressed as a generating function of all spanning subgraphs:

    Z_G(a,b) = ∑_F⊆ E()a^k(F) b^e(F).

The Tutte polynomial is equivalent to the dichromatic
polynomial because of the identities

    [                                     Z_G(a,b)                                            =              a^k(G)b^r(G) T(G;1+ab^-1,1+b) ;;                                     T(G;x,y)                                            = (x-1)^-k(G)(y-1)^-v(G) Z_G((x-1)(y-1),y-1) . ]


A multivariable version of dichromatic polynomial was introduced in <cit.> 
and used in <cit.>. 
The multivariable Tutte polynomial also appears as a very special case of Zaslavsky's colored Tutte polynomial of a matriod 
<cit.>. 
It can be defined as 

    Z_G(a,):=∑_F⊆ E(G) a^k(F)∏_e∈ Fb_e ,

The sum runs over all spanning subgraphs of G, which we identify with subsets F of E(G); :={b_e} is the set of variables (weights).

The multivariable dichromatic polynomial was generalized to ribbon graphs in  <cit.> 
as

    Z_G(a,,c):=∑_F⊆ E(G) a^k(F)(∏_e∈ Fb_e) c^bc(F).
    Bollobás–Riordan polynomial!dichromatic version

It is equivalent to the Bollobás-Riordan polynomial BR_G(X,Y,Z) due to the relations

    Z_G(a,,c)= (ac)^k(G)BR_G(ac,c,c^-1) ,


    BR_G(X,Y,Z)= (∏_e∈ E(G)y_e) (YZ)^-v(G)X^-k(G)
    Z_G(XYZ^2,{x_eYZ/y_e},Z^-1) ,

where on the right-hand side of the first equation we use the Bollobás-Riordan polynomial with weights x_e:=b_e, y_e:=1. 




 §.§ The arrow version of the Bollobás-Riordan polynomial.


The arrow version of the Jones polynomial was introduced in <cit.> as far reaching generalization of the classical Jones polynomial for virtual links. The Thistlethwaite-type theorem for this polynomial was obtained in <cit.>. 


An arrow ribbon graph is a ribbon graph together with
an arrow structure on it which is a (possibly empty) set of arrows tangent to the boundaries of the (vertex- and edge-) discs of the decomposition.
Two arrow graphs are equivalent if there is a homeomorphism between the corresponding surfaces respecting the decompositions and the orientations of the arrows.
The endpoints of segments along which the edges are attached to the vertices divide the boundaries of (vertex- and edge-) discs into arcs.
The arrows may slide along these arcs but may not slide over the end-points of the arcs or each other. Each arc may contain several arrows.


So, if there are several arrows on an arc, then only their order on the arc is relevant, not their actual position on the arc. 

Here are some examples.

    -42ag-ex14000-34ag-ex24000-42ag-ex375040


#1BR_#1
In the presence of an arrow structure on a ribbon graph G we can extend
the Bollobás-Riordan polynomial to the arrow Bollobás-Riordan polynomial 
<cit.> 
adding new variables K_c reflecting the arrow structure:

    G:=∑_F⊆ E(G) 
      (∏_e∈ Fx_e) (∏_e∉Fy_e) 
      X^r(G)-r(F)Y^n(F)Z^k(F)-bc(F)+n(F)∏_f∈∂(F) K_c(f).
    Bollobás–Riordan polynomial!arrow version

Here the independent variables K_c(f) are assigned to each boundary component with 
c(f) being equal to half of the number of arrows along the boundary component f remaining after cancellations of all pairs of arrows which are next to each other and pointing in the same direction.

    -25ar-can1502030 -2toto2500 
          K_1    -25ar-can2502030 -2toto2500 
          K_1/2    -25ar-can3502030 -2toto2500 
          K_2

We set K_0=1. One may note that whenever the number of arrows is odd on a boundary component, the associated variable is always K_1/2.
Thus the arrow Bollobás-Riordan polynomial G becomes a polynomial in infinitely many variables 
x_e, y_e, X, Y, Z, K_1/2, K_1, K_2, ….
Note that, for a concrete graph G only finitely many K's appear in G.


For the arrow graph G shown on the leftmost column in the table, there are eight spanning subgraphs. Their parameters and the corresponding monomial in K's are shown.


    [ 8ag-ex3(23,30)e_1(40,24)e_2(40,-5)e_356305                                 8agBBB5200                                 8agBBA5200                                15agBAB5200                                15agBAA5200;                                 (k,r,n,bc)                                  (1,1,1,2)                                  (1,1,0,1)                                  (1,1,0,1)                            (2,0,0,2)(0,12);                                   ∏ K_c(f)                                      K_1^2                                        K_1                                        K_1                                    K_1/2^2;                                                                           8agABB56400                                 8agABA5600                                10agAAB5600                                10agAAA5600;                                        2-5                                  (1,1,2,1)                                  (1,1,1,1)                                  (1,1,1,1)                            (2,0,1,2)(0,12);                                                                                   K_1                                        K_1                                          1                                    K_1/2^2 ]



    [                                                                          G                                                                          = y_1x_2x_3YK_1^2+y_1y_2x_3K_1+y_1x_2y_3K_1+
                  y_1y_2y_3XK_1/2^2;                                                                                  +x_1x_2x_3Y^2Z^2K_1+x_1y_2x_3YZK_1+x_1x_2y_3YZ+x_1y_2y_3XYZK_1/2^2 . ]




§ THE RELATIVE TUTTE POLYNOMIAL OF PLANAR GRAPHS WITH DISTINGUISHED EDGES.
 

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

We will use only plane relative graphs.


The medial graph M(G), see for example <cit.> or
 <cit.>, of a ribbon graph G is a 4-valent graph embedded in the same surface as G and constructed in a standard way. Consider the core graph  of G as naturally embedded in G. Place a vertex at the center of each edge of . These will be the vertices of M(G). The centers of edges of
 adjacent in the cyclic ordering around a vertex of  are connected by arcs following the boundary of G and not intersecting . These will be the edges of M(G). 
medial graph

Here is an example of the construction for a plane graph. 

    -60med22502070

The medial graph can be considered as an image of an immersion of several circles into the plane having only double points at the vertices of M(G) as intersections (and self-intersections). The number of these circles is denoted by δ(G).

The last ingredient in definition of the relative Tutte polynomial is a function ψ(G) of two variables d and w defined for plane ribbon graph G as follows

    ψ(G):=d^δ(G)-k(G)w^v(G)-k(G) .

This function is block-invariant, which means that its value on a one-point join of two graphs G_1 and G_2 does depend on the choice of identifying vertices of G_1 and G_2. 


Let G be a relative plane graph with the distinguished set of 0-edges H.
We define the relative Tutte polynomial
relative Tutte polynomial by the equation

    T_G,H(X,Y,ψ):=∑_F ⊆ G∖ H 
             (∏_e ∈ Fx_e) (∏_e ∈Fy_e) 
             X^k(F∪ H)-k(G)Y^n(F)ψ (H_F) ,

here, abusing notation, we use F, H, F ∪ H etc. both for denoting the subsets of edges and the spanning subgraph of G with those edges;  F:=G ∖ (F∪ H); and 
H_F is the plane graph obtained from F ∪ H by contracting all edges of F. 


Remarks. 

1. The relative Tutte polynomial was introduced by Y. Diao and G. Hetyei in <cit.>, 
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 (M. Carnovale, Y. Dong, J. Jeffries) at the Ohio State University summer program “Knots and Graphs" in 2009.
However, similar expressions may be traced back to L. Traldi 
<cit.> 
for the non-relative case, and to S. Chaiken <cit.> 
for the relative case of matroids. 

2. The function ψ in <cit.> can be obtained from ours by the substitution w=1. 

3. Another difference with <cit.> is that we are using a doubly weighted version of the relative Tutte polynomial with weights (x_e,y_e) of an edge e∈ G∖ H.

4. In the process of constructing the graph H_F by contracting the edges of F in F ∪ 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 ∪ H are plane graphs, then the graph 
H_F is also embedded in the plane.

5. While the medial graph of the planar graph H_F depends on the embedding of H_F in the plane, the number δ(H_F) does not (see <cit.>). It depends only on the abstract graph H_F.
This was proved in the paper <cit.>, 
which showed that δ(H_F)= log_2|T(H_F;-1,-1)| + 1. 



 §.§ From ribbon graphs to relative plane graphs.


Here we describe a construction from <cit.> 
relating ribbon graphs and planar relative graphs.

The manner in which we draw ribbon graphs suggests that we consider a projection π: G→^2 with singularites 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 these singularities the projection is one-to-one. In fact we use this idea on the medial graph M(G).

    -30singular2(45,60)R(25,40)π(-5,-10) Possible singularities of the projection4000-20singular(60,50)R(30,30)π605045

The image B:=π(M(G)) 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(G) will be called regular vertices, and the vertices that arise from the singularities of the projection will be called 0-vertices. 
The faces, the connected components of the complement of B in the plane, can be colored in white and green in checkerboard manner.
Place a vertex on each green face and connect the vertices corresponding to the faces sharing a vertex of B by an edge through the corresponding vertex of B. We obtain get a plane graph 
C(B) whose medial graph is B, M(C(B))=B. This procedure is similar to taking the plane dual,
only now we place a vertex only on green faces, not on every face, and th edges of C(B) go not across the edges of B but across the vertices of B.
We consider C(B) as a relative plane graph whose 0-edges are those which pass through the 
0-vertices of B.

The constructed relative plane graph C(B) clearly depends on the projection π and on the position of the 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 below shows two possibilities for C(B) depending on the position of a vertex of the medial graph M(G).



    -100rg1a(225,65)B(285,65)C(B)(40,22)π(G)(137,75)M(G)(53,135)G(33,100)π32035100

In this figure the 0-edges of C(B) are drawn as dashed lines.
 




 §.§ From relative plane graphs to ribbon graphs.
 

Conversely, from a relative plane graph C we may construct a ribbon graph G. Consider the spanning subgraph H of C whose edges are the 0-edges of C. Construct its medial graph M(H). Consider it as an immersion of a collection of (̣H) circles with only transverse double points as singularities. 
We construct a ribbon graph G with (̣H) vertices corresponding to the circles of the medial graph M(G). The edges of G correspond to regular edges of C. They glued to the 
vertex-discs according to the intersection of a small neighborhood of a regular edge with the arcs of the medial graph. Namely, we can label small arcs on M(G) at which the regular edges 
intersect M(G) by arrows following counterclockwise orientation of the plane. Then we glue ribbons along the corresponding arcs of the vertex-discs.  





    -80pg-rg1(38,10)C(173,4)H320070


    -80pg-rg2(314,16)G320080

 



 §.§ Relation to the Bollobás–Riordan polynomial.
 


Suppose G is a ribbon graph, and C is a relative plane graph associated to a projection of G with H as a spanning subgraph corresponding to the zero-edges. Or, equivalently, assume C is a relative plane graph and G is the ribbon graph arising from C. 

Then under the substitution w=√(X/Y), d=√(XY),

    X^ Y^Ṯ_C,H(X,Y,ψ)=BR_G( X,Y,1/√(XY) ) ,

where :=k(C)-k(G)-$̱ and:̱=-1/2(v(G)-v(C)). Remarks.  1. It is an interesting consequence of this theorem that the specialization 
(w=√(X/Y), d=√(XY)) of the relative Tutte polynomial does not depend on the various  choices made in the construction of the relative plane graph. 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πand, more generally, the moves preserving the relative Tutte polynomial.

 2. The construction ofCfromGand back can be generalized to a wider class of projectionsπ. We can require that only the restriction ofπto the boundary ofGbe 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 above. 



 §.§ Dual relative plane graphs


LetCbe a relative plane graph with 0-edgesH. The  dual ofC, denotedC^*is formed by taking the dual ofCas a plane graph, and labeling the edges ofC^*which intersect 0-edges ofCas the 0-edges ofG^*. Note that for relative plane graphs(C^*)^*=C, as with usual planar duality.relative graph!dual

The following theorem generalizes the classical relation for the Tutte polynomials of dual plane graphs,T(C;x,y)=T(C^*;y,x), to relative plane graphs. 

 
Under the substitution w=√(X/Y), d=√(XY), we have
X^a(C,H)Y^b(C)T_C,H(X,Y,ψ)=
Y^a(C^*,H^*)X^b(C^*)T_C^*,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 C^* that intersects e, and    a(C,H) = (|E(C ∖ H)|-v(C))/2+k(C) ,    
b(C) = v(C)/2 .


§ THE LAS VERGNAS POLYNOMIAL.
𝒞
M. Las Vergnas <cit.> came to his polynomials of graphs on surfaces through his general approach to matroid perspectives. It turns out that  for a (ribbon) graph on a surface with the edge setE, there is a geometric (Poincaré) dual graphG^*. For this graph there is a dual matroid to its cycle matroid,((G^*))^*, which is the bond matroid ofG^*. Then the natural bijection of the ground sets((G^*))^*→(G)forms a matroid perspective according to <cit.>. The Tutte polynomial of a perspectiveM→M'is a polynomialT_M→M'(x,y,z)in three variables defined byT_M→ M' := ∑_F⊆ M (x-1)^r_M'(E)-r_M'(F) (y-1)^n_M(F)  
  z^(r_M(E)-r_M(F))-(r_M'(E)-r_M'(F)),where in the rank and nullity functions, we use the subscript to indicate at which matroid the function fuction is considered in.

 Properties (<cit.>). The usual Tutte polynomial of matroidsMandM'can be recovered from the Tutte polynomial of matroid perspective in the following ways:[                        T(M;x,y) = T_M→M(x,y,z) ;;                     T(M;x,y) = T_M→M'(x,y,x-1) ;; T(M';x,y) = (y-1)^r(M)-r(M') T_M→M'(x,y,1/y-1) . ]The  Las Vergnas polynomial of G, LV_G(x,y,z),  is the Las Vergnas polynomial of the matroid perspective ((G^*))^*→(G).  Las Vergnas polynomial

IfGis a planar graph, then the Whitney planarity criteria claims that the matroid((G^*))^*is isomorphic to(G). So the matroid perspective is the identity, and then the Las Vergnas polynomial is equal to the classical Tutte polynomial ofG.


Let G be a graph with one vertex and two loops embedded into a torus as shown. Then the dual graph G^* is isomorphic to G.
-20rg-torus(0,45)G10000-20rg-torus-d(80,50)G^*1003525
In this case the bond matroid M=((G^*))^* has rank 2, and the cycle matroid M'=(G) has rank 0. 
For any subset F: r_M(F)=|F|, n_M(F)=0, and r_M'(F)=0. We have
LV_G(x,y,z)=z^2+2z+1 .

§ THE KRUSHKAL POLYNOMIAL.
Σϰ̨ im
The most general topological polynomial for graphs on surfaces was discovered by V. Krushkal in his research in topological quantum field theories and the algebraic and combinatorial properties of models of statistical mechanics <cit.>. 

Originally V. Krushkal  <cit.> defined his polynomial for orientable surfaces only. Here we follow the exposition of
Clark Butler <cit.> who extended the definition to non-orientable surfaces.


Let G be a graph embedded in a surface . The embedding does not have to be cellular and the surface  does not have to be orientable.
Then the Krushkal polynomial is defined by

K_G,(X, Y, A, B) := ∑_F⊆ G X^k(F)-k(G)
Y^k(∖ F)-k() 

A^s(F)/2 B^s^⊥(F)/2, Krushkal polynomial
where the sum runs over all spanning subgraphs considered as ribbon graphs, and the parameters 
s(F) and s^⊥(F) are defined by
s(F):= 2k(F)-χ(F),    
s^⊥(F):= 2k(∖ F)-χ(∖ F)

Here χ(F) (resp. χ(∖ F))
stands for the Euler characteristic of the surface F 
(resp. ∖ F) obtained by gluing a disc to each boundary component of the ribbon graph F (resp. 
∖ F).

As was outlined in Section <ref>, for orientable surfaces the parameters s and 
s^⊥ are equal to twice the genus of the corresponding surfaces, and for non-orientable surfaces they are equal to the number of Möbius bands one has to glue into k(F) and 
∖ F spheres to obtain a homeomerphic surfaces
 Remarks.  1.  In the orientable case V. Krushkal  <cit.> used
a different expression for the exponent$̨ of Y, as the dimension of the kernel of the map of the first homology groups

    (̨F)=((H_1(F;) → H_1(;)))

induced by inclusion F↪. It was noted in <cit.> that this dimension is equal to 
(̨F)=k(∖ F)-k(). C. Butler observed in <cit.> that considering homology groups with coefficients in _2:=/2 leads to a topological interpretation of the exponents in the Krushkal polynomial for a general (not necessarily orientable) surface :

    [                k(∖ F)-k()                         = ((H_1(F;_2) → H_1(;_2))),;                      s(F)                         =                H_1(F;_2),;                    s^⊥(F)                         =              H_1(∖ F;_2). ]


2. In the orientable case V. Krushkal <cit.> indicated that the parameters s(F) and s^⊥(F) have another interpretation in terms of the symplectic bilinear form on the vector space H_1(;) given by the intersection number.
For a given spanning subgraph F, let V be its image in the homology group:

    H_1(;)⊃ V := V(F) := (H_1(F;) → H_1(;)) .

For the subspace V we can define its orthogonal complement V^⊥ in H_1(;) with respect to the symplectic intersection form. Then

    s(F)=(V/(V∩ V^⊥)) ,     
    s^⊥(F)=(V^⊥/(V∩ V^⊥)) .




 §.§ Relation to the previous polynomials.
 

Let G be a ribbon graph, or equivalently a cellular embedding of the graph in a surface 
:=G.


The Tutte polynomial is a specialization of the Krushkal polynomial:

    T(G;x,y)=(y-1)^s()/2 K_G,(x-1, y-1, y-1, (y-1)^-1).




The unweighted (with all edge weights equal to 1, x_e=y_e=1) Bollobás-Riordan polynomial is a specialization of the Krushkal polynomial:

    BR_G(X,Y,Z)=Y^s(G)/2 K_G,(X,Y,YZ^2,Y^-1).




The Las Vergnas polynomial is a specialization of the Krushkal polynomial:

    LV_G(x,y,z) = z^s(G)/2 K_G,(x,y,z^-1,z).





 §.§ Properties.



    K_G,={[ K_G/e, + K_G-e,                ;                                ;   (1+ X)· K_G/e                ;   (1+ Y)· K_G-e                ;                                 ].


    K_G_1⊔ G_2,_1⊔_2 = K_G_1,_1· K_G_2,_2,





 §.§ The contraction/deletion properties of these polynomials.


The contraction/deletion properties for BR_G, for K_G,, and for LV_G, are not quite the same. The problem arises when deletion of an edge of a ribbon graph changes its genus. The genus might decrease by 1 with the removal of an edge.
For example, if we delete a loop from the ribbon graph G of Example <ref>, then the resulting graph with a single loop will have genus zero. So, while in the Bollobás-Riordan approach it is considered as a ribbon graph embedded into a sphere, in the Krushkal approach it is still embedded into the torus.
We cannot apply the substitution (<ref>) to that graph
since its embedding on the torus is no longer cellular.
Thus the Krushkal polynomial does not satisfy the contraction/deletion property in the sense of the Bollobás and Riordan polynomial.
The Las Vergnas polynomial LV_G,(x,y,z) does not satisfy either the contraction/deletion property in the sense of Bollobás and Riordan.
The contraction/deletion property for it discussed in <cit.>.


This is an example of a calculation of the three polynomials.
Here G is a graph on the torus with two vertices and three edges a, b, and c considered as a ribbon graph. Its dual G^* has one vertex and three loops. We use the same symbols a, b, c to denote the corresponding edges of G^* as well.

    G=-22G-torus(52,33)a(15,15)a(46,8)b(70,24)b(28,13)c(85,35)c903035 
    =-13cG-rg(37,32)a(15,-7)b(33,-6)c5000        
    G^*=-22Gd-torus(28,50)a(72,16)b(7,26)c903535

The matroid M'=(G) is of rank 1, and for any nonempty subset F, r_M'(F)=1. The cycle matroid (G^*) of the dual graph is of rank zero because G^* has only loops. So its dual M=((G^*))^* has rank 3, all subsets F are independent and r_M(F)=|F|. The next table shows the values of various parameters and the contributions of all eight subsets F⊆{a,b,c} to the three polynomials.

    [                                                     F                          ∅                        {a}                        {b}                      {a,b}                        {c}                      {a,c}                      {b,c}                    {a,b,c};                                                  k(F)                          2                          1                          1                          1                          1                          1                          1                          1;                        ———                       (̨F)                          0                          0                          0                          0                          0                          0                          0                          0;                        ———                       s(F)                          0                          0                          0                          0                          0                          0                          0                          2;                        ———                     s^⊥(F)                          2                          2                          2                          0                          2                          0                          0                          0;    ———(20,0)60pt90Krushkal                       K_G,                         XB                          B                          B                          1                          B                          1                          1                          A;                                                r_M(F)                          0                          1                          1                          2                          1                          2                          2                          3;                        ———                    r_M'(F)                          0                          1                          1                          1                          1                          1                          1                          1;                        ———                     n_M(F)                          0                          0                          0                          0                          0                          0                          0                          0; ———(20,0)50pt90Las Vergnas                       LV_G                   (x-1)z^2                        z^2                        z^2                          z                        z^2                          z                          z                          1;                                                  k(F)                          2                          1                          1                          1                          1                          1                          1                          1;                        ———                       n(F)                          0                          0                          0                          1                          0                          1                          1                          2;                        ———                      bc(F)                          2                          1                          1                          2                          1                          2                          2                          1;        ———(20,0)50pt900pt0                       BR_G                          X                          1                          1                          Y                          1                          Y                          Y                     Y^2Z^2;                            ]

Thus

    K_G,=3+3B+XB +A,    
    LV_G=3z+3z^2+(x-1)z^2+1,


    BR_G=3Y+3+X+Y^2Z^2.

One can readily confirm the relations (<ref>) and (<ref>) from here.

Now if we contract the edge c, the graph G/c will still be cellularly  embedded in the same torus .
The right four columns of the table above give the following polynomials:

    K_G/c,=B+2+A,    
    LV_G/c=z^2+2z+1,    
    BR_G/c=1+2Y+Y^2Z^2.

Meanwhile if we delete the edge c, then 

    K_G-c,=XB+2B+1 .

But the graph G-c is not cellularly embedded into the torus  any more. Thus the Las Vergnas and the Bollobás-Riordan polynomials are not defined for it. The ribbon graph G-c, after gluing discs to its two boundary components, results in the sphere G-c=S^2. Thus the graph G-c embeds cellularly into the sphere S^2. For this embedding we have

    K_G-c,S^2=X+2+Y,    
    LV_G-c=(x-1)+2+(y-1),    
    BR_G-c=X+2+Y.

Therefore 

    K_G,=K_G-c,+K_G/c,        
    BR_G=BR_G-c+BR_G/c ,

but

    K_G,≠K_G-c,S^2+K_G/c,        
    LV_G≠LV_G-c+LV_G/c .





 §.§ Duality for the Krushkal polynomial.
 

The classical relation, T(G;x,y)=T(G^*;y,x), for the Tutte polynomials of dual plane graphs can be generalized to a relation for the Krushkal polynomial of arbitrary ribbon graphs. 


Let G be a ribbon graph naturally embedded into the surface =G, and G^*⊂ be its Poincaré (geometric) dual ribbon graph.Then

    K_G,(X, Y, A, B)=K_G^*,(Y, X, B, A) .
Krushkal polynomial!duality




§ QUASI-TREES.
 


A quasi-tree is a ribbon graph with one boundary component.
quasi-tree

 
Quasi-trees, as well as a notion of activities relative to a spanning quasi-tree, were 
introduced and used for a quasi-tree expansion of the Bollobas-Riordan polynomial in 
<cit.> 
Their results were generalized to non-orientable ribbon graphs in <cit.> 
(see also an unpublished manuscript <cit.>). 

We denote the set of all spanning quasi-trees of a given ribbon graph G by 𝒬_G. 

If G is a plane graph of genus zero, then a spanning quasi-tree is a spanning tree. But for non-plane graphs the set of spanning quasi-trees is bigger than the set of spanning trees. In Example <ref>, the whole graph consisting of a vertex and two loops on a torus is a quasi-tree but, of course, not a tree. The table in Example <ref> shows that the ribbon graph G has four spanning quasi-trees {a}, {b}, {c}, and {a,b,c}.



 §.§ Quasi-tree activities.
 


Let ≺ be a total order on edges E(G) of a ribbon graph G, and Q be a spanning quasi-tree of G. Tracing the boundary component of Q we will get a round trip passing the boundary arcs of each edge-ribbon twice, on opposite sides of a ribbon separating it from faces for edges in Q and on opposite sides of a ribbon separating it from vertices for edges not in Q. This can be encoded in a chord diagram C_G(Q) consisting of a circle corresponding to the boundary of Q with pairs of arcs corresponding to the same edge-ribbon connected by  chords.  Thus the set of chords inherits the total order ≺.


An edge is called live if the corresponding chord is smaller than any chord intersecting it relative to the order ≺. 
Otherwise it is called dead. edge!live/dead
activities! w.r.t. quasi-tree
quasi-tree!activities



For a plane graph G a spanning quasi-tree is a spanning tree and the notion of live/dead consides with the classical Tutte's notion of
active/inactive. But for the higher genus the notions are different, so we follow the terminology live/dead of <cit.>, 
where a reader can find further discussion and examples.
Also, this notion is different from the embedding-activities introduced by O. Bernardi in <cit.>. 



In Example <ref> of a single vertex and two loops there are two spanning quasi-trees consisting of a vertex without edges and the whole graph. Both of them have a chord diagram depicted on the left in the picture below.
In Example <ref> there are four spanning quasi-trees. All of them have the same chord diagram, depicted on the right in the picture below.

    -10cd-240300        -10cd-34000

In either case there is only one live edge, the smallest in the order ≺. It could be either internal or external depending on whether it belongs or does not belong to the spanning quasi-tree.



Here we consider a more complicated example of a non-orientable ribbon graph G following 
<cit.>.

    -20rg-ex4(10,20)1(60,37)2(60,-5)3(116,50)41203020

The edges are labeled by natural numbers, so their order is the obvious one: 
1≺ 2≺ 3≺ 4.  There are four spanning quasi-trees 
Q_{2}, Q_{3}, Q_{2,3}, and Q_{2,3,4}, where the subscript indicates the set of edges included in the quasi-tree. Their chord diagrams look like this:

    C_G(Q_{2})=
    -17cd-4-q2(18,28)1(28,22)2(11,29)3(26,12)4402030,     
    C_G(Q_{3})=-17cd-4-q3(18,28)1(32,21)2(11,30)3(20,4)44000,


    C_G(Q_{2,3})=-17cd-4-q23(17,28)1(28,20)2(11,27)3(4,12)440020,     
    C_G(Q_{2,3,4})=-17cd-4-q234(17,28)1(28,19)2(11,27)3(14,8)44000.

Thus 1 is always an externally live edge, 2 is also live, and 3 is internally live for Q_{2,3,4}. We depict the chords corresponding to dead edges by dashed lines. Also some chords on the pictures are marked by a cross. These correspond to non-orientable edges according to the next definition. 


 
An edge of a non-orientable ribbon graph G can be classified as orientable or 
non-orientable relative to a spanning quasi-tree Q for G.
Choose an orientation on the boundary circle ∂ Q of Q and on the boundary of each edge-ribbon considered as a topological disc.
Then, tracing ∂ Q in the direction of the orientation we meet exactly two arcs of each-ribbon edge. If the orientations of these two arcs are coherent, either both along the tracing, or both against the tracing, then we call the edge orientable relative to 
Q. Otherwise we call it non-orientable.
edge!orientable/non-orientable

It is easy to see that this property does not depend on the choice of the orientations. Essentially the chord diagram C_G(Q) depicts a partial dual ribbon graph G^E(Q) in the sense of <cit.>. All edges of G^E(Q) are loops. For loops we can define orientability in the usual topological sense which coincides with our definition above.


For the graph G in Example <ref> consider a spanning quasi-tree
 and choose the orientations as follows.

    -20rg-ex4(10,20)1(60,37)2(60,-5)3(116,50)41204020 -2toto2500 -20rg-ex4or(14,20)1(60,40)2(60,-4)3(128,50)413000

We observe that the two relevant arcs of edge 1 are oriented coherently to
the direction of ∂ Q_{2,3}. For the other edges this is not true.
So 1 is an orientable edge relative to Q_{2,3}, and the other three
edges are not.

Thus each edge has three bits of additional information relative to a spanning tree Q: internal/external, live/dead, and orientable/non-orientable. This information is used in the quasi-tree expansion of the Krushkal polynomial in next subsection.
 



 §.§ Quasi-tree expansion of the Krushkal polynomial.
 


With each spanning quasi-tree Q of a ribbon graph G we associate 


  ∙ a spanning ribbon subgraph F(Q) by deleting the (internally) live orientable edges of Q;

  ∙ an abstract (not embedded) graph Γ(Q) whose vertices are the connected components of F(Q) and whose edges are the internally live orientable edges of Q.



We will also need a dual construction. For a ribbon graph G, regarded as a graph cellularly embedded into the surface =G, we consider the Poincaré dual graph ribbon graph G^*. A spanning subgraph F for G determines a spanning subgraph F^⋆ containing all edges of G^* which do not intersect edges of F. Note that F^⋆ is not a dual ribbon graph for F, its edge set is rather the complement of the set of edges of G^* corresponding to the edges of F. The asterisk applied to an entire graph means the dual graph, but the star applied to a subgraph means the spanning subgraph given by this construction.

The spanning subgraphs F and F^⋆ have common boundary and their gluing along this common boundary gives the whole surface .
In particular, for a spanning quasi-tree Q for G, the subgraph Q^⋆ is a quasi-tree for G^*. Moreover, these quasi-trees have the same chord diagrams, C_G(Q)=C_G^*(Q^⋆). Also the natural bijection of edges of G and G^* leads to the total order ≺^* on edges of 
G^* induced by ≺. Consequently the property of an edge of being live/dead relative to 
Q is mappeded by the bijection to the same property relative to Q^⋆. Also one may check that the property of an edge of being orientable/non-orientable relative to Q is preserved by the bijection to the same property relative to Q^⋆. But its property of being internal/external is changed to the opposite.


Now we can apply definition <ref> to the quasi-tree of G^* just constructed.


  ∙ We obtain a spanning ribbon subgraph F(Q^⋆) by deleting the internally live orientable edges of Q^⋆. They correspond to externally live orientable edges of Q.

  ∙ We obtain an abstract graph Γ(Q^⋆) consists of vertices that are the connected components of F(Q^⋆) and edges that are the internally live orientable edges of 
Q^⋆.




For a ribbon graph G, the Krushkal polynomial has the following expansion over the set of quasi-trees. 

    K_G(X,Y,A,B)=∑_Q∈𝒬_G
    A^s(F(Q))/2T_Q · B^s(F(Q^⋆))/2T_Q^⋆ ,

where T_Q=T(Γ(Q);X+1,A+1) and T_Q^⋆=T(Γ(Q^⋆);Y+1,B+1) stand for the classical Tutte polynomial of the abstract graphs
Γ(Q) and Γ(Q^⋆), and the parameter s was defined in <ref>.
Krushkal polynomial!quasi-tree expansion



For the graph G on the torus with a single vertex and two loops, parallel and meridian, in Example <ref> we have two spanning quasi-trees consisting of a vertex only and the whole graph, as in Example <ref>.
For Q being a vertex, both F(Q) and Γ(Q) consist of one vertex. So s(F(Q))=0 and 
T_Q=1. The dual quasi-tree Q^⋆=D^* is the whole graph in this case, and one of its loops is internally active. 
So F(Q^⋆) consists of one vertex with a loop attached to it. 
The abstract graph Γ(Q^⋆) is the same. Thus s(F(Q^⋆))=0 and 
T_Q^⋆=T(Γ(Q^⋆);Y+1,B+1)=B+1. Therefore the contribution of the single vertex spanning quasi-tree is B+1.
For the second quasi-tree Q, the whole graph, the situation is completely symmetrical. Its dual quasi-tree Q^⋆ consists of a single vertex, and its contribution is A+1. So

    K_G(X,Y,A,B)=A+2+B,

as was mentioned in Example <ref>.



For the graph G in Examples <ref> and <ref> with edges labeled a, b, and c there are four spanning quasi-trees Q_{a}, Q_{b}, Q_{c}, and Q_{a,b,c}.
For each of them a is a live edge and b and c are dead relative to the total order a≺ b≺ c. The next tables show the ribbon graphs
F(Q), F(Q^⋆) and abstract graphs Γ(Q), Γ(Q^⋆) and their contributions to the Krushkal polynomial for each of these spanning quasi-trees.

    [                                Q                            Q_{a}                            Q_{b}                            Q_{c}                        Q_{a,b,c};                             F(Q)                    -5F_Q_a501525             -13F_Q_b(15,-7)b5000             -13F_Q_c(33,-6)c5000   -13F_Q_abc(15,-7)b(33,-6)c5000;               (0,15) A^s(F(Q))/2                                1                                1                                1                                1;                             Γ(Q)                    0Ga_Q_a302015                       0Ga_Q_b600                       0Ga_Q_b600                  -10Ga_Q_abc2000;                              T_Q                              X+1                                1                                1                              A+1;                                 ;                              Q^⋆                          Q^⋆_{a}                          Q^⋆_{b}                          Q^⋆_{c}                      Q^⋆_{a,b,c};                           F(Q^⋆) -12F_Qst_a(15,-7)b(33,-6)c502525           -12F_Qst_b(15,-5)c3000           -12F_Qst_c(20,-6)b3000                  -2F_Qst_abc1400;             (0,15) B^s(F(Q^⋆))/2                                B                                1                                1                                1;                           Γ(Q^⋆)                     0Ga_Q_b62015                  -10Ga_Q_abc2000                  -10Ga_Q_abc2000                       0Ga_Q_b600;                            T_Q^⋆                                1                              B+1                              B+1                                1;                                  ]

So the Krushkal polynomial is equal to

    K_G=(X+1)B+(B+1)+(B+1)+(A+1)=XB+A+3B+3,

which coincides with the direct calculation in Example <ref>



Now we consider the example <ref> of a non-orientable ribbon graph
G and its dual G^* from <cit.>.

    G=-20rg-ex4(10,20)1(60,37)2(60,-5)3(116,50)41203035        
    G^*=-40rgd-ex4(25,31)1(38,60)2(38,10)3(100,50)410000

It has four spanning quasi-trees Q_{2}, Q_{3}, Q_{2,3}, and Q_{2,3,4}. Again we indicate the ribbon graphs
F(Q), F(Q^⋆) and abstract graphs Γ(Q), Γ(Q^⋆) and their contributions to the Krushkal polynomial.

    [                               Q                           Q_{2}                           Q_{3}                         Q_{2,3}                       Q_{2,3,4};                            F(Q)                   -5F_Q_a501525            -10F_Q_3(15,-7)35000   -16F_Q_23(30,22)2(15,-6)35000          -20F_Q_234(55,20)45500;              (0,15) A^s(F(Q))/2                               1                               1                           A^1/2                               1;                            Γ(Q)                   0Ga_Q_a302015                      0Ga_Q_b600                      0Ga_Q_b600                  -5Ga_Q_2343500;                             T_Q                             X+1                               1                               1                           X+A+2;                                ;                             Q^⋆                         Q^⋆_{2}                         Q^⋆_{3}                       Q^⋆_{2,3}                     Q^⋆_{2,3,4};                          F(Q^⋆) -18F_Qst_2(18,6)3(57,26)4572525  -18F_Qst_3(22,32)2(53,26)45700         -12F_Qst_23(53,26)45700                     -5F_Q_a5000;            (0,15) B^s(F(Q^⋆))/2                               B                               B                           B^1/2                               1;                          Γ(Q^⋆)                   0Ga_Q_a302015                     0Ga_Q_a3300                   0Ga_Q_a302015                   0Ga_Q_a302015;                           T_Q^⋆                             Y+1                             Y+1                             Y+1                             Y+1;                                 ]

So the Krushkal polynomial is equal to

    K_G=(X+1)(Y+1)B+(Y+1)B+(Y+1)A^1/2B^1/2+(X+A+2)(Y+1).

One may check this answer by a direct calculation according to the definition <ref>.


Clark Butler's Theorem <ref> specializes to the quasi-tree expansion of the Bollobás-Riordan polynomial from <cit.> 
in the orientable case and from <cit.> 
in the non-orientable case.
Also it specializes to a quasi-tree expansion of the Las Vergnas polynomial, see <cit.>. It would be very interesting to find such an expansion for the Tutte polynomial of matroid perspectives entirely in the matroid setting.




ABCDE

MR2998838 R. Askanazi, S. Chmutov, C. Estill, J. Michel, J., P. Stollenwerk,
  Polynomial invariants of graphs on surfaces, Quantum Topology 3 (2013) 77–90.

MR3157807 C. Bajo, B. Burdick, S. Chmutov, Evaluations of the 
   Tutte-Krushkal-Renardy polynomial for cell complexes. 
   Journal of Combinatorial theory, Ser.A 123 (2014) 186-ֲ01.
   Preprint . 

MR2428901 O. Bernardi, A characterization of the Tutte polynomial via  
   combinatorial embeddings, Ann. Comb. 12(2) (2008) 139–153. 

MR1851080 B. Bollobás, O. Riordan, A polynomial of graphs on orientable 
   surfaces, Proc. London Math. Soc. 83 (2001) 513–531. 

MR1906909 B. Bollobás and O. Riordan, A polynomial of graphs
   on surfaces, Math. Ann. 323 (2002) 81–96. 

MR1215962 R. Bott, Reflections of the theme of the posters,
   in Topological Methods in Modern Mathematics, A Symposium in Honor 
   of John Milnor's Sixtieth Birthday, Goldberg and Phillips (1993) 125–135. 

MR2994589 R. Bradford, C. Butler, S. Chmutov, Arrow ribbon graphs, 
	 Journal of Knot Theory and its Ramifications, 21(13) (2012) # 1240002 (16 pages).
   Preprint . 
   
But C. Butler, A quasi-tree expansion of the Krushkal polynomial, 
   (2012). Preprint .

MR3390227 C. Butler, S. Chmutov, Bollobás-Riordan and relative Tutte 
   polynomials. Arnold Mathematical Journal 1(3) (2015) 283-ֲ98.
   Preprint . 

MR0982858 S. Chaiken,  The Tutte polynomial of a ported matroid, 
   Journal of Combinatorial Theory, Ser.B 46 (1989) 96–117. 

MR2854567 A. Champanerkar, I. Kofman, N. Stoltzfus, N. Quasi-tree 
   expansion for the Bollobás-Riordan-Tutte polynomial, 
	 Bull. Lond. Math. Soc. 43(5) (2011) 972–984. 

MR2507944 S. Chmutov, Generalized duality for graphs on 
   surfaces and the signed Bollobás-Riordan polynomial, 
   Journal of Combinatorial Theory, Ser.B 99(3) (2009) 617–638.
   Preprint ,  

MR2962302 S. Chmutov, S. Duzhin, Y. Mostovoy, Introduction to 
   Vassiliev Knot Invariants.   
   Cambridge University Press (2012) ISBN 978-1-107-02083-2. (504 pages) 
   Preprint . 

MR2343139 S. Chmutov, I. Pak,  The Kauffman bracket of 
   virtual links and the Bollobás-Riordan polynomial,
   Moscow Mathematical Journal 7(3) (2007) 409–418. 
   Preprint . 
   
MR2460170 S. Chmutov, J. Voltz,  Thistlethwaite's theorem 
   for virtual links, 
   Journal of Knot Theory and Its Ramifications 17(10) (2008) 189֭–1198.
	 Preprint . 

MR2989987 M. D'Adderio, L. Moci, Arithmetic matroids, the Tutte 
   polynomial, and toric arrangements, 
	 Adv. Math. 232 (2013) 335–367.
   Preprint .	

MR2389605 O. Dasbach, D. Futer, E. Kalfagianni, X.-S. Lin, 
   N. Stoltzfus, The Jones polynomial and graphs on surfaces, 
   Journal of Combinatorial Theory, Ser.B 98 (2008) 384–399.
   Preprint .  

Dew E. Dewey, A quasitree expansion of the Bollobás-Riordan polynomial, 
		Available at .
		
MR3111544 Y. Diao, G. Hetyei, Relative Tutte polynomials for 
  colored graphs and virtual knot theory, 
  Combinatorics Probability and Computing 19 (2010) 343–֭369.
  Preprint . 
  
MR2794024 A. Duval, C. Klivans, J. Martin, 
   Cellular matrix-tree theorems,
   Trans. Amer. Math. Soc. 361(11) (2009) 6073–6114. 

DK H. A. Dye, L. H. Kauffman, Virtual crossing number and the arrow polynomial, 
   Journal of Knot Theory and Its Ramifications 18(10) (2009) 1335–1357. 

EMS J. Ellis-Monaghan, I. Sarmiento, A duality relation for the 
   topological Tutte polynomial, talk at the AMS sectional Meeting #1009, 
	 Bard College, 10/9/2005.
 
	 . 

MR3086663 J. Ellis-Monaghan, I. Moffatt, Graphs on Surfaces: Dualities,  
   Polynomials, and Knots, Springer (2013).
	
EMM1 J. Ellis-Monaghan, I. Moffatt, The Las Vergnas Polynomial for embedded 
   graphs, European Journal of Combinatorics 50 (2015) 97–114.
	 Preprint . 

MR2341831  H. Glover, D. Marušič, Hamiltonicity of 
   cubic Cayley graphs, J. Eur. Math. Soc. 9 (2007) 775- 787. 

MR1417567  H. Glover, T. Y. Yang, A Hamilton cycle in the 
   Cayley graph of the ⟨ 2,p,3⟩-presentation of 
   PSl_2(p), Discrete Math. 160 (1996) 149–163. 

MR1829620 C. Godsil, G. Royle, Algebraic graph theory, 
   GTM 207, Springer (2001). 

MR1855951 J. L. Gross, T. W. Tucker,
   Topological graph theory, Wiley (1987). 

GrYe J. L. Gross, J. Yellen editors, Handbook of Graph Theory,
   CRC Press (2004).

MR0830043 J. L. Harer, The virtual cohomological dimension of 
  the mapping class group of an orientable surface, 
  Invent. Math. 84 (1986) 157֭–176. 

He L. Heffter, Über das Problem der Nachbagebiete, 
   Math. Ann. 38 477–508. 

MR0720308 G. Kalai, Enumeration of Q-acyclic cellular complexes, 
	Israel J. Math. 45 (1983) 337–351. 

MR0935433 L. H. Kauffman, New invariants in knot theory,
   Amer. Math. Monthly 95 (1988) 195–242. 

MR1031266 L. H. Kauffman, A Tutte polynomial for signed graphs, 
   Discrete Appl. Math. 25 (1989) 105–127. 

MR1341841 M. Kontsevich, Feynman diagrams and low-dimensional
     topology, First European Congress of Mathematics II,
     Birkhäuser (1994)  97–121. 

MR2769192 V. Krushkal, Graphs, Links, and Duality on Surfaces, 
   Combinatorics, Probability and Computing 20 (2011) 267–287. 
   Preprint . 

KR V. Krushkal, D. Renardy, A polynomial invariant and 
   duality for triangulations. 
   Preprint . 

MR2036721 S. K. Lando, A. K. Zvonkin,
   Graphs on surfaces and their applications, Springer (2004). 

MR0587623 M. Las Vergnas, On Eulerian partitions of graphs,
   Graph Theory and Combinatorics 34, 
	 Pitman Advanced Publishing Program (1979) 62–75. 

MR0597150 M. Las Vergnas, On the Tutte polynomial of a morphism of matroids, 
   Annals of Discrete Mathematics 8 (1980) 7–20. 

MR2382735 M. Loebl, I. Moffatt, The chromatic polynomial of fatgraphs and its  
   categorification,Adv. Math. 217(4) (2008) 1558–1587. 
   
MR2368618 I. Moffatt, Knot Invariants and the Bollobás-Riordan Polynomial 
   of embedded graphs, European Journal of Combinatorics 29 (2008) 95–107. 
   Preprint . 

MR1844449 B. Mohar, C. Thomassen, Graphs on Surfaces,
   The Johns Hopkins University Press, 2001. 

MR0930077 K. Murasugi, On invariants of graphs with applications to knot theory, 
   Trans. AMS 314(1) (1989) 1–49. 
  
MR0919235 R. C. Penner, The decorated Teichmüller space of punctured   
   surfaces, Comm. Math. Phys. 113 (1987) 299֭–339. 

MR1036112 N. Reshetikhin, V. Turaev, Ribbon graphs and their
   invariants derived from quantum groups, Comm. Math. Phys. 127
   (1990) 1–26. 

MR2187739 A. Sokal, The multivariate Tutte polynomial (alias  
   Potts model) for graphs and matroids, in Surveys in Combinatorics, ed. Bridget S. Webb, 
	 Cambridge University Press (2005) 173–226. 
	 Preprint . 

MR0899051 M. Thistlethwaite, A spanning tree expansion for
   the Jones polynomial, Topology 26 (1987) 297–309. 

MR0955462 L. Traldi, A dichromatic polynomial for weighted graphs and link 
   polynomials, Proc. AMS 106 (1989) 279–286. 

MR2047240 L. Traldi, A subset expansion of the coloured Tutte polynomial, 
   Combinatorics Probability and Computing 13 (2004) 269–֭275. 

MR2552629 F. Vignes-Tourneret, The multivariate signed Bollobás-Riordan 
   polynomial, Discrete Math. 309 (2009) 5968–5981. 
   Preprint . 

MR2780852 F. Vignes-Tourneret, Non-orientable quasi-trees for the 
   Bollobás-Riordan polynomial, 
	 European Journal of Combinatorics 32(4) (2011) 510–532. 

MR1304401 Z. Wang, On Bott polynomials, 
   Journal of Knot Theory and Its Ramifications 3(4) (1994) 537–546.

MR1080738 T. Zaslavsky, Strong Tutte functions of matroids and graphs, 
   Trans. AMS 334(1) (1992) 317–347. 

MR1744869 T. Zaslavsky, A mathematical bibliography of signed and gain 
   graphs and allied areas, Electronic J. Combinatorics 5 (1998) DS8. 
  


 

