Polynomial Invariants for Arbitrary Rank $D$ Weakly-Colored Stranded Graphs

Polynomial Invariants for Arbitrary Rank $\boldsymbol{D}$
Weakly-Colored Stranded Graphs

Remi Cocou AVOHOU

R.C. Avohou

International Chair in Mathematical Physics and Applications, ICMPA-UNESCO
Chair,
072BP50, Cotonou, Republic of Benin<EMAIL_ADDRESS>
Received June 26, 2015, in final form March 14, 2016; Published online March
22, 2016

Polynomials on stranded graphs are higher dimensional generalization of Tutte
and Bollobás–Riordan polynomials [Math. Ann. 323 (2002), 81–96]. Here, we
deepen the analysis of the polynomial invariant defined on rank 3 weakly-
colored stranded graphs introduced in arXiv:1301.1987. We successfully find in
dimension $D\geq 3$ a modified Euler characteristic with $D-2$ parameters.
Using this modified invariant, we extend the rank 3 weakly-colored graph
polynomial, and its main properties, on rank 4 and then on arbitrary rank $D$
weakly-colored stranded graphs.

Tutte polynomial; Bollobás–Riordan polynomial; graph polynomial invariant;
colored graph; Ribbon graph; Euler characteristic

05C10; 57M15

##  1 Introduction

The polynomial invariant for $3D$ weakly-colored graphs introduced in [1] is a
polynomial invariant which extends both the Tutte and Bollobás–Riordan (BR)
polynomials [7, 17] from graph and ribbon graphs to a family of combinatorial
objects called stranded graphs. This polynomial obeys a particular
contraction/cut recurrence relation which replaces the contraction/deletion
relation satisfied by Tutte and BR polynomials. Let us review now in greater
details the context where these graphs appear and their invariant.

The objects that we investigate are called stranded graphs and they still
arouse the interest of the mathematicians and physicists [2, 3, 4, 9, 13].
Such stranded graphs are made with stranded vertices which are chord diagrams
and stranded edges which are collections of segments. In [9], it has been
proved that the colored version of these graphs are dual to simplicial pseudo-
manifolds in any dimension $D$. Restricted to $2D$, the same class of graphs
corresponds to ribbon graphs or rank 2 stranded graphs with vertices of
coordination 3. Considering the ribbon vertices as $0$-cells, lines or edges
as $1$-cells and faces as $2$-cells, ribbon graphs become two dimensional
cellular complexes. However, the cellular complex structure has been not yet
generalized for all stranded graphs in higher dimensions but only on those
which are colored [11]. In a colored graph, a $p$-cell or $p$-bubble is
defined as a connected subgraph made only of lines of $p$ chosen colors.

Colored tensor graphs are specific stranded graphs [9] on which we impose a
fixed coordination of vertices and an edge coloring. The contraction of an
edge modifies this coordination and then destroys the color structure. This
has led to the enlargement of the family of graphs from the colored tensor
graphs to what will be called weakly-colored (w-colored) stranded graphs for
which contraction and a notion similar to the deletion make sense.

Stranded vertices are furthermore decorated with half-edges called “half
lines” (or external legs in quantum field theory framework [10, 11]). The
graphs with decorated vertices are very useful in physics. For instance, it
was defined on these graphs a generalized Symanzik polynomial with very nice
properties in quantum field theory due to the importance of the external legs
[14]. The notion of half-edge [17] is consistent with the operation that
involves cutting an edge of a given graph. The cut of an edge of a graph means
removing this edge and let two half-edges attached to its incidence vertices
(or vertex in the loop situation). Moreover, this operation brings some
modifications on the “boundary of the graph”. The boundary graph encodes the
boundary of the simplicial complex dual to the stranded graph. We now
distinguish two kinds of faces: closed strands, homeomorphic to $S_{1}$ which
define the internal faces and the remaining which are homeomorphic to $(0,1)$
define the external faces.

The generalization of the universal invariant, namely Tutte polynomial, from
graphs to ribbon graphs [5, 6, 7, 8] was performed by Bollobás and Riordan by
adding two supplementary variables to the Tutte polynomial. One variable
stands for the orientability of the ribbon seen as surface and the other one
for an invariant related to the genus of the corresponding ribbon graph.

The Bollobás–Riordan polynomial invariant was generalized by Tanasa in [16]
where one supplementary variable keeps track of the sum of genera [12, 15] of
the $3$-bubbles (surfaces) of a rank 3 tensor graph. A similar procedure
proves to be applicable for finding an invariant on rank 3 w-colored graphs.
We emphasize that, several other potentially interesting invariant candidates
under contraction and cut can be identified. In $D\geq 4$, we must expect a
much richer structure of the possible invariants.

In this paper, we discover several possibilities when we deal with $D\geq 4$.
We provide two combinatorial methods to generate a generalized Euler
characteristic which can be used to define an extension of the invariant in
rank 3 determined in [1]. Furthermore, for each choice of invariant, it
appears possible to parametrize the invariant by a finite family of positive
rational numbers. As a consequence, the polynomial invariant built on these
invariants will acquire new parameters $\alpha_{k}\in\mathbb{Q}^{+}$,
$k=3,\dots,n$. The modified Euler characteristic
$\gamma_{n;\boldsymbol{\alpha}}$ of a rank $n\geq 3$ weakly-colored graph
$\mathcal{G}$ is given by

$\displaystyle\gamma_{n;\boldsymbol{\alpha}}=\frac{n(n-1)}{2}(V-E)+(n-1)F_{{\rm
int}}-(2+(n-2)\alpha_{3})B^{3}$
$\displaystyle\hphantom{\gamma_{n;\boldsymbol{\alpha}}=}{}+\sum_{k=4}^{n}\big{[}(k-1)\alpha_{k-1}-(n-k+1)\alpha_{k}\big{]}B^{k},$

where $V$, $E$, $F_{{\rm int}}$ and $B^{k}$ are respectively the number of
vertices, edges, internal faces and $k$-bubbles of $\mathcal{G}$. Our first
main result stated in Theorem 3.6 describes the relations satisfied by the
polynomial invariant in rank 4. By induction, we determine a polynomial
invariant on arbitrary rank $D$ w-colored graphs. Our second main result is
the contraction/cut recurrence relation (Theorem 4.5) satisfied by this
polynomial. The usual Tutte and BR polynomials can be recovered after
restricting to the proper graph theory rank and after an appropriate change of
variables.

The organization of the rest of the paper is the following. In the next
section, we give a brief review of the polynomial invariant on rank 3
w-colored stranded graphs. Section 3 is dedicated to the extension of this
polynomial on rank 4 w-colored stranded graphs. By an induction procedure we
generalize in Section 4, the rank 4 polynomial to arbitrary rank $D$ w-colored
stranded graphs. Finally, an appendix provides a detailed analysis of various
other interesting invariants which could be alternatively used for defining
new polynomials extending Tutte and BR in any dimension $D$.

##  2 Weakly-colored graphs and the rank 3 polynomial invariant

We briefly recall here the definition of the polynomial invariant defined for
rank 3 w-colored graphs introduced in [1]. We also address its main properties
which will find extension on higher rank graphs.

A graph $\mathcal{G}(\mathcal{V},\mathcal{E})$ is defined as a set of vertices
$\mathcal{V}$ and of edges $\mathcal{E}$ together with an incidence relation
between them. $\mathcal{G}(\mathcal{V},\mathcal{E})$ is stranded when its
vertices and edges are stranded.

######  Definition 2.1 (stranded vertex and edge).

A rank $D$ stranded vertex is a chord diagram that is a collection of $2n$
points on the unit circle (called the vertex frontier) paired by $n$ chords,
satisfying:

  1. (a)

the chords may cross, but do not intersect;

  2. (b)

the chord end points are partitioned into sets called pre-edges with
$0,1,2,\dots$, or $D$ elements; these points should lie on a single arc on the
frontier with no other end points on this arc;

  3. (c)

the pre-edges should form a connected collection that is, by merging all
points in each pre-edge and by removing the vertex frontier, the resulting
graph is connected.

The coordination (also called valence or degree) of a rank $D>0$ stranded
vertex is the number of its non-empty pre-edges. By convention: (C1) we
include a particular vertex made with one disc and assume that it is a
stranded vertex of any rank made with a unique closed chord and (C2) a point
is a rank 0 stranded vertex.

A rank $D$ stranded edge is a collection of segments called strands such that:

  1. (a′)

the strands are not intersecting (but can cross without intersecting);

  2. (b′)

the end points of the strands can be partitioned in two disjoint parts called
sets of end segments of the edge such that a strand cannot have its end points
in the same set of end segments;

  3. (c′)

the number of strands is $D$.

Some illustrations of stranded vertices and edges with rank $D=4,5$,
respectively, are provided in Fig. 1.

$v$$d$$e$

Figure 1: A rank 4 stranded vertex $v$ of coordination 6, connected pre-edges
highlighted with different colors; a trivial disc vertex $d$; a rank 5 edge
$e$ with non parallel strands.

######  Definition 2.2 (stranded and tensor graphs).

A rank $D$ stranded graph $\mathcal{G}$ is a graph
$\mathcal{G}(\mathcal{V},\mathcal{E})$ which admits:

  1. (i)

rank $D$ stranded vertices;

  2. (ii)

rank at most $D$ stranded edges;

  3. (iii)

one vertex and one edge intersect by one set of end segments of the edge which
should coincide with a pre-edge at the vertex frontier; All intersections of
vertices and edges are pairwise distinct.

A rank $D$ tensor graph $\mathcal{G}$ is a rank $D$ stranded graph such that:

  1. (i′)

the vertices of $\mathcal{G}$ have a fixed coordination $D+1$ and their pre-
edges have a fixed cardinal $D$. The merged point graph is $K_{D+1}$ (or
vertex graph);

  2. (ii′)

the edges of $\mathcal{G}$ are of rank $D$.

Consider a stranded graph. Collapsing its stranded vertices to points and
edges to simple lines, the resulting object is a graph. A stranded graph is
said to be connected if its corresponding collapsed graph is connected. From
this point, stranded vertices and edges are claimed connected.

Before proceeding further, let us present the notion of colorable (tensor)
graphs [9].

######  Definition 2.3 (colored and bipartite graphs).

A $(D+1)$ colored graph is a graph together with an assignment of a color
belonging to the set $\\{0,\dots,D\\}$ to each of its edges such that no two
adjacent edges share the same color.

A bipartite graph is a graph whose set $\mathcal{V}$ of vertices is split into
two disjoint sets, i.e., $\mathcal{V}=\mathcal{V}^{+}\cup\mathcal{V}^{-}$ with
$\mathcal{V}^{+}\cap\mathcal{V}^{-}=\varnothing$, such that each edge connects
a vertex $v^{+}\in\mathcal{V}^{+}$ and a vertex $v^{-}\in\mathcal{V}^{-}$.

######  Definition 2.4 (colored tensor graph [11, 13]).

A rank $D\geq 1$ colored tensor graph $\mathcal{G}$ is a graph such that:

  * •

$\mathcal{G}$ is $(D+1)$ colored and bipartite;

  * •

$\mathcal{G}$ is a rank $D$ tensor graph.

The collapsed graph coming from a colored tensor graph is merely obtained by
regarding the tensor graph as a simple bipartite colored graph and is called
_compact_ in the following.

Certainly, in such a colored graph, there is a lot more information that we
address now.

######  Definition 2.5 ($p$-bubbles [11]).

Let $\mathcal{G}$ be a rank $D$ colored tensor graph.

  * –

A 0-bubble is a vertex of $\mathcal{G}$.

  * –

A 1-bubble is an edge of $\mathcal{G}$.

  * –

For all $p\geq 2$, a $p$-bubble of $\mathcal{G}$ with colors
$i_{1}<i_{2}<\cdots<i_{p}$, $p\leq D$, and $i_{k}\in\\{0,\dots,D\\}$ is a
connected rank $p-1$ colored tensor graph the compact form of which is a
connected subgraph of the compact form of $\mathcal{G}$ made of edges of
colors $\\{i_{1},\dots,i_{p}\\}$.

The $p$-bubbles must not be confused with the notion of subgraphs used in the
definition of the polynomial invariants. They are basic components of
combinatorial graphs and generate an associated homology [11]. A 2-bubble is
also called a face.

We now introduce the notion of half-edge which allows to address the operation
called “cut” of an edge. This operation is different from the usual edge
deletion and it is used to define another category of subgraphs called
“c-subgraphs”.

######  Definition 2.6 (rank $D$ stranded half-edge).

A rank $D$ stranded half-edge is a collection of $D$ parallel segments called
strands satisfying the same properties of strands of rank $D$ edges but the
stranded half-edge is incident to a unique rank $D^{\prime}$ stranded vertex,
with $D^{\prime}\geq D$, by one of its set of end segments without forming a
loop.

A rank $D$ stranded half-edge has two sets of end segments: one touching a
vertex and another called free or external set of end segments, the elements
of which are called themselves free or external segments. The $D$ end-points
of all free segments are called external points of the rank $D$ stranded half-
edge.

A stranded graph having stranded half-edges is called half-edged stranded
graph and denoted $\mathcal{G}(\mathcal{V},\mathcal{E},\mathfrak{f}^{0})$ or
simply $\mathcal{G}_{\mathfrak{f}^{0}}$, with $\mathfrak{f}^{0}$ the set of
the half-edges.

######  Definition 2.7 (cut of an edge [14]).

Let $\mathcal{G}(\mathcal{V},\mathcal{E},\mathfrak{f}^{0})$ be a rank D
stranded graph and $e$ a rank $d$ edge of $\mathcal{G}_{\mathfrak{f}^{0}}$,
$1\leq d\leq D$. The cut graph $\mathcal{G}_{\mathfrak{f}^{0}}\vee e$ or the
graph obtained from $\mathcal{G}_{\mathfrak{f}^{0}}$ by cutting $e$ is
obtained by replacing the edge $e$ by two rank $d$ stranded half-edges at the
end vertices of $e$ and respecting the strand structure of $e$, see Fig. 2. If
$e$ is a loop, the two stranded half-edges are on the same vertex.

Figure 2: Cutting a rank 3 stranded edge.

Rank D stranded half-edges can be considered on colored tensor graphs by
respecting the following condition in addition to Definition 2.2: to each edge
and stranded half-edges, one assigns a color $i\in\\{0,1,\dots,D\\}$ such that
no two adjacent stranded half-edges share the same color. As well, the colored
edge can be cut in the same sense of Definition 2.7. The crucial issue is to
respect the color structure of the graph after the cut such that each of the
resulting stranded half-edges possesses the same color structure of the former
edge. Rank $D$ half-edged colored tensor graph are rank $D$ half-edged tensor
graph equipped with edge and stranded half-edge coloring.

Let us come back on the notion of c-subgraph using the operation of cutting of
an edge. We obtain a c-subgraph
$A(\mathcal{V}_{A},\mathcal{E}_{A},\mathfrak{f}^{0}_{A})$ of a rank $D$
stranded graph $\mathcal{G}(\mathcal{V},\mathcal{E},\mathfrak{f}^{0})$ by
cutting a subset of edges of $\mathcal{G}_{\mathfrak{f}^{0}}$. A spanning
c-subgraph $A$ of $\mathcal{G}_{\mathfrak{f}^{0}}$ is defined as a c-subgraph
$A(\mathcal{V}_{A},\mathcal{E}_{A},\mathfrak{f}^{0}_{A})$ of
$\mathcal{G}_{\mathfrak{f}^{0}}$ with all vertices and all additional half-
edges of $\mathcal{G}_{\mathfrak{f}^{0}}$. Hence
$\mathcal{E}_{A}\subseteq\mathcal{E}$ and $\mathcal{V}_{A}=\mathcal{V}$,
$\mathfrak{f}^{0}_{A}=\mathfrak{f}^{0}\cup\mathfrak{f}^{0;1}_{A}(\mathcal{E}_{A})$,
where $\mathfrak{f}^{0;1}_{A}(\mathcal{E}_{A})$ is the set of half-edges
obtained by cutting all edges in $\mathcal{E}_{A}^{\prime}$ (the set of edges
incident to the vertices of $A$ and not contained in $\mathcal{E}_{A}$) and
incident to vertices of $A$. We denote it
$A\Subset\mathcal{G}_{\mathfrak{f}^{0}}$.

This operation, which involves cutting an edge, has many implications on the
structure of the graph. For example it modifies the strand structure of this
graph. In particular, the cut operation or the presence of half-edges
immediately introduce another type of faces which pass through the external
points of the half-edges. Combinatorially, a discrepancy is introduced between
this type of faces called open faces and those which do not pass through the
external points of the half-edges are closed. The sets of closed and open
faces is denoted by $\mathcal{F}_{{\rm int}}$ and $\mathcal{F}_{{\rm ext}}$,
respectively. Hence, for a rank $D$ half-edged colored tensor graph, the set
$\mathcal{F}$ of faces is the disjoint union $\mathcal{F}_{{\rm
int}}\cup\mathcal{F}_{{\rm ext}}$. The notion of closed or open rank $D$ half-
edged colored tensor graph can be reported accordingly if $\mathcal{F}_{{\rm
ext}}=\varnothing$ or not, respectively. A bubble is open or external if it
contains open faces otherwise it is closed or internal. The sets of closed and
open bubbles for rank 3 tensor graph is denoted by $\mathcal{B}_{{\rm int}}$
and $\mathcal{B}_{{\rm ext}}$, respectively (see an illustration in Fig. 3).

1230

Figure 3: An open rank 3 half-edged colored tensor graph; an open face
highlighted in red; the bubbles ${\mathbf{b}}_{012}$, ${\mathbf{b}}_{013}$ and
${\mathbf{b}}_{123}$ are open bubbles and ${\mathbf{b}}_{023}$ is closed.

The presence of half-edges produces a new graph called “boundary graph” which
is obtained by setting a vertex to each half-edge [10].

######  Definition 2.8 (boundary tensor graph [10]).

The boundary graph
$\partial{\mathcal{G}}({\mathcal{V}}_{\partial},{\mathcal{E}}_{\partial})$ of
a rank $D$ half-edged colored tensor graph
$\mathcal{G}(\mathcal{V},\mathcal{E},\mathfrak{f}^{0})$ is a graph obtained by
inserting a vertex with degree $D$ at each additional stranded half-edge of
$\mathcal{G}_{\mathfrak{f}^{0}}$ and taking the external faces of
$\mathcal{G}_{\mathfrak{f}^{0}}$ as its edges. Thus,
$|{\mathcal{V}}_{\partial}|=|\mathfrak{f}^{0}|$ and
${\mathcal{E}}_{\partial}=\mathcal{F}_{{\rm ext}}$.

The boundary of a closed rank $D$ half-edged colored tensor graph is empty.

11230

Figure 4: Boundary graph (in dashed lines) of the graph of Fig. 3.

In order to introduce the notion of contraction of a stranded edge, some
particular edges called $p$-inner edge (an illustration is given in Fig. 5)
must be discussed. Assuming that $e$ is of rank $D$, consider the two pre-
edges $f_{1}$ and $f_{2}$ where $e$ is branched to its end vertex $v$ (a loop
situation) or vertices $v_{1,2}$ (a non loop case). It may happen that, after
branching $e$, $p$ closed faces are formed such that these closed faces are
completely contained in $e$ and $v$ or $v_{1,2}$. These closed faces are
called inner faces of the edge. An edge with $p$ inner faces is called
$p$-inner edge.

The notion of contraction introduced in this work is the notion of “soft”
contraction in [1].

OABCD$v_{1}$$v_{2}$$v_{1}$$v_{2}$$v_{3}$$v_{1}$$v_{2}$$v_{3}$$v_{4}$

Figure 5: $p$-inner loops: a 4-inner (O) and a 3-inner (A) loop with their
unique possible configuration; a 2-inner loop with possible two sectors
$v_{1}$ and $v_{2}$ (B) and a 1-inner loop with three possible sectors
$v_{1}$, $v_{2}$ and $v_{3}$ (C) and a 0-inner loop with four possible sectors
$v_{1},v_{2},v_{3}$ and $v_{4}$ (D).

######  Definition 2.9 (stranded edge contractions).

Let $\mathcal{G}(\mathcal{V},\mathcal{E},\mathfrak{f}^{0})$ be a rank $D$
half-edges stranded graph. Let $e$ be a rank $D$ edge with pre-edges $f_{1}$
and $f_{2}$ and consider their neighbor families $\\{f_{1;i}\\}$ and
$\\{f_{2;j}\\}$.

If $e$ is a rank $D$ $p$-inner edge but not a loop, the graph
$\mathcal{G}_{\mathfrak{f}^{0}}/e$ obtained by contracting $e$ is defined from
$\mathcal{G}_{\mathfrak{f}^{0}}$ by removing the $p$ inner faces generated by
$e$, replacing $e$ and its end vertices $v_{1,2}$ by $p$ disjoint disc
vertices and a new vertex $v^{\prime}$. The new vertex $v^{\prime}$ possesses
all pre-edges except for those of $e$ and all stranded half-edges as they
appear on $v_{1}$ and $v_{2}$, and chords obtained by connecting directly
$\\{f_{1;i}\\}$ and/or $\\{f_{2;j}\\}$ via the outer strands of $f_{1}$ and
$f_{2}$.

If $e$ is a rank $D$ $p$-inner loop, the graph
$\mathcal{G}_{\mathfrak{f}^{0}}/e$ obtained by contracting $e$ is defined from
$\mathcal{G}_{\mathfrak{f}^{0}}$ by removing the $p$ inner faces of $e$, by
replacing $e$ and its end vertex $v$ by $p$ disjoint disc vertices and one
vertex $v^{\prime}$ having all pre-edges of $v$ except for those of $e$, all
stranded half-edges and chords built in the similar way as previously done by
connecting the neighbor families of $f_{1}$ and/or $f_{2}$. If there is no
outer strand left after removing the $p$ inner faces of $e$ then the vertex
$v^{\prime}$ is empty. (Examples of rank 4 loop contraction is given in Fig.
6.)

OABCD$v_{1}$$v_{2}$$v_{1}$$v_{2}$$v_{3}$$v_{1}$$v_{2}$$v_{3}$$v_{4}$

Figure 6: $p$-inner loop contractions corresponding to O, A, B, C and D of
Fig. 5, respectively.

######  Proposition 2.10.

Let $\mathcal{G}(\mathcal{V},\mathcal{E},\mathfrak{f}^{0})$ be a rank $D$
half-edged stranded graph and $e$ be one of its edges. The graph
$\mathcal{G}_{\mathfrak{f}^{0}}/e$ obtained by contraction of $e$ admits a
rank $D$ half-edged stranded graph structure.

######  Definition 2.11 (equivalence class of half-edged stranded graph).

Let $D_{\mathcal{G}_{\mathfrak{f}^{0}}}$ be the subgraph in a rank $D$ half-
edges stranded graph $\mathcal{G}_{\mathfrak{f}^{0}}$ defined by all of its
trivial disc vertices and
$\mathcal{G}_{\mathfrak{f}^{0}}{\setminus}D_{\mathcal{G}_{\mathfrak{f}^{0}}}$
the rank $D$ half-edges stranded graph obtained after removing
$D_{\mathcal{G}_{\mathfrak{f}^{0}}}$ from $\mathcal{G}_{\mathfrak{f}^{0}}$.

Two rank $D$ half-edged stranded graphs
$\mathcal{G}_{1,\mathfrak{f}^{0}(\mathcal{G}_{1})}$ and
$\mathcal{G}_{2,\mathfrak{f}^{0}(\mathcal{G}_{2})}$ are “equivalent up to
trivial discs” if and only if
$\mathcal{G}_{1,\mathfrak{f}^{0}(\mathcal{G}_{1})}{\setminus}D_{\mathcal{G}_{1,\mathfrak{f}^{0}(\mathcal{G}_{1})}}={\mathcal{G}_{2,\mathfrak{f}^{0}(\mathcal{G}_{2})}}{\setminus}D_{\mathcal{G}_{2,\mathfrak{f}^{0}(\mathcal{G}_{2})}}$.
We note
$\mathcal{G}_{1,\mathfrak{f}^{0}(\mathcal{G}_{1})}\sim{\mathcal{G}_{2,\mathfrak{f}^{0}(\mathcal{G}_{2})}}$.

######  Lemma 2.12 (full contraction of a tensor graph).

Contracting an edge in a rank $D$ $($colored$)$ half-edged tensor graph does
not change its boundary. The contraction of all edges in arbitrary order of a
half-edged tensor graph $\mathcal{G}_{\mathfrak{f}^{0}}$ $($possibly with
colors$)$ yields a half-edged stranded graph
$\mathcal{G}^{0}_{\mathfrak{f}^{0}}$ determined by the boundary
$\partial(\mathcal{G}_{\mathfrak{f}^{0}})$ up to additional discs.

Based on this lemma we can now introduce the definition of a rank $D$
w-colored graph. An example is given in Fig. 7.

######  Definition 2.13 (rank $D$ w-colored graph).

A rank $D$ weakly-colored or w-colored graph is the equivalence class (up to
trivial discs) of a rank $D$ half-edged stranded graph obtained by successive
edge contractions of some rank $D$ half-edged colored tensor graph.

112301120

Figure 7: Contraction of an edge in a rank 3 half-edged colored tensor graph.

######  Proposition 2.14.

Let $\mathfrak{G}$ be a rank $D$ w-colored graph,
$\mathcal{G}_{\mathfrak{f}^{0}}$ be a representative of $\mathfrak{G}$ and $e$
one of its edges.

$\mathfrak{G}\vee e$ denotes the equivalence class of
$\mathcal{G}_{\mathfrak{f}^{0}}\vee e$ called the cut graph $\mathfrak{G}$
along $e$ and is a rank $D$ w-colored graph.

$\mathfrak{G}/e$ denotes the equivalence class of
$\mathcal{G}_{\mathfrak{f}^{0}}/e$, called the contraction of $\mathfrak{G}$
along $e$ and is a rank $D$ w-colored graph.

Let us discuss the notion of trivial loop for $4D$ w-colored stranded graphs.
A loop $e$ is called trivial if it is a 4-inner or 3-inner or if it is a
2-inner, 1-inner or 0-inner loop with all separate sectors such that there is
no edge between sectors $v_{i}$ as illustrated in Fig. 5.

For a 4-inner loop, the contraction gives four trivial discs, see Fig. 6O. For
a 3-inner loop, the contraction yields to Fig. 6A. For a trivial 2-inner loop
the contraction is still straightforward and yields Fig. 6B. Contracting a
trivial 2-inner loop, the vertex gets disconnected in two non trivial
vertices. For a 1-inner loop contraction (see Fig. 6C), one gets one extra
disc and has two possible configurations: either the vertex remains connected
or it gets disconnected with three (possibly non trivial) vertices in both
situations. If the 1-inner loop is trivial, it is immediate that the vertex
gets disconnected in three non trivial vertices. For a 0-inner loop
contraction (see Fig. 6D), we have no additional disc but four types of
configurations with up to four disconnected (and possibly non trivial)
vertices. The contraction of a trivial 0-inner loop yields directly four
disconnected and non trivial vertices.

The notion of trivial loop for $3D$ w-colored is direct from the above
discussion: a rank 3 loop $e$ is called trivial if it is a 3-inner or 2-inner
or if it is a 1-inner or 0-inner with all separate sectors such that there is
no edge between sectors $v_{i}$.

Equivalence class of stranded graphs. We now define the equivalence class of
stranded graphs by performing a sequence of operations corresponding to the
following:

  1. –

any homeomorphism of chords and strands keeping fixed their end points (we
therefore use a “minimal” graphical representation for stranded vertices and
edges which is the one defined by chords and strands using simple arcs between
the pre-edge points);

  2. –

any change of the crossing states between chords and also between strands (see
Fig. 8);

Figure 8: Examples of equivalent crossing states of chords (in stranded
vertices) and strands (in stranded edge).

  3. –

any permutation of the pre-edge points within a pre-edge (see Fig. 9: $v_{1}$
is obtained from $v_{0}$ after permuting the points 1 and 2 in the pre-edge
$\\{1,2,3\\}$ and renaming $e_{1}\to\tilde{e}_{1}$).

  4. –

any move of the pre-edges on the frontier vertex (see Fig. 9: $v_{2}$ is
obtained from $v_{0}$ after moving a pre-edge $\\{7,8\\}$ on the vertex
frontier and also its edge $e_{3}$ remains incident to that pre-edge at the
same pre-edge points).

$v_{0}$$e_{1}$$e_{2}$$e_{3}$$e_{4}$$v_{1}$$\tilde{e}_{1}$$e_{2}$$e_{3}$$e_{4}$$v_{2}$$e_{1}$$e_{2}$$e_{3}$$e_{4}$

Figure 9: Three vertices $v_{0}$, $v_{1}$ and $v_{2}$ and their incident
stranded edges corresponding to equivalent configurations of stranded graphs,
if the rest of each graph is kept fixed.

Consider a representative $\mathcal{G}_{\mathfrak{f}^{0}}$ of a rank 3
w-colored graph $\mathfrak{G}(\mathcal{V},\mathcal{E},\mathfrak{f}^{0})$. We
denote by $V(\mathcal{G}_{\mathfrak{f}^{0}})$,
$E(\mathcal{G}_{\mathfrak{f}^{0}})$, $k(\mathcal{G}_{\mathfrak{f}^{0}})$,
$f(\mathcal{G}_{\mathfrak{f}^{0}})$,
$C_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}})$,
$E_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}})$ and
$F_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}})$, the number of vertices, edges,
connected components, half-edges, connected components of the boundary graphs,
edges of the boundary graph and faces of the boundary graph of
$\mathcal{G}_{\mathfrak{f}^{0}}$.
$\operatorname{r}(\mathcal{G}_{\mathfrak{f}^{0}})=V(\mathcal{G}_{\mathfrak{f}^{0}})-k(\mathcal{G}_{\mathfrak{f}^{0}})$,
$n(\mathcal{G}_{\mathfrak{f}^{0}})=E(\mathcal{G}_{\mathfrak{f}^{0}})-\operatorname{r}(\mathcal{G}_{\mathfrak{f}^{0}})$
the rank and nullity of $\mathcal{G}_{\mathfrak{f}^{0}}$ and $B_{{\rm
int}}(\mathcal{G}_{\mathfrak{f}^{0}})$, $B_{{\rm
ext}}(\mathcal{G}_{\mathfrak{f}^{0}})$, the numbers of internal and external
bubbles in $\mathcal{G}_{\mathfrak{f}^{0}}$.

We now address the invariant on rank 3 w-colored graphs based on the sum of
the genera of bubbles.

######  Proposition 2.15 ([1]).

Let $\mathcal{G}_{\mathfrak{f}^{0}}$ be any representative of $\mathfrak{G}$ a
rank $3$ w-colored graph. Then

$\displaystyle\gamma_{3}(\mathcal{G}_{\mathfrak{f}^{0}})=3(V(\mathcal{G}_{\mathfrak{f}^{0}})-E(\mathcal{G}_{\mathfrak{f}^{0}}))+2[F_{{\rm
int}}(\mathcal{G}_{\mathfrak{f}^{0}})-B_{{\rm
int}}(\mathcal{G}_{\mathfrak{f}^{0}})-B_{{\rm
ext}}(\mathcal{G}_{\mathfrak{f}^{0}})]\leq 0.$

######  Definition 2.16 (topological invariant for rank 3 w-colored graph).

Let $\mathfrak{G}(\mathcal{V},\mathcal{E},\mathfrak{f}^{0})$ be a rank 3
w-colored graph. The generalized topological invariant associated with
$\mathfrak{G}$ is given by the following function associated with any of its
representatives $\mathcal{G}_{\mathfrak{f}^{0}}$ (using the above notations)

$\displaystyle\mathfrak{T}_{\mathfrak{G}}(x,y,z,s,w,q,t)=\mathfrak{T}_{\mathcal{G}_{\mathfrak{f}^{0}}}(x,y,z,s,w,q,t)$
$\displaystyle\qquad{}=\sum_{A\Subset\mathcal{G}_{\mathfrak{f}^{0}}}(x-1)^{\operatorname{r}(\mathcal{G}_{\mathfrak{f}^{0}})-\operatorname{r}(A)}(y-1)^{n(A)}z^{5k(A)-\gamma_{3}(A)}s^{C_{\partial}(A)}w^{F_{\partial}(A)}q^{E_{\partial}(A)}t^{f(A)},$
(2.1)

with $\gamma_{3}(A)=3(V(A)-E(A))+2[F_{{\rm int}}(A)-B_{{\rm int}}(A)-B_{{\rm
ext}}(A)]$.

It is important to show that considering different representatives
$\mathcal{G}_{\mathfrak{f}^{0}(\mathcal{G})}$ and
$\mathcal{G}^{\prime}_{\mathfrak{f}^{0}(\mathcal{G}^{\prime})}$ of
$\mathfrak{G}$, the definition does not depend of the choice of the
representative. In fact, there exists a one-to-one map between spanning
c-subgraphs of $\mathcal{G}_{\mathfrak{f}^{0}(\mathcal{G})}$ and those of
$\mathcal{G}^{\prime}_{\mathfrak{f}^{0}(\mathcal{G}^{\prime})}$. We can then
map each $A\Subset\mathcal{G}_{\mathfrak{f}^{0}(\mathcal{G})}$ onto
$A^{\prime}\Subset\mathcal{G}^{\prime}_{\mathfrak{f}^{0}(\mathcal{G}^{\prime})}$
such that
$A^{\prime}=(A{\setminus}D_{\mathcal{G}_{\mathfrak{f}^{0}(\mathcal{G})}})\cup
D_{\mathcal{G}^{\prime}_{\mathfrak{f}^{0}(\mathcal{G}^{\prime})}}$. We now
verify that $\operatorname{r}(\mathcal{G}_{\mathfrak{f}^{0}(\mathcal{G})})$,
$\operatorname{r}(A)$, $n(A)$ and $5k(A)-(3V+2F_{\rm int}(A))$ are independent
of the representative. The exponents $B_{\rm int}(A)$, $B_{\rm ext}(A)$,
$C_{\partial}(A)$, $f(A)$, $E_{\partial}(A)$ and $F_{\partial}(A)$ only depend
on
$A{\setminus}D_{\mathcal{G}_{\mathfrak{f}^{0}(\mathcal{G})}}=A^{\prime}{\setminus}D_{\mathcal{G}^{\prime}_{\mathfrak{f}^{0}(\mathcal{G}^{\prime})}}$
therefore are not dependent on the representative.

######  Proposition 2.17 (polynomial invariant).

$\mathfrak{T}_{\mathfrak{G}}=\mathfrak{T}_{\mathcal{G}_{\mathfrak{f}^{0}}}$ is
a polynomial.

The main properties satisfied by the above polynomial are given by the next
statement.

######  Theorem 2.18 (contraction/cut rule for rank 3 w-colored graphs).

Let $\mathfrak{G}$ be a rank $3$ w-colored graph. Then, for a regular edge $e$
of any of the representative $\mathcal{G}_{\mathfrak{f}^{0}}$ of
$\mathfrak{G}$, we have

$\displaystyle\mathfrak{T}_{\mathcal{G}_{\mathfrak{f}^{0}}}=\mathfrak{T}_{\mathcal{G}_{\mathfrak{f}^{0}}\vee
e}+\mathfrak{T}_{\mathcal{G}_{\mathfrak{f}^{0}}/e}.$

For a bridge $e$, we have

$\displaystyle\mathfrak{T}_{\mathcal{G}_{\mathfrak{f}^{0}}\vee
e}=z^{8}s(wq)^{3}t^{2}\mathfrak{T}_{\mathcal{G}_{\mathfrak{f}^{0}}/e}\qquad\text{and}\qquad\mathfrak{T}_{\mathcal{G}_{\mathfrak{f}^{0}}}=\big{[}(x-1)z^{8}s(wq)^{3}t^{2}+1\big{]}\mathfrak{T}_{\mathcal{G}_{\mathfrak{f}^{0}}/e}.$

For a trivial p-inner loop $e$, $p=0,1,2$, we have

$\displaystyle\mathfrak{T}_{\mathcal{G}_{\mathfrak{f}^{0}}}=\mathfrak{T}_{\mathcal{G}_{\mathfrak{f}^{0}}\vee
e}+(y-1)z^{4p-7}\mathfrak{T}_{\mathcal{G}_{\mathfrak{f}^{0}}/e}.$

The proof of this statement uses bijections between c-subgraphs and the
variations of the number of $p$-bubbles under contraction/cut rules.

There are several possible reductions of the above polynomial satisfying nice
properties. Some of them are determined by a change of variables. We have

$\displaystyle\mathfrak{T}_{\mathcal{G}_{\mathfrak{f}^{0}}}\big{(}x,y,z,z^{-2},w,q,t\big{)}=\mathfrak{T}^{\prime}_{\mathcal{G}_{\mathfrak{f}^{0}}}(x,y,z,w,q,t),$
$\displaystyle\mathfrak{T}_{\mathcal{G}_{\mathfrak{f}^{0}}}\big{(}x,y,z,z^{-2}s^{2},s^{-1},s,s^{-1}\big{)}=\mathfrak{T}^{\prime\prime}_{\mathcal{G}_{\mathfrak{f}^{0}}}(x,y,z,s),$
$\displaystyle\mathfrak{T}_{\mathcal{G}_{\mathfrak{f}^{0}}}\big{(}x,y,z,z^{2}z^{-2},z^{-1},z,z^{-1}\big{)}=\mathfrak{T}^{\prime\prime\prime}_{\mathcal{G}_{\mathfrak{f}^{0}}}(x,y,z).$

$\mathfrak{T}^{\prime}_{\mathcal{G}_{\mathfrak{f}^{0}}}$,
$\mathfrak{T}^{\prime\prime}_{\mathcal{G}_{\mathfrak{f}^{0}}}$ and
$\mathfrak{T}^{\prime\prime\prime}_{\mathcal{G}_{\mathfrak{f}^{0}}}$ satisfy
also the contraction/cut rule. Furthermore
$\mathfrak{T}_{\mathcal{G}_{\mathfrak{f}^{0}}}$ maps to Tutte polynomial by
putting variables $z=w=q=t=1$. The mapping of
$\mathfrak{T}_{\mathcal{G}_{\mathfrak{f}^{0}}}$ to BR polynomial is also
possible but we must pay attention to the exponent of the variable $z$ which
is modified by the number of additional discs. We will come back on this point
in the following.

######  Definition 2.19 (multivariate form).

The multivariate form associated with (2.1) is defined by

$\displaystyle\widetilde{\mathfrak{T}}_{\mathfrak{G}}(x,\\{\beta_{e}\\},\\{z_{i}\\}_{i=1,2,3},s,w,q,t)=\widetilde{\mathfrak{T}}_{\mathcal{G}_{\mathfrak{f}^{0}}}(x,\\{\beta_{e}\\},\\{z_{i}\\}_{i=1,2,3},s,w,q,t)$
$\displaystyle\qquad{}=\sum_{A\Subset\mathcal{G}_{\mathfrak{f}^{0}}}x^{\operatorname{r}(A)}\left(\prod_{e\in
A}\beta_{e}\right)z_{1}^{F_{{\rm int}}(A)}z_{2}^{B_{{\rm
int}}(A)}z_{3}^{B_{{\rm
ext}}(A)}s^{C_{\partial}(A)}w^{F_{\partial}(A)}q^{E_{\partial}(A)}t^{f(A)},$

for $\\{\beta_{e}\\}_{e\in\mathcal{E}}$ labeling the edges of the graph
$\mathcal{G}_{\mathfrak{f}^{0}}$.

For all non-loop edge $e$, $\mathfrak{T}$ obeys the rule
$\widetilde{\mathfrak{T}}_{\mathfrak{G}}=\widetilde{\mathfrak{T}}_{\mathfrak{G}\vee
e}+x\beta_{e}\widetilde{\mathfrak{T}}_{\mathfrak{G}/e}$, which can be shown
using standard techniques.

##  3 The polynomial invariant for $\boldsymbol{4D}$ w-colored graphs

Rank 4 w-colored graph structures are richer than the above case. This is
completely expected since rank 4 w-colored graphs represent topologically $4D$
simplicial manifolds. For the present study, we observe that increasing the
rank of the graph implies that the number of $p$-bubbles increases. As a
consequence, we have a lot more freedom to define an invariant. In this work,
we have not fully harnessed the number of possibilities of defining
invariants. This will be addressed in a forthcoming work.

Let us focus on the importance of the bubble combinatorics in the resolution
of the contraction/cut invariant problem. For the determination of the
invariant in Proposition 2.15, each rank 3 w-colored graph is looked as
collection of ribbon graphs. The invariant comes from the summation on the
genera of all these graphs. The case of the rank 4 w-colored stranded graphs
leads to several options. A rank 4 w-colored stranded graph may be looked as a
collection of $3$-bubbles which are ribbon graphs, a collection of $4$-bubbles
which are themselves rank 3 graphs or a mixture of both (see Fig. 10). A sum
over invariants of all 4-bubbles is introduced in Appendix A for an interested
reader. In general, we may also perform a summation of the invariants of all
$3$-bubbles, the invariant of all $4$-bubbles or may mix both to find a new
invariant.

$\mathcal{G}_{1,\mathfrak{f}^{0}(\mathcal{G}_{1})}$${\mathbf{b}}_{1}$$0$$\bar{0}$$0$$\bar{0}$${\mathbf{b}}_{2}$$0$$\bar{0}$

Figure 10: A 3-bubble ${\mathbf{b}}_{1}$ and a 4-bubble ${\mathbf{b}}_{2}$ of
$\mathcal{G}_{1,\mathfrak{f}^{0}(\mathcal{G}_{1})}$.

In the present work, we mainly discuss the summation of the invariants of all
$3$-bubbles. This is to make contact with very recent results [10, 15, 16].

Some notations deserve to be clarified. Consider a representative
$\mathcal{G}_{\mathfrak{f}^{0}}$ of any rank 4 w-colored graph: a $d$-bubble
(closed or open) in $\mathcal{G}_{\mathfrak{f}^{0}}$ is denoted by
${\mathbf{b}}^{d}$, the set of $d$-bubbles is $\mathcal{B}^{d}$, and its
cardinal $B^{d}$. $\mathcal{V}_{{\mathbf{b}}^{d}}$,
$\mathcal{E}_{{\mathbf{b}}^{d}}$, $\mathcal{F}_{{\rm int};{\mathbf{b}}^{d}}$
and $\mathcal{B}^{p}_{{\mathbf{b}}^{d}}$ are respectively the set of vertices,
edges, internal faces and $p$-bubbles ($p\leq d$) of ${\mathbf{b}}^{d}$ of
cardinal $V_{{\mathbf{b}}^{d}}$, $E_{{\mathbf{b}}^{d}}$, $F_{{\rm
int};{\mathbf{b}}^{d}}$ and $B^{p}_{{\mathbf{b}}^{d}}$ respectively.

######  Lemma 3.1 (rank 4 trivial loop contraction).

Let $\mathfrak{G}$ a w-colored graph and $\mathcal{G}_{\mathfrak{f}^{0}}$ any
of its representative with boundary $\partial\mathcal{G}_{\mathfrak{f}^{0}}$,
$e$ be a trivial loop of $\mathcal{G}_{\mathfrak{f}^{0}}$, and
$\mathcal{G}^{\prime}_{\mathfrak{f}^{0}}=\mathcal{G}_{\mathfrak{f}^{0}}/e$ the
result of the contraction of $\mathcal{G}_{\mathfrak{f}^{0}}$ by $e$ with
boundary denoted by $\partial\mathcal{G}^{\prime}_{\mathfrak{f}^{0}}$. Let $k$
denote the number of connected components of $\mathcal{G}_{\mathfrak{f}^{0}}$,
$V$ its number of vertices, $E$ its number of edges, $F_{{\rm int}}$ its
number of faces, $B^{i}_{\rm int}$ its number of closed $i$-bubbles and
$B^{i}_{\rm ext}$ its number of open $i$-bubbles $(i=3,4)$, $C_{\partial}$ the
number of connected component of $\partial\mathcal{G}_{\mathfrak{f}^{0}}$,
$f=V_{\partial}$ its number of stranded half-edges, $E_{\partial}=F_{{\rm
ext}}$ the number of edges and $F_{\partial}$ the number of faces of
$\partial\mathcal{G}_{\mathfrak{f}^{0}}$, and let $k^{\prime}$, $V^{\prime}$,
$E^{\prime}$, $F^{\prime}_{{\rm int}}$, $C^{\prime}_{\partial}$, $B^{\prime
i}_{{\rm int}}$, $B^{\prime i}_{\rm ext}(i=3,4)$, $C^{\prime}_{\partial}$,
$f^{\prime}$, $E^{\prime}_{\partial}$, and $F^{\prime}_{\partial}$ denote the
similar numbers for $\mathcal{G}^{\prime}_{\mathfrak{f}^{0}}$ and its boundary
$\partial\mathcal{G}^{\prime}_{\mathfrak{f}^{0}}$.

If $e$ is a $4$-inner loop, then

$\displaystyle k^{\prime}=k+3,\qquad V^{\prime}=V+3,\qquad
E^{\prime}=E-1,\qquad F^{\prime}_{{\rm int}}=F_{{\rm int}},$ $\displaystyle
C^{\prime}_{\partial}=C_{\partial},\qquad f^{\prime}=f,\qquad
E^{\prime}_{\partial}=E_{\partial},\qquad F^{\prime}_{\partial}=F_{\partial},$
$\displaystyle B^{\prime i}_{\rm int}=B^{i}_{{\rm
int}}-\complement_{4}^{i-1},\qquad B^{\prime i}_{\rm ext}=B^{i}_{\rm
ext},\qquad i=3,4.$ (3.1)

If $e$ is a $3$-inner loop, then

$\displaystyle k^{\prime}=k+3,\qquad V^{\prime}=V+3,\qquad
E^{\prime}=E-1,\qquad F^{\prime}_{{\rm int}}=F_{{\rm int}},$ $\displaystyle
C^{\prime}_{\partial}=C_{\partial},\qquad f^{\prime}=f,\qquad
E^{\prime}_{\partial}=E_{\partial},\qquad F^{\prime}_{\partial}=F_{\partial},$
$\displaystyle B^{\prime i}_{\rm int}=B^{i}_{{\rm
int}}-\complement_{3}^{i-1},\qquad B^{\prime i}_{\rm ext}=B^{i}_{\rm
ext},\qquad i=3,4.$ (3.2)

If $e$ is a trivial $p$-inner loop such that $p=0,1,2$, then

$\displaystyle k^{\prime}=k+3,\qquad V^{\prime}=V+3,\qquad
E^{\prime}=E-1,\qquad F^{\prime}_{{\rm int}}=F_{{\rm int}},$ $\displaystyle
C^{\prime}_{\partial}=C_{\partial},\qquad f^{\prime}=f,\qquad
E^{\prime}_{\partial}=E_{\partial},\qquad F^{\prime}_{\partial}=F_{\partial},$
$\displaystyle B^{\prime 3}_{\rm int}+B^{\prime 3}_{\rm ext}=B^{3}_{{\rm
int}}+B^{3}_{\rm ext}+\beta_{p},\qquad B^{\prime 4}_{\rm int}+B^{\prime
4}_{\rm ext}=B^{4}_{{\rm int}}+B^{4}_{\rm ext}+\beta^{\prime}_{p},$ (3.3)

where $\beta_{p}=6-3p$, $\beta^{\prime}_{p}=8-3p$ and
$\complement_{n}^{p}=\frac{n!}{p!(n-p)!}$ the ordinary binomial coefficient.

###### Proof.

The case of a 4-inner loop is that of a particular closed graph constituted by
a single vertex with a unique loop. The contraction destroys the vertex, the
six closed 3-bubbles, the four closed 4-bubbles and produces 4 discs. The
result is immediate.

For $p$-inner loops, $p\leq 3$, there are other stranded half-edges or edges
on the same end vertex. The two first lines of (3.2)–(3.3) are direct using
the definition of the contraction that preserves (open and closed) strands. We
now turn on the number of bubbles of the graph.

Let us recall that we obtain the 3-bubbles by removing simultaneously from the
initial graph two colors. The 4-bubbles are obtained by removing all strands
with the pair of colors. In all the following discussion, removing a strand
means removing all others having the same color.

Let us focus on the 3-inner loop case. We have 3 strands which are closed and
one outer strand. By contracting this edge, we loose the 3 3-bubbles passing
through the inner strands. The 3-bubbles which use the outer strand are still
present after the contraction and just loose some internal faces. We also
loose the only one closed 4-bubble passing through these inner strands. All
4-bubbles using the outer strand are still present after the contraction. This
ends the proof of (3.2).

In the case of the 2-inner loop, we have two outer strands and two strands
which are immediately closed (the inner ones). Contracting the edge, we loose
the closed 3-bubble formed by the two inner strands obtained by removing the
two outer strands. Any other 3-bubble is obtained either by removing one of
the outer strands and one of inner or by removing the two inner strands. The
number of 3-bubbles (closed or opened) obtained in
$\mathcal{G}_{\mathfrak{f}^{0}}$ or $\mathcal{G}^{\prime}_{\mathfrak{f}^{0}}$
are the same performing the first operation. If we remove the two inner
strands, the 3-bubbles using the outer strands in
$\mathcal{G}_{\mathfrak{f}^{0}}$ get split in two parts in
$\mathcal{G}^{\prime}_{\mathfrak{f}^{0}}$. We then obtain one more bubble in
$\mathcal{G}^{\prime}_{\mathfrak{f}^{0}}$. This compensates the one we have
lost previously. Hence $B^{\prime 3}_{\rm int}+B^{\prime 3}_{\rm
ext}=B^{3}_{{\rm int}}+B^{3}_{\rm ext}$.

The number of 4-bubbles obtained by removing one of the outer strands is
preserved in the contracted graph. If we remove one of the inner strands, we
obtain one extra 4-bubble in the contracted graph. Then $B^{\prime 4}_{\rm
int}+B^{\prime 4}_{\rm ext}=B^{4}_{{\rm int}}+B^{4}_{\rm ext}+2$.

For the 1-inner loop, the procedure is similar. We have three outer strands
and one inner. Removing the inner and one of the outer strands, we obtain one
more 3-bubble in the contracted graph but if we remove two of the outers, the
number of 3-bubbles in the contracted graph is the same. We have $B^{\prime
3}_{\rm int}+B^{\prime 3}_{\rm ext}=B^{3}_{{\rm int}}+B^{3}_{\rm ext}+3$.

We now concentrate on the $4$-bubbles case. If we remove the inner strand, we
obtain two more $4$-bubbles in the contracted graph. Otherwise, if we remove
one of the outer strands, we obtain one more $4$-bubbles in the contracted
graph. Hence $B^{\prime 4}_{\rm int}+B^{\prime 4}_{\rm ext}=B^{4}_{{\rm
int}}+B^{4}_{\rm ext}+5$.

Case of the 0-inner loop. By implementing the above techniques we can prove
also $B^{\prime 3}_{\rm int}+B^{\prime 3}_{\rm ext}=B^{3}_{{\rm
int}}+B^{3}_{\rm ext}+6$ and $B^{\prime 4}_{\rm int}+B^{\prime 4}_{\rm
ext}=B^{4}_{{\rm int}}+B^{4}_{\rm ext}+8$. ∎

######  Lemma 3.2 (cut/contraction of special edges).

Let $\mathcal{G}_{\mathfrak{f}^{0}}$ be a representative of $\mathfrak{G}$ a
rank $4$ w-colored graph and $e$ an edge in $\mathcal{G}_{\mathfrak{f}^{0}}$.

If $e$ is a bridge, we have

$\displaystyle k(\mathcal{G}_{\mathfrak{f}^{0}}\vee
e)=k(\mathcal{G}_{\mathfrak{f}^{0}}/e)+1,\qquad
V(\mathcal{G}_{\mathfrak{f}^{0}}\vee
e)=V(\mathcal{G}_{\mathfrak{f}^{0}}/e)+1,$ $\displaystyle
E(\mathcal{G}_{\mathfrak{f}^{0}}\vee
e)=E(\mathcal{G}_{\mathfrak{f}^{0}}/e),\qquad
f(\mathcal{G}_{\mathfrak{f}^{0}}\vee
e)=f(\mathcal{G}_{\mathfrak{f}^{0}}/e)+2,$ (3.4) $\displaystyle F_{{\rm
int}}(\mathcal{G}_{\mathfrak{f}^{0}}\vee e)=F_{{\rm
int}}(\mathcal{G}_{\mathfrak{f}^{0}}/e),\qquad B^{3}_{{\rm
int}}(\mathcal{G}_{\mathfrak{f}^{0}}\vee e)=B^{3}_{{\rm
int}}(\mathcal{G}_{\mathfrak{f}^{0}}/e),$ $\displaystyle B^{4}_{{\rm
int}}(\mathcal{G}_{\mathfrak{f}^{0}}\vee e)=B^{4}_{{\rm
int}}(\mathcal{G}_{\mathfrak{f}^{0}}/e),$ (3.5) $\displaystyle
C_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}}\vee
e)=C_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}}/e)+1,\qquad
E_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}}\vee
e)=E_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}}/e)+4,$ $\displaystyle
F_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}}\vee
e)=F_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}}/e)+6,$ (3.6) $\displaystyle
B^{3}_{{\rm ext}}(\mathcal{G}_{\mathfrak{f}^{0}}\vee e)=B^{3}_{{\rm
ext}}(\mathcal{G}_{\mathfrak{f}^{0}}/e)+6,\qquad B^{4}_{{\rm
ext}}(\mathcal{G}_{\mathfrak{f}^{0}}\vee e)=B^{4}_{{\rm
ext}}(\mathcal{G}_{\mathfrak{f}^{0}}/e)+4.$ (3.7)

If $e$ is a trivial $p$-inner loop, $p=0,1,2,3$, we have

$\displaystyle k(\mathcal{G}_{\mathfrak{f}^{0}}\vee
e)=k(\mathcal{G}_{\mathfrak{f}^{0}}/e)-3,\qquad
V(\mathcal{G}_{\mathfrak{f}^{0}}\vee
e)=V(\mathcal{G}_{\mathfrak{f}^{0}}/e)-3,\qquad
E(\mathcal{G}_{\mathfrak{f}^{0}}\vee e)=E(\mathcal{G}_{\mathfrak{f}^{0}}/e),$
$\displaystyle f(\mathcal{G}_{\mathfrak{f}^{0}}\vee
e)=f(\mathcal{G}_{\mathfrak{f}^{0}}/e)+2,$ (3.8) $\displaystyle F_{{\rm
int}}(\mathcal{G}_{\mathfrak{f}^{0}}\vee
e)+C_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}}\vee e)=F_{{\rm
int}}(\mathcal{G}_{\mathfrak{f}^{0}}/e)+C_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}}/e)-3,$
$\displaystyle E_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}}\vee
e)=E_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}}/e)+4,$ (3.9) $\displaystyle
B^{3}_{{\rm int}}(\mathcal{G}_{\mathfrak{f}^{0}}\vee e)+B^{3}_{{\rm
ext}}(\mathcal{G}_{\mathfrak{f}^{0}}\vee e)=B^{3}_{{\rm
int}}(\mathcal{G}_{\mathfrak{f}^{0}}/e)+B^{3}_{{\rm
ext}}(\mathcal{G}_{\mathfrak{f}^{0}}/e)-(6-3p),$ (3.10) $\displaystyle
B^{4}_{{\rm int}}(\mathcal{G}_{\mathfrak{f}^{0}}\vee e)+B^{4}_{{\rm
ext}}(\mathcal{G}_{\mathfrak{f}^{0}}\vee e)=B^{4}_{{\rm
int}}(\mathcal{G}_{\mathfrak{f}^{0}}/e)+B^{4}_{{\rm
ext}}(\mathcal{G}_{\mathfrak{f}^{0}}/e)-(8-3p).$ (3.11)

###### Proof.

Let us begin by the case of the bridge. In (3.4), the relations are directly
achieved. Now, we turn on (3.5). From [1, Lemma 7], we claim that the faces
passing through $e$ are open and belong to the same connected component of the
boundary graph. Then all closed faces on each side of the bridge are preserved
after cutting $e$. The same are still preserved after edge contraction and
therefore $F_{{\rm int}}(\mathcal{G}_{\mathfrak{f}^{0}}\vee e)=F_{{\rm
int}}(\mathcal{G}_{\mathfrak{f}^{0}}/e)$, $B^{3}_{{\rm
int}}(\mathcal{G}_{\mathfrak{f}^{0}}\vee e)=B^{3}_{{\rm
int}}(\mathcal{G}_{\mathfrak{f}^{0}}/e)$ and $B^{4}_{{\rm
int}}(\mathcal{G}_{\mathfrak{f}^{0}}\vee e)=B^{4}_{{\rm
int}}(\mathcal{G}_{\mathfrak{f}^{0}}/e)$. Let us focus on (3.6). Since the
faces passing through $e$ belong to the same connected component, cutting $e$,
this unique component yields two boundary components. We obtain
$C_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}}\vee
e)=C_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}}/e)+1$,
$E_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}}\vee
e)=E_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}}/e)+4$ (the cut of $e$ divides
each external face into two different open strands) and
$F_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}}\vee
e)=F_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}}/e)+6$ since
$C_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}}/e)=C_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}})$,
$E_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}}/e)=E_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}})$
and
$F_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}}/e)=F_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}})$
which are direct from Lemma 2.12. For the number of external bubbles, there
are six 3-bubbles and four 4-bubbles in $\mathcal{G}_{\mathfrak{f}^{0}}$
passing through the bridge. These bubbles are present in
$\mathcal{G}_{\mathfrak{f}^{0}}/e$ and cutting the bridge each of these
bubbles splits in two. This yields (3.7).

We concentrate now on a trivial $p$-inner loop $e$. The relations (3.8) is
directly found. We focus on the rest of the equations. Consider the faces
$f_{i}$ in $e$ made with outer strands. For $p=0,1,2,3$, we have $f_{i}$,
$1\leq i\leq 4-p$. These faces can be open or closed. We do a case by case
study according to the number of open or closed faces among the $f_{i}$’s.

Suppose that $4-p$ of $f_{i}$’s are closed. Cutting $e$ entails

$\displaystyle F_{{\rm int}}(\mathcal{G}_{\mathfrak{f}^{0}}\vee e)=F_{{\rm
int}}(\mathcal{G}_{\mathfrak{f}^{0}})-4,\qquad\\!C_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}}\vee
e)=C_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}})+1,\qquad\\!E_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}}\vee
e)=E_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}})+4,$ $\displaystyle
B^{3}(\mathcal{G}_{\mathfrak{f}^{0}}\vee
e)=B^{3}(\mathcal{G}_{\mathfrak{f}^{0}}),\qquad
B^{4}(\mathcal{G}_{\mathfrak{f}^{0}}\vee
e)=B^{4}(\mathcal{G}_{\mathfrak{f}^{0}}),\qquad
F_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}}\vee
e)=F_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}})+6.$

Remark that, in this situation, only the variation of the total number of
bubbles can be known.

Suppose that $4-p-1$ of the $f_{i}$’s are closed and one is open. Cutting $e$
implies

$\displaystyle F_{{\rm int}}(\mathcal{G}_{\mathfrak{f}^{0}}\vee e)=F_{{\rm
int}}(\mathcal{G}_{\mathfrak{f}^{0}})-3,\qquad
C_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}}\vee
e)=C_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}}),\qquad
E_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}}\vee
e)=E_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}})+4,$ $\displaystyle
B^{3}(\mathcal{G}_{\mathfrak{f}^{0}}\vee
e)=B^{3}(\mathcal{G}_{\mathfrak{f}^{0}}),\qquad
B^{4}(\mathcal{G}_{\mathfrak{f}^{0}}\vee
e)=B^{4}(\mathcal{G}_{\mathfrak{f}^{0}}),\qquad
F_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}}\vee
e)=F_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}})+3.$

Suppose that $4-p-2$ of the $f_{i}$’s are closed and two are open. Cutting $e$
gives

$\displaystyle F_{{\rm int}}(\mathcal{G}_{\mathfrak{f}^{0}}\vee e)=F_{{\rm
int}}(\mathcal{G}_{\mathfrak{f}^{0}})-2,\qquad\\!C_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}}\vee
e)=C_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}})-1,\qquad\\!E_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}}\vee
e)=E_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}})+4,$ $\displaystyle
B^{3}(\mathcal{G}_{\mathfrak{f}^{0}}\vee
e)=B^{3}(\mathcal{G}_{\mathfrak{f}^{0}}),\qquad
B^{4}(\mathcal{G}_{\mathfrak{f}^{0}}\vee
e)=B^{4}(\mathcal{G}_{\mathfrak{f}^{0}}),\qquad
F_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}}\vee
e)=F_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}}).$

Suppose that $4-p-3$ of the $f_{i}$’s are closed and three are open. Cutting
$e$ gives

$\displaystyle F_{{\rm int}}(\mathcal{G}_{\mathfrak{f}^{0}}\vee e)=F_{{\rm
int}}(\mathcal{G}_{\mathfrak{f}^{0}})-1,\qquad\\!C_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}}\vee
e)=C_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}})-2,\qquad\\!E_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}}\vee
e)=E_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}})+4,$ $\displaystyle
B^{3}(\mathcal{G}_{\mathfrak{f}^{0}}\vee
e)=B^{3}(\mathcal{G}_{\mathfrak{f}^{0}}),\qquad
B^{4}(\mathcal{G}_{\mathfrak{f}^{0}}\vee
e)=B^{4}(\mathcal{G}_{\mathfrak{f}^{0}}),\qquad
F_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}}\vee
e)=F_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}})-3.$

Note that this case does not apply for $p=2$.

For $p=0$ an additional situation applies: assume that all four $f_{i}$’s are
open. Cutting $e$ gives

$\displaystyle F_{{\rm int}}(\mathcal{G}_{\mathfrak{f}^{0}}\vee e)=F_{{\rm
int}}(\mathcal{G}_{\mathfrak{f}^{0}}),\qquad
C_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}}\vee
e)=C_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}})-3,\qquad
E_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}}\vee
e)=E_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}})+4,$ $\displaystyle
B^{3}(\mathcal{G}_{\mathfrak{f}^{0}}\vee
e)=B^{3}(\mathcal{G}_{\mathfrak{f}^{0}}),\qquad
B^{4}(\mathcal{G}_{\mathfrak{f}^{0}}\vee
e)=B^{4}(\mathcal{G}_{\mathfrak{f}^{0}}),\qquad
F_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}}\vee
e)=F_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}})-6.$

Lemma 3.1 relates the same numbers for $\mathcal{G}_{\mathfrak{f}^{0}}/e$ and
$\mathcal{G}_{\mathfrak{f}^{0}}$ from which one is able to prove (3.9), (3.10)
and (3.11). ∎

Before focusing on the invariant, let us establish an intermediate result.

######  Lemma 3.3.

For any representative $\mathcal{G}$ of a rank $4$ w-colored graph
$\mathfrak{G}$, we have

$\displaystyle\sum_{{\mathbf{b}}^{3}\in\mathcal{B}^{3}}V_{{\mathbf{b}}^{3}}\geq
6V,\qquad\sum_{{\mathbf{b}}^{3}\in\mathcal{B}^{3}}E_{{\mathbf{b}}^{3}}=6E,\qquad\sum_{{\mathbf{b}}^{3}\in\mathcal{B}^{3}}F_{{\rm
int};{\mathbf{b}}^{3}}=3F_{{\rm int}}.$ (3.12)

Moreover,

$\displaystyle\sum_{{\mathbf{b}}^{4}\in\mathcal{B}^{4}}B^{3}_{{\mathbf{b}}^{4}}=2B^{3},\qquad
3B^{4}\leq 2B^{3},\qquad B^{4}\geq 4.$ (3.13)

###### Proof.

Each vertex of $\mathcal{G}_{\mathfrak{f}^{0}}$ can be decomposed at least in
6 vertices (6 vertices is the minimum given by the simplest vertex of the form
$\mathcal{G}_{1,\mathfrak{f}^{0}(\mathcal{G}_{1})}$ in Fig. 10 for any rank 4
w-colored graph) which could belong to a $3$-bubble. This gives the first
relation in (3.12). Furthermore, using the colors, one observes that each edge
of $\mathcal{G}_{\mathfrak{f}^{0}}$ splits into 6 ribbon edges, and each
internal face of $\mathcal{G}_{\mathfrak{f}^{0}}$ belongs to three
$3$-bubbles. Thus we have the rest of equations in (3.12).

We concentrate now on (3.13). Consider a $3$-bubble ${\mathbf{b}}^{3}$ in
$\mathcal{G}_{\mathfrak{f}^{0}}$, ${\mathbf{b}}^{3}$ is made with $3$ colors
of $\mathcal{G}_{\mathfrak{f}^{0}}$. Since $\mathcal{G}_{\mathfrak{f}^{0}}$ is
made with $5$ colors, ${\mathbf{b}}^{3}$ is contained exactly in two
$4$-bubbles obtained by adding to the three colors in ${\mathbf{b}}^{3}$ one
of the two remaining colors of $\mathcal{G}_{\mathfrak{f}^{0}}$. Hence, the
first equation in (3.13) follows. Using again the color prescription, each
$4$-bubble has at least three $3$-bubbles, $B^{3}_{{\mathbf{b}}^{4}}\geq 3$.
Summing each member of this relation on the set of $4$-bubbles, we end the
proof the second equation in (3.13). ∎

Now, we can introduce a parametrized invariant on this category of graph.

######  Proposition 3.4.

Let $\mathcal{G}_{\mathfrak{f}^{0}}$ be any representative of a rank $4$
w-colored graph $\mathfrak{G}$. There exist some positive rational numbers
$\alpha_{3}$ and $\alpha_{4}$ such that

$\displaystyle\gamma_{4;(\alpha_{3},\alpha_{4})}(\mathcal{G}_{\mathfrak{f}^{0}})=6(V-E)+3F_{{\rm
int}}-2(1+\alpha_{3})B^{3}+(3\alpha_{3}-\alpha_{4})B^{4}$

is a negative integer.

###### Proof.

Consider a representative $\mathcal{G}_{\mathfrak{f}^{0}}$ of a rank $4$
w-colored graph. The $3$-bubbles of $\mathcal{G}_{\mathfrak{f}^{0}}$ are
connected rank $2$ stranded graphs or ribbon graphs with half-edges. Consider
a $3$-bubble ${\mathbf{b}}^{3}$ of $\mathcal{G}_{\mathfrak{f}^{0}}$ and
$\widetilde{{\mathbf{b}}^{3}}$ its underline ribbon graph. Using the Euler
formula, one has

$\displaystyle V_{{\mathbf{b}}^{3}}-E_{{\mathbf{b}}^{3}}+F_{{\rm
int};{\mathbf{b}}^{3}}+C_{\partial}\big{(}{\mathbf{b}}^{3}\big{)}-2=-\kappa\leq
0,$

with $\kappa$ the genus of $\widetilde{{\mathbf{b}}^{3}}$. Hence,

$\displaystyle V_{{\mathbf{b}}^{3}}-E_{{\mathbf{b}}^{3}}+F_{{\rm
int};{\mathbf{b}}^{3}}\leq 2.$ (3.14)

A summation on all the $3$-bubbles of $\mathcal{G}_{\mathfrak{f}^{0}}$ gives

$\displaystyle\sum_{{\mathbf{b}}^{3}\in\mathcal{B}^{3}}(V_{{\mathbf{b}}^{3}}-E_{{\mathbf{b}}^{3}})+\sum_{{\mathbf{b}}^{3}\in\mathcal{B}^{3}}F_{{\rm
int};{\mathbf{b}}^{3}}-2B^{3}\leq 0.$

From Lemma 3.3, we have

$\displaystyle 6(V-E)+3F_{{\rm int}}-2B^{3}\leq 0,\qquad 3B^{4}-2B^{3}\leq
0,\qquad-B^{4}+4\leq 0.$ (3.15)

Consider some positive rational numbers $\alpha_{3}$ and $\alpha_{4}$ such
that $-2(1+\alpha_{3})B^{3}+(3\alpha_{3}-\alpha_{4})B^{4}$ is an integer.
Multiplying the two last relations in (3.15) by $\alpha_{3}$ and $\alpha_{4}$,
respectively, we obtain $3\alpha_{3}B^{4}-2\alpha_{3}B^{3}\leq 0$ and
$-\alpha_{4}B^{4}+4\alpha_{4}\leq 0$. Combining these two last relations with
the first relation in (3.15), we obtain

$\displaystyle 6(V-E)+3F_{{\rm
int}}-2(1+\alpha_{3})B^{3}+(3\alpha_{3}-\alpha_{4})B^{4}+4\alpha_{4}\leq 0,$
(3.16)

i.e., $\gamma_{4;(\alpha_{3},\alpha_{4})}(\mathcal{G}_{\mathfrak{f}^{0}})$ is
a negative integer. ∎

Clearly, the quantity $\gamma_{4;(\alpha_{3},\alpha_{4})}(\cdot)$ is a
negative integer for all non negative integers $\alpha_{3}$ and $\alpha_{4}$.
Furthermore, $\gamma_{4;(\alpha_{3},\alpha_{4})}(\cdot)$ is still a negative
integer if $\alpha_{3}$ and $\alpha_{4}$ are equal to specific positive
rational numbers.

We consider the combinatorial object $6(V-E)+3F_{{\rm
int}}-2(1+\alpha_{3})B^{3}+(3\alpha_{3}-\alpha_{4})B^{4}$ as a general̄ized
Euler characteristic. Indeed, fixing $3\alpha_{3}-\alpha_{4}>0$ (since
$1+\alpha_{3}>0$), this integer is reminiscent of a weighted form of the Euler
characteristic, if one considers the $B^{d}$’s as Betti numbers. Of course,
one also expects an alternating sum of positive integers as in the Euler
characteristic. Here we see that we can achieve this only by tuning properly
the parameters alphas.

We can define the polynomial invariant on rank 4 w-colored graphs.

######  Definition 3.5 (topological invariant for rank 4 w-colored graph).

Let $\mathfrak{G}(\mathcal{V},\mathcal{E},\mathfrak{f}^{0})$ be a rank 4
w-colored graph and $\alpha_{3}$ and $\alpha_{4}$ some positive rational
numbers. The generalized topological invariant associated with $\mathfrak{G}$
is given by the following function associated with any of its representatives
$\mathcal{G}$ (using the above notations)

$\displaystyle\mathfrak{T}_{\mathfrak{G};(\alpha_{3},\alpha_{4})}(x,y,z,s,w,q,t)=\mathfrak{T}_{\mathcal{G}_{\mathfrak{f}^{0}};(\alpha_{3},\alpha_{4})}(x,y,z,s,w,q,t)$
$\displaystyle\qquad{}=\sum_{A\Subset\mathcal{G}_{\mathfrak{f}^{0}}}(x-1)^{\operatorname{r}(\mathcal{G})-\operatorname{r}(A)}(y-1)^{n(A)}z^{9k(A)-\gamma_{4;(\alpha_{3},\alpha_{4})}(A)}s^{C_{\partial}(A)}w^{F_{\partial}(A)}q^{E_{\partial}(A)}t^{f(A)},$

with $\gamma_{4;(\alpha_{3},\alpha_{4})}(A)=6(V(A)-E(A))+3F_{{\rm
int}}(A)-2(1+\alpha_{3})B^{3}(A)+(3\alpha_{3}-\alpha_{4})B^{4}(A)$ a negative
integer.

Comparing this polynomial with the one defined on rank 3 w-colored of
c-subgraphs, we see that in addition to the 3-bubbles, the polynomial
invariant also takes into consideration 4-bubbles.

We can now introduce our main theorem.

######  Theorem 3.6 (contraction/cut rule for w-colored graphs).

Let $\mathfrak{G}$ be a rank $4$ w-colored graph and $\alpha_{3}$ and
$\alpha_{4}$ some positive rational numbers. Then, for a regular edge $e$ of
any of the representative $\mathcal{G}_{\mathfrak{f}^{0}}$ of $\mathfrak{G}$,
we have

$\displaystyle\mathfrak{T}_{\mathcal{G}_{\mathfrak{f}^{0}};(\alpha_{3},\alpha_{4})}=\mathfrak{T}_{\mathcal{G}_{\mathfrak{f}^{0}}\vee
e;(\alpha_{3},\alpha_{4})}+\mathfrak{T}_{\mathcal{G}_{\mathfrak{f}^{0}}/e;(\alpha_{3},\alpha_{4})}.$
(3.17)

For a bridge $e$, we have $\mathfrak{T}_{\mathcal{G}_{\mathfrak{f}^{0}}\vee
e;(\alpha_{3},\alpha_{4})}=z^{15+4\alpha_{4}}sw^{6}q^{4}t^{2}\mathfrak{T}_{\mathcal{G}_{\mathfrak{f}^{0}}/e;(\alpha_{3},\alpha_{4})}$
and

$\displaystyle\mathfrak{T}_{\mathcal{G}_{\mathfrak{f}^{0}};(\alpha_{3},\alpha_{4})}=[(x-1)z^{15+4\alpha_{4}}sw^{6}q^{4}t^{2}+1]\mathfrak{T}_{\mathcal{G}_{\mathfrak{f}^{0}}/e;(\alpha_{3},\alpha_{4})}.$
(3.18)

For a trivial p-inner loop $e$, $p=0,1,2,3$, we have

$\displaystyle\mathfrak{T}_{\mathcal{G}_{\mathfrak{f}^{0}};(\alpha_{3},\alpha_{4})}=\mathfrak{T}_{\mathcal{G}_{\mathfrak{f}^{0}}\vee
e;(\alpha_{3},\alpha_{4})}+(y-1)z^{-15+6p+3\alpha_{3}(4-p)+\alpha_{4}(3p-8)}\mathfrak{T}_{\mathcal{G}_{\mathfrak{f}^{0}}/e;(\alpha_{3},\alpha_{4})}.$
(3.19)

###### Proof.

Let $\mathcal{G}_{\mathfrak{f}^{0}}$ be a representative of a rank 4 w-colored
graph $\mathfrak{G}$. Our main concern is the change in the number of internal
and external $i$-bubbles ($i=3,4$) and the independence of the final result on
the representative $\mathcal{G}_{\mathfrak{f}^{0}}$. From Proposition 2.14, we
can define $\mathfrak{G}\vee e$ and $\mathfrak{G}/e$ and conclude that the
resulting polynomials $\mathfrak{T}_{\mathcal{G}_{\mathfrak{f}^{0}}\vee
e;(\alpha_{3},\alpha_{4})}$ and
$\mathfrak{T}_{\mathcal{G}_{\mathfrak{f}^{0}}/e;(\alpha_{3},\alpha_{4})}$ are
independent on the representative $\mathcal{G}_{\mathfrak{f}^{0}}\vee e$ and
$\mathcal{G}_{\mathfrak{f}^{0}}/e$, respectively.

Let us prove the equation (3.17). Consider an ordinary edge $e$ of
$\mathcal{G}_{\mathfrak{f}^{0}}$, the set of spanning c-subgraphs which do not
contain $e$ being the same as the set of spanning c-subgraphs of
$\mathcal{G}_{\mathfrak{f}^{0}}\vee e$, the number of open and closed
$i$-bubbles ($i=3,4$) on each subgraph is the same, it is direct to get
$\sum\limits_{A\Subset\mathcal{G}_{\mathfrak{f}^{0}};e\notin
A}(\cdot)=\mathfrak{T}_{\mathcal{G}_{\mathfrak{f}^{0}}\vee
e;(\alpha_{3},\alpha_{4})}$. The strands of $e$ are clearly preserved after
the contraction. The bubbles which do not pass through $e$ are not affected at
all by the procedure. The bubbles passing through $e$ are also preserved since
the contraction do not delete faces or strands. Hence
$\sum\limits_{A\Subset\mathcal{G}_{\mathfrak{f}^{0}};e\in
A}(\cdot)=\mathfrak{T}_{\mathcal{G}_{\mathfrak{f}^{0}}/e;(\alpha_{3},\alpha_{4})}$.

We now concentrate on the bridge case and (3.18). Cutting a bridge yields,
from the sum $\sum\limits_{A\Subset\mathcal{G}_{\mathfrak{f}^{0}};e\notin A}$,
the product $(x-1)\mathfrak{T}_{\mathcal{G}_{\mathfrak{f}^{0}}\vee
e;(\alpha_{3},\alpha_{4})}$. Using the mapping between
$\\{A\Subset\mathcal{G}_{\mathfrak{f}^{0}};e\in A\\}$ and
$\\{A\Subset\mathcal{G}_{\mathfrak{f}^{0}}/e\\}$, we obtain
$\sum\limits_{A\Subset\mathcal{G}_{\mathfrak{f}^{0}};e\in
A}(\cdot)=\mathfrak{T}_{\mathcal{G}_{\mathfrak{f}^{0}}/e;(\alpha_{3},\alpha_{4})}$.
We now investigate the relation between
$\mathfrak{T}_{\mathcal{G}_{\mathfrak{f}^{0}}\vee e;(\alpha_{3},\alpha_{4})}$
and $\mathfrak{T}_{\mathcal{G}_{\mathfrak{f}^{0}}/e;(\alpha_{3},\alpha_{4})}$.
There is a bijection between $A\Subset\mathcal{G}_{\mathfrak{f}^{0}}\vee e$
and $A^{\prime}\Subset\mathcal{G}_{\mathfrak{f}^{0}}/e$ where each $A$ and
$A^{\prime}$ are both uniquely related to some
$A_{0}\Subset\mathcal{G}_{\mathfrak{f}^{0}}$ as $A=A_{0}\vee e$ and
$A^{\prime}=A_{0}/e$. Using Lemma 3.2, the relation (3.18) follows.

Let us investigate the trivial $p$-inner loop case and prove (3.19). As
discussed earlier, the relation
$\sum\limits_{A\Subset\mathcal{G}_{\mathfrak{f}^{0}};e\notin
A}(\cdot)=\mathfrak{T}_{\mathcal{G}_{\mathfrak{f}^{0}}\vee
e;(\alpha_{3},\alpha_{4})}$ should be direct. Focus now on the second sum.

Consider a trivial $p$-inner loop $e$ in $\mathcal{G}_{\mathfrak{f}^{0}}$.
Then $e$ is a trivial $p$-inner loop in all
$A\Subset\mathcal{G}_{\mathfrak{f}^{0}}$ containing $e$. Contracting $e$
generates $p$ discs and $4-p$ non trivial vertices. Using Lemma 3.1, the
nullity is $n(A)=n(A^{\prime})+1$ which ensures the factor $y-1$, and the
exponent of $z$ becomes

$\displaystyle 9k(A)-\big{[}6(V(\mathcal{G}_{\mathfrak{f}^{0}})-E(A))+3F_{\rm
int}(A)-2(1+\alpha_{3})B^{3}(A)+(3\alpha_{3}-\alpha_{4})B^{4}(A)\big{]}$
$\displaystyle\qquad{}=9(k(A^{\prime})-3)-\big{[}6[V(\mathcal{G}_{\mathfrak{f}^{0}}/e)-3)-(E(A^{\prime})+1)]+3F_{\rm
int}(A^{\prime})$
$\displaystyle\qquad\quad{}-2(1+\alpha_{3})(B^{3}(A^{\prime})-\beta_{p})+(3\alpha_{3}-\alpha_{4})(B^{4}(A^{\prime})-\beta^{\prime}_{p})\big{]}$
$\displaystyle\qquad{}=9k(A^{\prime})-\big{[}6(V(\mathcal{G}_{\mathfrak{f}^{0}})-E(A^{\prime}))+3F_{\rm
int}(A^{\prime})-2(1+\alpha_{3})B^{3}(A^{\prime})$
$\displaystyle\qquad\quad{}+(3\alpha_{3}-\alpha_{4})B^{4}(A^{\prime})\big{]}-15+6p+3\alpha_{3}(4-p)+\alpha_{4}(3p-8),$

where $\beta_{p}=6-3p$, $\beta^{\prime}_{p}=8-3p$, $A$ and $A^{\prime}$ refer
to the subgraphs related by bijection between spanning c-subgraphs of
$\\{A\Subset\mathcal{G}_{\mathfrak{f}^{0}};e\in A\\}$ and
$\\{A^{\prime}\Subset\mathcal{G}_{\mathfrak{f}^{0}}/e\\}$. Finally, one gets
$(y-1)z^{-15+6p+3\alpha_{3}(4-p)+\alpha_{4}(3p-8)}\mathfrak{T}_{\mathcal{G}_{\mathfrak{f}^{0}}/e;(\alpha_{3},\alpha_{4})}$.
As previously shows, this result is independent of the representative. ∎

Let us come back on the expression of our polynomial to make a comparison with
recent results introduced in [16]. One variable (the variable $s$) stands for
the number of connected components of the boundary graph of a spanning
c-subgraph. We replace this number by
$\sum_{{\mathbf{b}}^{3}}C_{\partial}({\mathbf{b}}^{3})$. With the change of
variables $s=z^{-1}$, we directly recover the sum of genera as introduced by
Tanasa [16] on some special closed tensor graph (with, necessarily, all
3-bubbles closed). However, there is a relationship between the number of
boundary components of a graph $\mathcal{G}$ denoted
$C_{\partial}(\mathcal{G})$ and the sum
$\sum_{{\mathbf{b}}^{3}}C_{\partial}({\mathbf{b}}^{3})$. This certainly needs
to be investigated in the context of w-colored stranded graphs.

##  4 The polynomial invariant for $\boldsymbol{nD}$ w-colored graphs

Having identified a rank 4 invariant polynomial, we can quickly generalize it
in any rank starting by extending the previous results.

######  Lemma 4.1.

Consider a representative $\mathcal{G}_{\mathfrak{f}^{0}}$ of a rank $n$
w-colored graph $\mathfrak{G}$. $\forall$ $3\leq p\leq d\leq n$,

$\displaystyle\sum_{{\mathbf{b}}^{d}\in\mathcal{B}^{d}}V_{{\mathbf{b}}^{d}}\geq\complement_{n}^{d-1}V,\qquad\sum_{{\mathbf{b}}^{d}\in\mathcal{B}^{d}}E_{{\mathbf{b}}^{d}}=\complement_{n}^{d-1}E,\qquad\sum_{{\mathbf{b}}^{d}\in\mathcal{B}^{d}}F_{{\rm
int};{\mathbf{b}}^{d}}=\complement_{n-1}^{d-2}F_{{\rm int}},$ (4.1)
$\displaystyle\sum_{{\mathbf{b}}^{d}\in\mathcal{B}^{d}}B^{p}_{{\mathbf{b}}^{d}}=\complement_{n-p+1}^{d-p}B^{p},\qquad\complement_{d-1}^{p-1}B^{d}\leq\complement_{n-p+1}^{d-p}B^{p}.$
(4.2)

###### Proof.

Consider a vertex $v$ of a representative $\mathcal{G}_{\mathfrak{f}^{0}}$ of
a rank $n$ w-colored graph; $v$ can be decomposed, at least, in
$\complement_{n}^{d-1}$ ($d\leq n$) vertices which could belong to a
$d$-bubble (this number is the minimum given by the simplest vertex of the
graph $\mathcal{G}_{1,\mathfrak{f}^{0}(\mathcal{G}_{1})}$ in Fig. 11). We then
prove the first relation in (4.1). From the coloring, each edge of
$\mathcal{G}_{\mathfrak{f}^{0}}$ decomposes into $\complement_{n}^{d-1}$ edges
belonging to a $d$-bubble. Each internal face of
$\mathcal{G}_{\mathfrak{f}^{0}}$ is shared by $\complement_{n-1}^{d-2}$
$d$-bubbles. Thus we have the remaining equations in (4.1).

Let us prove (4.2). Consider the $d$-bubbles in
$\mathcal{G}_{\mathfrak{f}^{0}}$. Each $p$-bubble ${\mathbf{b}}^{p}$ ($p\leq
d$) in $\mathcal{G}_{\mathfrak{f}^{0}}$, is a $p$-bubble of
$\complement_{n-p+1}^{d-p}$ $d$-bubbles of $\mathcal{G}_{\mathfrak{f}^{0}}$.
Indeed, consider a $p$-bubble in $\mathcal{G}_{\mathfrak{f}^{0}}$, it remains
$n-p+1$ colors from which we can take arbitrary $d-p$ colors to obtain a
$d$-bubble. The first equation in (4.2) follows. Using once again the
coloring, each $d$-bubble has at least $\complement_{d-1}^{p-1}$ $p$-bubbles,
that is $B^{p}_{{\mathbf{b}}^{d}}\geq\complement_{d-1}^{p-1}$. We can now sum
each member of this relation on the total number of $d$-bubbles and complete
the proof of (4.2). ∎

######  Proposition 4.2.

Let $\mathcal{G}_{\mathfrak{f}^{0}}$ be any representative of a rank $n\geq 4$
w-colored graph. There exist some positive rational numbers
$\boldsymbol{\alpha}=\\{\alpha_{k}\\}_{k=3,\dots,n}$ such that

$\displaystyle\gamma_{n;\boldsymbol{\alpha}}(\mathcal{G}_{\mathfrak{f}^{0}})=\frac{n(n-1)}{2}(V-E)+(n-1)F_{{\rm
int}}-(2+(n-2)\alpha_{3})B^{3}$
$\displaystyle\hphantom{\gamma_{n;\boldsymbol{\alpha}}(\mathcal{G}_{\mathfrak{f}^{0}})=}{}+\sum_{k=4}^{n}\big{[}(k-1)\alpha_{k-1}-(n-k+1)\alpha_{k}\big{]}B^{k}$

is a negative integer.

###### Proof.

Consider a representative of a rank $n$ w-colored graph. The $3$-bubbles of
$\mathcal{G}_{\mathfrak{f}^{0}}$ are ribbon graphs. Each of them satisfies
(3.14) and the sum over all the $3$-bubbles of
$\mathcal{G}_{\mathfrak{f}^{0}}$ gives

$\displaystyle\sum_{{\mathbf{b}}^{3}\in\mathcal{B}^{3}}(V_{{\mathbf{b}}^{3}}-E_{{\mathbf{b}}^{3}})+\sum_{{\mathbf{b}}^{3}\in\mathcal{B}^{3}}F_{{\rm
int};{\mathbf{b}}^{3}}-2B^{3}\leq 0.$

From Lemma 4.1, we have

$\displaystyle\frac{n(n-1)}{2}(V-E)+(n-1)F_{{\rm int}}-2B^{3}\leq 0,$
$\displaystyle kB^{k+1}-(n-k+1)B^{k}\leq
0,\qquad\forall\,k=3,\dots,n-1,\qquad-B^{n}+n\leq 0.$ (4.3)

We multiply the second relation in (4.3) by a positive integer $\alpha_{k}$,
$k=3,\dots,n-1$ and the last relation by a positive integer $\alpha_{n}$ such
that the quantity

$\displaystyle-(2+(n-2)\alpha_{3})B^{3}+\sum_{k=4}^{n}\big{[}(k-1)\alpha_{k-1}-(n-k+1)\alpha_{k}\big{]}B^{k}$

is an integer. We obtain

$\displaystyle k\alpha_{k}B^{k+1}-(n-k+1)\alpha_{k}B^{k}\leq
0,\qquad\forall\,k=3,\dots,n-1,\qquad-\alpha_{n}B^{n}+n\alpha_{n}\leq 0.$
(4.4)

A summation from $k=3$ to $k=n-1$ of the first relation in (4.4) and then
adding the result to the second inequality leads to

$\displaystyle\sum_{k=3}^{n-1}\big{[}k\alpha_{k}B^{k+1}-(n-k+1)\alpha_{k}B^{k}\big{]}-\alpha_{n}B^{n}+n\alpha_{n}\leq
0.$ (4.5)

Adding relation (4.5) to the first relation in (4.3) achieves the proof. ∎

One may wonder why the number $B^{2}$ is not used in the above summation.
$B^{2}$ denotes the number of 2-bubbles which is equal to $F_{{\rm
int}}+C_{\partial}$. One notes that the quantity $C_{\partial}$ is not used in
the invariant, we have introduced a different variable for internal faces and
boundary components.

The number $\gamma_{n;\boldsymbol{\alpha}}(\cdot)$ is a generalized and
weighted Euler characteristics. If one envisages to have an alternating sum of
positive integers, we must require the following conditions:

$\displaystyle(k-1)\alpha_{k-1}-(n-k+1)\alpha_{k}>0\qquad\mbox{if $k$ is
even},$ $\displaystyle(k-1)\alpha_{k-1}-(n-k+1)\alpha_{k}<0\qquad\mbox{if $k$
is odd}.$

This system which is triangular can be clearly solved and generally admits
several solutions.

It is instructive to investigate how the above invariant
$\gamma_{n;\boldsymbol{\alpha}}(\cdot)$ can be prolonged to the lowest ranks,
$n=2$ and $n=3$. Consider a representative $\mathcal{G}_{\mathfrak{f}^{0}}$ of
rank $n$ w-colored stranded graphs $\mathfrak{G}$.

For $n=2$, $\mathcal{G}_{\mathfrak{f}^{0}}$ is a half-edged ribbon graph.
Consider the underlying ribbon graph $\mathcal{G}$, or ribbon graph in the
sense of Bollobás and Riordan, the invariant used is $2k(A)-(V(A)-E(A)+F(A))$
for each $A\Subset\mathcal{G}$. In the case of half-edged ribbon graphs, the
invariant is $2k(A)-(V(A)-E(A)+F_{{\rm int}}(A))$ for each
$A\Subset\mathcal{G}_{\mathfrak{f}^{0}}$. Since this quantity is always non
negative, we have for a connected graph $\mathcal{G}_{\mathfrak{f}^{0}}$,

$\displaystyle
V(\mathcal{G}_{\mathfrak{f}^{0}})-E(\mathcal{G}_{\mathfrak{f}^{0}})+F_{{\rm
int}}(\mathcal{G}_{\mathfrak{f}^{0}})\leq 2,$ (4.6)

where $V$, $E$ and $F_{{\rm int}}$ are, respectively, the number of vertices,
edges and internal faces. We set

$\displaystyle\gamma_{2}(\mathcal{G}_{\mathfrak{f}^{0}})=V-E+F_{{\rm int}}.$

This is precisely the invariant used in the definition of the BR polynomial on
ribbon graphs with half-edges [1].

For $n=3$, the $3$-bubbles of $\mathcal{G}_{\mathfrak{f}^{0}}$ are connected
rank $2$ or ribbon graphs. Each of them satisfies (4.6) and a summation on all
the $3$-bubbles of $\mathcal{G}_{\mathfrak{f}^{0}}$ gives

$\displaystyle\sum_{{\mathbf{b}}^{3}\in\mathcal{B}^{3}}(V_{{\mathbf{b}}^{3}}-E_{{\mathbf{b}}^{3}})+\sum_{{\mathbf{b}}^{3}\in\mathcal{B}^{3}}F_{{\rm
int};{\mathbf{b}}^{3}}-2B^{3}\leq 0.$

Using now Lemma 4.1, we have

$\displaystyle 3(V-E)+2F_{{\rm int}}-2B^{3}\leq 0,\qquad-B^{3}+3\leq 0.$ (4.7)

Consider a positive rational number $\alpha_{3}$ such that
$(2+\alpha_{3})B^{3}$ is an integer. We multiply the second relation in (4.7)
by $\alpha_{3}$ and obtain $-\alpha_{3}B^{3}+3\alpha_{3}\leq 0$. We add this
relation to the first relation in (4.7) and get

$\displaystyle 3(V-E)+2F_{{\rm int}}-(2+\alpha_{3})B^{3}\leq-3\alpha_{3}.$
(4.8)

We can then set

$\displaystyle\gamma_{3;\alpha_{3}}(\mathcal{G})=3(V-E)+2F_{{\rm
int}}-(2+\alpha_{3})B^{3}.$

The expression $\gamma_{3;0}(\cdot)$ is the invariant introduced on rank 3
w-colored stranded graphs in [1]. Hence, the present framework fully extends
that work to a one-parameter family of invariant polynomials.

######  Definition 4.3 (topological invariant for rank $n$ w-colored graph).

Let $\mathfrak{G}(\mathcal{V},\mathcal{E},\mathfrak{f}^{0})$ be a rank $n$
w-colored graph and $\boldsymbol{\alpha}=\\{\alpha_{k}\\}_{k=3,\dots,n}$ some
positive rational numbers. The generalized topological invariant associated
with $\mathfrak{G}$ is given by the following function associated with any of
its representatives $\mathcal{G}_{\mathfrak{f}^{0}}$.

$\displaystyle\mathfrak{T}_{\mathfrak{G};\boldsymbol{\alpha}}(x,y,z,s,w,q,t)=\mathfrak{T}_{\mathcal{G}_{\mathfrak{f}^{0}};\boldsymbol{\alpha}}(x,y,z,s,w,q,t)$
$\displaystyle=\sum_{A\Subset\mathcal{G}_{\mathfrak{f}^{0}}}(x-1)^{\operatorname{r}(\mathcal{G}_{\mathfrak{f}^{0}})-\operatorname{r}(A)}(y-1)^{n(A)}z^{\frac{(n-1)(n+2)}{2}k(A)-\gamma_{n;\boldsymbol{\alpha}}(A)}s^{C_{\partial}(A)}w^{F_{\partial}(A)}q^{E_{\partial}(A)}t^{f(A)},$
(4.9)

with

$\displaystyle\gamma_{n;\boldsymbol{\alpha}}(A)=\frac{n(n-1)}{2}(V(A)-E(A))+(n-1)F_{{\rm
int}}(A)-(2+(n-2)\alpha_{3})B^{3}(A)$
$\displaystyle\hphantom{\gamma_{n;\boldsymbol{\alpha}}(A)=}{}+\sum_{k=4}^{n}\big{[}(k-1)\alpha_{k-1}-(n-k+1)\alpha_{k}\big{]}B^{k}(A)$

a negative integer.

Remark that Lemma 3.3 finds an extension for any rank $n$ w-colored graph.

$\mathcal{G}_{1,\mathfrak{f}^{0}(\mathcal{G}_{1})}$$0$$\bar{0}$$\bar{0}$${\mathbf{b}}$$0$

Figure 11: A 3-bubble ${\mathbf{b}}$ of the graph
$\mathcal{G}_{1,\mathfrak{f}^{0}(\mathcal{G}_{1})}$ made with $n$ strands.

Let us introduce the following lemma used in the proof of our main result.

######  Lemma 4.4 (cut/contraction of special edges).

Let $\mathcal{G}_{\mathfrak{f}^{0}}$ be a representative of $\mathfrak{G}$ a
rank n w-colored graph and $e$ an edge in $\mathcal{G}_{\mathfrak{f}^{0}}$.
Then, if $e$ is a bridge in the above notations, we have

$\displaystyle k(\mathcal{G}_{\mathfrak{f}^{0}}\vee
e)=k(\mathcal{G}_{\mathfrak{f}^{0}}/e)+1,\qquad
V(\mathcal{G}_{\mathfrak{f}^{0}}\vee
e)=V(\mathcal{G}_{\mathfrak{f}^{0}}/e)+1,\qquad
E(\mathcal{G}_{\mathfrak{f}^{0}}\vee e)=E(\mathcal{G}_{\mathfrak{f}^{0}}/e),$
$\displaystyle f(\mathcal{G}_{\mathfrak{f}^{0}}\vee
e)=f(\mathcal{G}_{\mathfrak{f}^{0}}/e)+2,$ (4.10) $\displaystyle F_{{\rm
int}}(\mathcal{G}_{\mathfrak{f}^{0}}\vee e)=F_{{\rm
int}}(\mathcal{G}_{\mathfrak{f}^{0}}/e),\qquad B^{p}_{{\rm
int}}(\mathcal{G}_{\mathfrak{f}^{0}}\vee e)=B^{p}_{{\rm
int}}(\mathcal{G}_{\mathfrak{f}^{0}}/e),\qquad\forall\,3\leq p\leq n,$ (4.11)
$\displaystyle C_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}}\vee
e)=C_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}}/e)+1,\qquad
E_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}}\vee
e)=E_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}}/e)+n,$ $\displaystyle
F_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}}\vee
e)=F_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}}/e)+\complement_{n}^{2},$ (4.12)
$\displaystyle B^{p}_{{\rm ext}}(\mathcal{G}_{\mathfrak{f}^{0}}\vee
e)=B^{p}_{{\rm
ext}}(\mathcal{G}_{\mathfrak{f}^{0}}/e)+\complement_{n}^{n-p+1},\qquad\forall\,3\leq
p\leq n.$ (4.13)

###### Proof.

This is a simple extension of Lemma 3.2. We first concentrate on the case of
the bridge. In (4.10), the equations can be easily found. We now investigate
(4.11). Notice that the faces passing through $e$ are necessarily open by [1,
Lemma 7]. All closed faces on each side of the bridge are preserved after
cutting $e$ and are still preserved after edge contraction. Hence $F_{{\rm
int}}(\mathcal{G}_{\mathfrak{f}^{0}}\vee e)=F_{{\rm
int}}(\mathcal{G}_{\mathfrak{f}^{0}}/e)$, $B^{p}_{{\rm
int}}(\mathcal{G}_{\mathfrak{f}^{0}}\vee e)=B^{p}_{{\rm
int}}(\mathcal{G}_{\mathfrak{f}^{0}}/e)$ $\forall$ $3\leq p\leq n$. Let us
focus on (4.12) and use the fact that the $n$ external faces belong to the
same boundary component. By cutting $e$, this unique component yields two
boundary components. It is direct to get
$C_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}}\vee
e)=C_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}}/e)+1$,
$E_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}}\vee
e)=E_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}}/e)+n$ (the cut of $e$ divides
each external face into two different external strands) and
$F_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}}\vee
e)=F_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}}/e)+\complement_{n}^{2}$ since
$C_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}}/e)=C_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}})$,
$E_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}}/e)=E_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}})$
and
$F_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}}G/e)=F_{\partial}(\mathcal{G}_{\mathfrak{f}^{0}})$
from Lemma 2.12. For the number of external bubbles, there are
$\complement_{n}^{n-p+1}$ $p$-bubbles in $\mathcal{G}_{\mathfrak{f}^{0}}$
passing through the bridge. These bubbles are clearly in
$\mathcal{G}_{\mathfrak{f}^{0}}/e$ and, cutting the bridge, each of these
bubbles splits in two. This yields (4.13). ∎

We can now introduce our main result of this section.

######  Theorem 4.5 (contraction/cut rule for w-colored graphs).

Let $\mathfrak{G}$ be a rank $n$ w-colored graph and and
$\boldsymbol{\alpha}=\\{\alpha_{k}\\}_{k=3,\dots,n}$ some positive rational
numbers. Then, for a regular edge $e$ of any of the representative
$\mathcal{G}_{\mathfrak{f}^{0}}$ of $\mathfrak{G}$, we have

$\displaystyle\mathfrak{T}_{\mathcal{G}_{\mathfrak{f}^{0}};\boldsymbol{\alpha}}=\mathfrak{T}_{\mathcal{G}_{\mathfrak{f}^{0}}\vee
e;\boldsymbol{\alpha}}+\mathfrak{T}_{\mathcal{G}_{\mathfrak{f}^{0}}/e;\boldsymbol{\alpha}}.$
(4.14)

For a bridge $e$, we have

$\displaystyle\mathfrak{T}_{\mathcal{G}_{\mathfrak{f}^{0}}\vee
e;\boldsymbol{\alpha}}=z^{(n-1)(n+1)+n\alpha_{n}}sw^{\frac{n(n-1)}{2}}q^{n}t^{2}\mathfrak{T}_{\mathcal{G}_{\mathfrak{f}^{0}}/e;\boldsymbol{\alpha}}$

and

$\displaystyle\mathfrak{T}_{\mathcal{G}_{\mathfrak{f}^{0}};\boldsymbol{\alpha}}=\big{[}(x-1)z^{(n-1)(n+1)+n\alpha_{n}}sw^{\frac{n(n-1)}{2}}q^{n}t^{2}+1\big{]}\mathfrak{T}_{\mathcal{G}_{\mathfrak{f}^{0}}/e;\boldsymbol{\alpha}}.$

This proof is an extended form of the proof given in Theorem 3.6 but with a
more larger number of bubbles. We see that in addition to the (3,4)-bubbles,
we have also some $i$-bubbles ($i\geq 4$).

###### Proof.

Consider a representative $\mathcal{G}_{\mathfrak{f}^{0}}$ of a rank $n$
w-colored graph $\mathfrak{G}$. Following the proof of (3.17) in Theorem 3.6
and replacing $(3,4)$-bubbles by $i$-bubbles ($i\geq 3$), (4.14) is direct.
Moreover, the same arguments for proving the bridge relation and (3.18), using
Lemma 4.4 instead of Lemma 3.2 allow us to achieve the proof. ∎

Theorem 4.5 shows that the rank $D$ w-colored graph polynomial satisfies the
recurrence relation of contraction and cut of ordinary edges. For $n=3$,
$\alpha_{3}=0$, we get Theorem 2.18 and $n=4$ leads to Theorem 3.6. Concerning
special edges, we have only discussed the bridge case. There are certainly
some relations for trivial $p$-inner self-loops ($p=0,\dots,n$) but these
relations are numerous and lengthy and do not add much to the discussion.

The reductions of the above polynomial (4.9) to
$\mathfrak{T}^{\prime}_{\mathcal{G}_{\mathfrak{f}^{0}};\boldsymbol{\alpha}}$,
$\mathfrak{T}^{\prime\prime}_{\mathcal{G}_{\mathfrak{f}^{0}};\boldsymbol{\alpha}}$
and
$\mathfrak{T}^{\prime\prime\prime}_{\mathcal{G}_{\mathfrak{f}^{0}};\boldsymbol{\alpha}}$
also satisfy the contraction/cut rule. Furthermore
$\mathfrak{T}_{\mathcal{G}_{\mathfrak{f}^{0}};\boldsymbol{\alpha}}$ maps to
Tutte polynomial by taking $n=1$ and by putting the variables $z$, $w$, $q$
and $t$ to 1. Taking $n=2$ and using the mapping between the half-edged ribbon
graphs and the rank 2 w-colored graph, we directly find the polynomial
invariant on ribbon graphs with half-edges [1]. An appropriate change of
variable $s=z^{-1}$ gives the BR polynomial.

Consider a representative $\mathcal{G}_{\mathfrak{f}^{0}}$ of rank $n$
w-colored graph $\mathfrak{G}$. In the polynomial invariant introduced in
(4.9), we can add other variables $y_{i}$ ($i=0,\dots,n$) for the number of
$i$-bubbles of the boundary graph $\partial\mathcal{G}_{\mathfrak{f}^{0}}$. An
extended form of the polynomial introduced in (4.9) is given by

$\displaystyle\mathfrak{T}_{\mathfrak{G};\boldsymbol{\alpha}}(x,y,z,\\{y_{i}\\}_{i=0,\dots,n})=\mathfrak{T}_{\mathcal{G}_{\mathfrak{f}^{0}};\boldsymbol{\alpha}}(x,y,z,\\{y_{i}\\}_{i=0,\dots,n})$
$\displaystyle\qquad{}=\sum_{A\Subset\mathcal{G}_{\mathfrak{f}^{0}}}(x-1)^{\operatorname{r}(\mathcal{G}_{\mathfrak{f}^{0}})-\operatorname{r}(A)}(y-1)^{n(A)}z^{\frac{(n-1)(n+2)}{2}k(A)-\gamma_{n;\boldsymbol{\alpha}}(A)}\left(\prod_{i=0}^{n}y_{i}^{B^{i}(\partial(A))}\right).$
(4.15)

######  Definition 4.6 (multivariate form).

The multivariate form associated with (4.15) is defined by:

$\displaystyle\widetilde{\mathfrak{T}}_{\mathfrak{G}}\big{(}x,\\{\beta_{e}\\},\\{z_{i}\\}_{i=2,\dots,n-1},\\{y_{i}\\}_{i=0,\dots,n},\\{q_{i}\\}_{i=3,\dots,n}\big{)}$
$\displaystyle\qquad{}=\widetilde{\mathfrak{T}}_{\mathcal{G}_{\mathfrak{f}^{0}}}\big{(}x,\\{\beta_{e}\\},\\{z_{i}\\}_{i=2,\dots,n-1},\\{y_{i}\\}_{i=0,\dots,n},\\{q_{i}\\}_{i=3,\dots,n}\big{)}$
$\displaystyle\qquad{}=\sum_{A\Subset\mathcal{G}_{\mathfrak{f}^{0}}}x^{\operatorname{r}(A)}\left(\prod_{e\in
A}\beta_{e}\right)\left(\prod_{i=2}^{n}z_{i}^{B_{{\rm
int}}^{i}(A)}\right)\left(\prod_{i=3}^{n}z_{i}^{B_{{\rm
ext}}^{i}(A)}\right)\left(\prod_{i=0}^{n}y_{i}^{B^{i}(\partial(A))}\right),$
(4.16)

for $\\{\beta_{e}\\}_{e\in\mathcal{E}}$ labeling the edges of the graph
$\mathcal{G}_{\mathfrak{f}^{0}}$.

This multivariate form extends the polynomial of Gurau introduced in [10] in
an essential way. Indeed, in addition to the internal bubbles, we also deal
with external ones and the multivariate form (4.16) is defined on an extended
category of graphs.

The following holds for all non loop edge $e$

$\displaystyle\widetilde{\mathfrak{T}}_{\mathfrak{G}}=\widetilde{\mathfrak{T}}_{\mathfrak{G}\vee
e}+x\beta_{e}\widetilde{\mathfrak{T}}_{\mathfrak{G}/e}.$

##  5 Example

Consider the graph $\mathcal{G}$ of Fig. 12. Let us prove that the polynomial
invariant $\mathfrak{T}_{\mathcal{G};(\alpha_{3},\alpha_{4})}$ satisfies the
recurrence relation.

$e_{1}$$1$$\bar{1}$$0$$\bar{0}$$2$$\bar{2}$$3$$\bar{3}$$4$$\bar{4}$$1$$\bar{1}$$0$$\bar{0}$$2$$\bar{2}$$3$$\bar{3}$$4$$\bar{4}$$1$$\bar{1}$$0$$\bar{0}$$4$$\bar{4}$$3$$\bar{3}$$e_{1}$$e_{1}$$e_{2}$$\mathcal{G}_{\mathfrak{f}^{0}}\vee
e_{2}$$\mathcal{G}_{\mathfrak{f}^{0}}/e_{2}$$\mathcal{G}_{\mathfrak{f}^{0}}$

Figure 12: A representative $\mathcal{G}_{\mathfrak{f}^{0}}$ of a w-colored
graph, the cut graph $\mathcal{G}_{\mathfrak{f}^{0}}\vee e_{2}$ and the
contracted graph $\mathcal{G}_{\mathfrak{f}^{0}}/e_{2}$ with respect to
$e_{2}$.

Using the spanning c-subgraph summation, we get

$\displaystyle\mathfrak{T}_{\mathcal{G}_{\mathfrak{f}^{0}};(\alpha_{3},\alpha_{4})}(x,y,z,s,w,q,t)=(y-1)z^{28+7\alpha_{3}+5\alpha_{4}}sw^{11}q^{12}t^{6}+2z^{31+10\alpha_{3}+6\alpha_{4}}sw^{14}q^{16}t^{8}$
$\displaystyle\hphantom{\mathfrak{T}_{\mathcal{G}_{\mathfrak{f}^{0}};(\alpha_{3},\alpha_{4})}(x,y,z,s,w,q,t)=}{}+(x-1)z^{37+10\alpha_{3}+10\alpha_{4}}s^{2}w^{20}q^{20}t^{10}.$

We must check that

$\displaystyle\mathfrak{T}_{\mathcal{G}_{\mathfrak{f}^{0}};(\alpha_{3},\alpha_{4})}=\mathfrak{T}_{\mathcal{G}_{\mathfrak{f}^{0}}\vee
e_{2};(\alpha_{3},\alpha_{4})}+\mathfrak{T}_{\mathcal{G}_{\mathfrak{f}^{0}}/e_{2};(\alpha_{3},\alpha_{4})}.$

This is the case, since

$\displaystyle\mathfrak{T}_{\mathcal{G}_{\mathfrak{f}^{0}}\vee
e_{2};(\alpha_{3},\alpha_{4})}(x,y,z,s,w,q,t)=z^{31+10\alpha_{3}+6\alpha_{4}}sw^{14}q^{16}t^{8}$
$\displaystyle\hphantom{\mathfrak{T}_{\mathcal{G}_{\mathfrak{f}^{0}}\vee
e_{2};(\alpha_{3},\alpha_{4})}(x,y,z,s,w,q,t)=}{}+(x-1)z^{37+10\alpha_{3}+10\alpha_{4}}s^{2}w^{20}q^{20}t^{10},$

and

$\displaystyle\mathfrak{T}_{\mathcal{G}_{\mathfrak{f}^{0}}/e_{2};(\alpha_{3},\alpha_{4})}(x,y,z,s,w,q,t)=(y-1)z^{28+7\alpha_{3}+5\alpha_{4}}sw^{11}q^{12}t^{6}+z^{31+10\alpha_{3}+6\alpha_{4}}sw^{14}q^{16}t^{8}.$

The different expressions of $\gamma_{4;(\alpha_{3},\alpha_{4})}(\cdot)$ in
the above polynomial are $-19-7\alpha_{3}-5\alpha_{4}$,
$-22-10\alpha_{3}-6\alpha_{4}$ and $-28-10\alpha_{3}-10\alpha_{4}$. Putting
$\alpha_{3}=\frac{1}{2}$ and $\alpha_{4}=\frac{3}{2}$, each of these
expressions is a negative integer.

As a final remark, the parameters $\alpha_{i}$ which label the $\gamma_{n}$
invariant are positive rational numbers. We may ask a unique prescription to
determine those parameters to get a unique $\gamma_{n}$. In the non integer
rational and integer cases, we do have the following issues to solve this
problem:

In the non integer rational numbers case, we have tuned $\alpha_{3}=1/2$ and
$\alpha_{4}=3/2$ in the above example before getting $\gamma_{n}$ as an
integer for all subgraphs. Thus, for each graph, we claim that we have $2^{E}$
constraints to solve for finding $n-2$ rational coefficients. The procedure
might not in general admit a solution (usually the case when the system is
over-determined, here this happens whenever $n<2(2^{E-1}+1)$ or when the rank
do not evolve fast enough with respect to the number of edges of the graph).
Furthermore, this solution is graph dependent and we do not see how to
generalize it to the arbitrary case. We quickly realize that, in contrast,
restricted to integer coefficients, the problem has several solutions and it
is graph independent. In that case, the issue becomes different: we do have
too many ways to define the invariant. We must therefore think about a new way
to fix this object.

Consider the parameters $\alpha_{i}$ as integers. Among possible invariants,
one may consider the one with minimum value simply because it will be the
apparently less complicated to write down. Interestingly, we face here a known
problem in optimization analysis. This is an integer programming problem [18]
of the form

$\displaystyle\min\big{\\{}Bx\leq 0,\,x\in\mathbb{Z}^{n+1}\big{\\}},$

where $B=(B^{0},\dots,B^{n})\in\mathbb{N}^{n+1}$ and
$x=(a_{0}\alpha_{0},\dots,a_{n}\alpha_{n})$ with $a_{i}$ the binomial
coefficient appearing in $\gamma_{n}$. Thus studying this kind of problem
could be interesting to fix our parameters and uniquely determine the
$\gamma_{n}$ invariant. This deserves to be elucidated.

##  Appendix A Determination of the invariant by the sum of invariants
of consecutive bubbles

Consider a representative $\mathcal{G}_{\mathfrak{f}^{0}}$ of a rank $n$
w-colored stranded graphs $\mathfrak{G}$.

For $n=2,3$, this method is not different from the previous one.

Case $n=4$. The $4$-bubbles of $\mathcal{G}_{\mathfrak{f}^{0}}$ are rank $3$
graphs. Each of them satisfies (4.8) and a sum over all these $4$-bubbles
gives

$\displaystyle
3\sum_{{\mathbf{b}}^{4}\in\mathcal{B}^{4}}(V_{{\mathbf{b}}^{4}}-E_{{\mathbf{b}}^{4}})+2\sum_{{\mathbf{b}}^{4}\in\mathcal{B}^{4}}F_{{\rm
int};{\mathbf{b}}^{4}}-(2+\alpha_{3})\sum_{{\mathbf{b}}^{4}\in\mathcal{B}^{4}}B^{3}_{{\mathbf{b}}^{4}}+3\alpha_{3}B^{4}\leq
0.$

From Lemma 4.1, one gets

$\displaystyle 3\times 4(V-E)+2\times 3F_{{\rm
int}}-2(2+\alpha_{3})B^{3}+3\alpha_{3}B^{4}\leq 0,\qquad-B^{4}+4\leq 0.$ (A.1)

Let us multiply the second relation in (A.1) by a positive rational number
$\alpha_{4}$ such that $-2(2+\alpha_{3})B^{3}+(3\alpha_{3}-\alpha_{4})B^{4}$
is an integer. We obtain $-\alpha_{4}B^{4}+4\alpha_{4}\leq 0$. Once again, we
add this relation to the first relation in (A.1) and obtain

$\displaystyle 3\times 4(V-E)+2\times 3F_{{\rm
int}}-2(2+\alpha_{3})B^{3}+(3\alpha_{3}-\alpha_{4})B^{4}\leq-4\alpha_{4}.$
(A.2)

As a remark, the relation (A.2) is different from the relation (3.16)
introduced in Section 3.

We can now find a general invariant by induction on $n$.

For all rank $n\geq 4$ w-colored graph, we have

$\displaystyle\frac{n!}{2}(V-E)+(n-1)!F_{{\rm int}}-(n-2)!(2+\alpha_{3})B^{3}$
$\displaystyle\qquad{}+\sum_{k=4}^{n}(n-k+1)!\big{[}(k-1)\alpha_{k-1}-\alpha_{k}\big{]}B^{k}\leq-n\alpha_{n}.$
(A.3)

The proof of equation (A.3) is by induction on $n$. Suppose that (A.3) holds
for all representative of a rank $n$ w-colored graph. Consider a
representative of a rank $n+1$ w-colored graph and let us prove that

$\displaystyle\frac{(n+1)!}{2}(V-E)+n!F_{{\rm int}}-(n-1)!(2+\alpha_{3})B^{3}$
$\displaystyle\qquad{}+\sum_{k=4}^{n+1}(n-k+2)!\big{[}(k-1)\alpha_{k-1}-\alpha_{k}\big{]}B^{k}\leq-(n+1)\alpha_{(n+1)}.$

The $(n+1)$-bubbles of $\mathcal{G}$ are rank $n$ graphs. Each of them
satisfies (A.3) and a summation on all the $(n+1)$-bubbles of $\mathcal{G}$
gives

$\displaystyle\frac{n!}{2}\sum_{{\mathbf{b}}^{n+1}\in\mathcal{B}^{n+1}}(V_{{\mathbf{b}}^{n+1}}-E_{{\mathbf{b}}^{n+1}})+(n-1)!F_{{\rm
int};{\mathbf{b}}^{n+1}}-(n-2)!(2+\alpha_{3})\sum_{{\mathbf{b}}^{n+1}\in\mathcal{B}^{n+1}}B^{3}_{{\mathbf{b}}^{n+1}}$
$\displaystyle\qquad{}+\sum_{k=4}^{n}(n-k+1)!\big{[}(k-1)\alpha_{k-1}-\alpha_{k}\big{]}\sum_{{\mathbf{b}}^{n+1}\in\mathcal{B}^{n+1}}B^{k}_{{\mathbf{b}}^{n+1}}+n\alpha_{n}B^{n+1}\leq
0.$

From Lemma 4.1, we have

$\displaystyle(n+1)\frac{n!}{2}(V-E)+n(n-1)!F_{{\rm
int}}-(n-1)(n-2)!(2+\alpha_{3})B^{3}$
$\displaystyle\qquad{}+\sum_{k=4}^{n}(n-k+2)(n-k+1)!\big{[}(k-1)\alpha_{k-1}-\alpha_{k}\big{]}B^{k}+n\alpha_{n}B^{n+1}\leq
0,$ $\displaystyle-B^{n+1}+n+1\leq 0.$ (A.4)

Let us multiply the second relation in (A.4) by a positive rational number
$\alpha_{n+1}$ such as
$-(n-1)(n-2)!(2+\alpha_{3})B^{3}+\sum\limits_{k=4}^{n}(n-k+2)(n-k+1)!\big{[}(k-1)\alpha_{k-1}-\alpha_{k}\big{]}B^{k}+(n\alpha_{n}-\alpha_{n+1})B^{n+1}$
is an integer. We obtain

$\displaystyle-\alpha_{n+1}B^{n+1}+(n+1)\alpha_{n+1}\leq 0.$ (A.5)

Adding (A.5) to the first relation in (A.4) ends the proof.

We could have introduced a polynomial invariant using the expression (A.4) and
also it will satisfy similar properties as established in Theorem 4.5.

### Acknowledgements

Numerous discussions with Joseph Ben Geloun and Mahouton N. Hounkonnou have
been hugely beneficial for this work and gratefully acknowledged. The author
acknowledges the support of Max-Planck Institute for Gravitational Physics,
Albert Einstein Institute, and the Association pour la Promotion Scientifique
de l’Afrique. The ICMPA is also in partnership with the Daniel Iagolnitzer
Foundation (DIF), France.

## References

  * [1] Avohou R.C., Ben Geloun J., Hounkonnou M.N., A polynomial invariant for rank 3 weakly-colored stranded graphs, arXiv:1301.1987.
  * [2] Avohou R.C., Ben Geloun J., Livine E.R., On terminal forms for topological polynomials for ribbon graphs: the $N$-petal flower, European J. Combin. 36 (2014), 348–366, arXiv:1212.5961.
  * [3] Ben Geloun J., Krajewski T., Magnen J., Rivasseau V., Linearized group field theory and power-counting theorems, Classical Quantum Gravity 27 (2010), 155012, 14 pages, arXiv:1002.3592.
  * [4] Ben Geloun J., Magnen J., Rivasseau V., Bosonic colored group field theory, Eur. Phys. J. C Part. Fields 70 (2010), 1119–1130, arXiv:0911.1719.
  * [5] Bollobás B., Modern graph theory, Graduate Texts in Mathematics, Vol. 184, Springer-Verlag, New York, 1998.
  * [6] Bollobás B., Riordan O., A polynomial invariant of graphs on orientable surfaces, Proc. London Math. Soc. 83 (2001), 513–531.
  * [7] Bollobás B., Riordan O., A polynomial of graphs on surfaces, Math. Ann. 323 (2002), 81–96.
  * [8] Ellis-Monaghan J.A., Moffatt I., Graphs on surfaces. Dualities, polynomials, and knots, Springer Briefs in Mathematics, Springer, New York, 2013.
  * [9] Gurau R., Lost in translation: topological singularities in group field theory, Classical Quantum Gravity 27 (2010), 235023, 20 pages, arXiv:1006.0714.
  * [10] Gurau R., Topological graph polynomials in colored group field theory, Ann. Henri Poincaré 11 (2010), 565–584, arXiv:0911.1945.
  * [11] Gurau R., Colored group field theory, Comm. Math. Phys. 304 (2011), 69–93, arXiv:0907.2582.
  * [12] Gurau R., The complete $1/N$ expansion of colored tensor models in arbitrary dimension, Ann. Henri Poincaré 13 (2012), 399–423, arXiv:1102.5759.
  * [13] Gurau R., Ryan J.P., Colored tensor models – a review, SIGMA 8 (2012), 020, 78 pages, arXiv:1109.4812.
  * [14] Krajewski T., Rivasseau V., Tanasă A., Wang Z., Topological graph polynomials and quantum field theory. I. Heat kernel theories, J. Noncommut. Geom. 4 (2010), 29–82, arXiv:0811.0186.
  * [15] Ryan J.P., Tensor models and embedded Riemann surfaces, Phys. Rev. D 85 (2012), 024010, 9 pages, arXiv:1104.5471.
  * [16] Tanasă A., Generalization of the Bollobás–Riordan polynomial for tensor graphs, J. Math. Phys. 52 (2011), 073514, 17 pages, arXiv:1012.1798.
  * [17] Tutte W.T., Graph theory, Encyclopedia of Mathematics and its Applications, Vol. 21, Addison-Wesley Publishing Company, Reading, MA, 1984.
  * [18] Wolsey L.A., Integer programming, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., New York, 1998.