Polynomial Invariants for Arbitrary Rank D Weakly-Colored Stranded Graphs
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...
Gespeichert in:
| Datum: | 2016 |
|---|---|
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | English |
| Veröffentlicht: |
Інститут математики НАН України
2016
|
| Schriftenreihe: | Symmetry, Integrability and Geometry: Methods and Applications |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/147726 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Polynomial Invariants for Arbitrary Rank D Weakly-Colored Stranded Graphs / R.C. Avohou // Symmetry, Integrability and Geometry: Methods and Applications. — 2016. — Т. 12. — Бібліогр.: 18 назв. — англ. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-147726 |
|---|---|
| record_format |
dspace |
| spelling |
nasplib_isofts_kiev_ua-123456789-1477262025-02-23T19:15:10Z Polynomial Invariants for Arbitrary Rank D Weakly-Colored Stranded Graphs Avohou, R.C. 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≥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. 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. 2016 Article Polynomial Invariants for Arbitrary Rank D Weakly-Colored Stranded Graphs / R.C. Avohou // Symmetry, Integrability and Geometry: Methods and Applications. — 2016. — Т. 12. — Бібліогр.: 18 назв. — англ. 1815-0659 2010 Mathematics Subject Classification: 05C10; 57M15 DOI:10.3842/SIGMA.2016.030 https://nasplib.isofts.kiev.ua/handle/123456789/147726 en Symmetry, Integrability and Geometry: Methods and Applications application/pdf Інститут математики НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
English |
| description |
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≥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. |
| format |
Article |
| author |
Avohou, R.C. |
| spellingShingle |
Avohou, R.C. Polynomial Invariants for Arbitrary Rank D Weakly-Colored Stranded Graphs Symmetry, Integrability and Geometry: Methods and Applications |
| author_facet |
Avohou, R.C. |
| author_sort |
Avohou, R.C. |
| title |
Polynomial Invariants for Arbitrary Rank D Weakly-Colored Stranded Graphs |
| title_short |
Polynomial Invariants for Arbitrary Rank D Weakly-Colored Stranded Graphs |
| title_full |
Polynomial Invariants for Arbitrary Rank D Weakly-Colored Stranded Graphs |
| title_fullStr |
Polynomial Invariants for Arbitrary Rank D Weakly-Colored Stranded Graphs |
| title_full_unstemmed |
Polynomial Invariants for Arbitrary Rank D Weakly-Colored Stranded Graphs |
| title_sort |
polynomial invariants for arbitrary rank d weakly-colored stranded graphs |
| publisher |
Інститут математики НАН України |
| publishDate |
2016 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/147726 |
| citation_txt |
Polynomial Invariants for Arbitrary Rank D Weakly-Colored Stranded Graphs / R.C. Avohou // Symmetry, Integrability and Geometry: Methods and Applications. — 2016. — Т. 12. — Бібліогр.: 18 назв. — англ. |
| series |
Symmetry, Integrability and Geometry: Methods and Applications |
| work_keys_str_mv |
AT avohourc polynomialinvariantsforarbitraryrankdweaklycoloredstrandedgraphs |
| first_indexed |
2025-11-24T15:15:47Z |
| last_indexed |
2025-11-24T15:15:47Z |
| _version_ |
1849685282990850048 |
| fulltext |
Symmetry, Integrability and Geometry: Methods and Applications SIGMA 12 (2016), 030, 23 pages
Polynomial Invariants for Arbitrary Rank D
Weakly-Colored Stranded Graphs
Remi Cocou AVOHOU
International Chair in Mathematical Physics and Applications, ICMPA-UNESCO Chair,
072BP50, Cotonou, Republic of Benin
E-mail: avohouremicocou@yahoo.fr
Received June 26, 2015, in final form March 14, 2016; Published online March 22, 2016
http://dx.doi.org/10.3842/SIGMA.2016.030
Abstract. 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 in-
troduced in arXiv:1301.1987. We successfully find in dimension D ≥ 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.
Key words: Tutte polynomial; Bollobás–Riordan polynomial; graph polynomial invariant;
colored graph; Ribbon graph; Euler characteristic
2010 Mathematics Subject Classification: 05C10; 57M15
1 Introduction
The polynomial invariant for 3D weakly-colored graphs introduced in [1] is a polynomial inva-
riant 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 coordina-
tion 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].
avohouremicocou@yahoo.fr
http://dx.doi.org/10.3842/SIGMA.2016.030
2 R.C. Avohou
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 S1 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 ≥ 4, we must expect a much richer
structure of the possible invariants.
In this paper, we discover several possibilities when we deal with D ≥ 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 αk ∈ Q+, k = 3, . . . , n. The modified Euler characteristic γn;α of a rank n ≥ 3
weakly-colored graph G is given by
γn;α =
n(n− 1)
2
(V − E) + (n− 1)Fint − (2 + (n− 2)α3)B
3
+
n∑
k=4
[
(k − 1)αk−1 − (n− k + 1)αk
]
Bk,
where V , E, Fint and Bk are respectively the number of vertices, edges, internal faces and
k-bubbles of 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.
Polynomial Invariants for Arbitrary Rank D Weakly-Colored Stranded Graphs 3
A graph G(V, E) is defined as a set of vertices V and of edges E together with an incidence
relation between them. G(V, 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:
(a) the chords may cross, but do not intersect;
(b) the chord end points are partitioned into sets called pre-edges with 0, 1, 2, . . . , or D ele-
ments; these points should lie on a single arc on the frontier with no other end points on
this arc;
(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:
(a′) the strands are not intersecting (but can cross without intersecting);
(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;
(c′) the number of strands is D.
Some illustrations of stranded vertices and edges with rank D = 4, 5, respectively, are pro-
vided 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 G is a graph G(V, E)
which admits:
(i) rank D stranded vertices;
(ii) rank at most D stranded edges;
(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 G is a rank D stranded graph such that:
4 R.C. Avohou
(i′) the vertices of G have a fixed coordinationD+1 and their pre-edges have a fixed cardinalD.
The merged point graph is KD+1 (or vertex graph);
(ii′) the edges of 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 correspon-
ding 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, . . . , D} to each of its edges such that no
two adjacent edges share the same color.
A bipartite graph is a graph whose set V of vertices is split into two disjoint sets, i.e.,
V = V+ ∪ V− with V+ ∩ V− = ∅, such that each edge connects a vertex v+ ∈ V+ and a vertex
v− ∈ V−.
Definition 2.4 (colored tensor graph [11, 13]). A rank D ≥ 1 colored tensor graph G is a graph
such that:
• G is (D + 1) colored and bipartite;
• 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 G be a rank D colored tensor graph.
– A 0-bubble is a vertex of G.
– A 1-bubble is an edge of G.
– For all p ≥ 2, a p-bubble of G with colors i1 < i2 < · · · < ip, p ≤ D, and ik ∈ {0, . . . , D}
is a connected rank p− 1 colored tensor graph the compact form of which is a connected
subgraph of the compact form of G made of edges of colors {i1, . . . , ip}.
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′ stranded vertex, with D′ ≥ 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
G(V, E , f0) or simply Gf0 , with f0 the set of the half-edges.
Polynomial Invariants for Arbitrary Rank D Weakly-Colored Stranded Graphs 5
Definition 2.7 (cut of an edge [14]). Let G(V, E , f0) be a rank D stranded graph and e a rank d
edge of Gf0 , 1 ≤ d ≤ D. The cut graph Gf0 ∨ e or the graph obtained from Gf0 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 ∈ {0, 1, . . . , 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(VA, EA, f0A) of a rank D stranded graph G(V, E , f0) by cutting a subset of
edges of Gf0 . A spanning c-subgraph A of Gf0 is defined as a c-subgraph A(VA, EA, f0A) of Gf0 with
all vertices and all additional half-edges of Gf0 . Hence EA ⊆ E and VA = V, f0A = f0 ∪ f0;1A (EA),
where f0;1A (EA) is the set of half-edges obtained by cutting all edges in E ′A (the set of edges
incident to the vertices of A and not contained in EA) and incident to vertices of A. We denote
it A b Gf0 .
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 Fint and Fext,
respectively. Hence, for a rankD half-edged colored tensor graph, the set F of faces is the disjoint
union Fint ∪ Fext. The notion of closed or open rank D half-edged colored tensor graph can be
reported accordingly if Fext = ∅ 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 Bint and Bext, respectively (see an illustration in Fig. 3).
1
2
3
0
Figure 3. An open rank 3 half-edged colored tensor graph; an open face highlighted in red; the bubbles
b012, b013 and b123 are open bubbles and b023 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].
6 R.C. Avohou
Definition 2.8 (boundary tensor graph [10]). The boundary graph ∂G(V∂ , E∂) of a rank D half-
edged colored tensor graph G(V, E , f0) is a graph obtained by inserting a vertex with degree D
at each additional stranded half-edge of Gf0 and taking the external faces of Gf0 as its edges.
Thus, |V∂ | = |f0| and E∂ = Fext.
The boundary of a closed rank D half-edged colored tensor graph is empty.
1 1
2
3
0
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 f1 and f2 where e is branched to its end vertex v (a loop
situation) or vertices v1,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 v1,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].
O A B C D
v1
v2
v1
v2
v3
v1
v2
v3
v4
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 v1 and v2 (B) and a 1-inner loop with three possible sectors v1, v2
and v3 (C) and a 0-inner loop with four possible sectors v1, v2, v3 and v4 (D).
Definition 2.9 (stranded edge contractions). Let G(V, E , f0) be a rank D half-edges stranded
graph. Let e be a rank D edge with pre-edges f1 and f2 and consider their neighbor families {f1;i}
and {f2;j}.
If e is a rank D p-inner edge but not a loop, the graph Gf0/e obtained by contracting e is
defined from Gf0 by removing the p inner faces generated by e, replacing e and its end vertices
v1,2 by p disjoint disc vertices and a new vertex v′. The new vertex v′ possesses all pre-edges
except for those of e and all stranded half-edges as they appear on v1 and v2, and chords obtained
by connecting directly {f1;i} and/or {f2;j} via the outer strands of f1 and f2.
If e is a rank D p-inner loop, the graph Gf0/e obtained by contracting e is defined from Gf0 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′ 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 f1 and/or f2.
If there is no outer strand left after removing the p inner faces of e then the vertex v′ is empty.
(Examples of rank 4 loop contraction is given in Fig. 6.)
Proposition 2.10. Let G(V, E , f0) be a rank D half-edged stranded graph and e be one of its
edges. The graph Gf0/e obtained by contraction of e admits a rank D half-edged stranded graph
structure.
Polynomial Invariants for Arbitrary Rank D Weakly-Colored Stranded Graphs 7
O A B C D
v1
v2
v1 v2
v3
v1 v2
v3 v4
Figure 6. p-inner loop contractions corresponding to O, A, B, C and D of Fig. 5, respectively.
Definition 2.11 (equivalence class of half-edged stranded graph). Let DGf0 be the subgraph in
a rank D half-edges stranded graph Gf0 defined by all of its trivial disc vertices and Gf0\DGf0
the rank D half-edges stranded graph obtained after removing DGf0 from Gf0 .
Two rank D half-edged stranded graphs G1,f0(G1) and G2,f0(G2) are “equivalent up to trivial
discs” if and only if G1,f0(G1)\DG1,f0(G1) = G2,f0(G2)\DG2,f0(G2) . We note G1,f0(G1) ∼ G2,f0(G2).
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 Gf0 (possibly with colors) yields a half-edged stranded graph G0f0
determined by the boundary ∂(Gf0) 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.
11
2
3
0
1 1
2
0
Figure 7. Contraction of an edge in a rank 3 half-edged colored tensor graph.
Proposition 2.14. Let G be a rank D w-colored graph, Gf0 be a representative of G and e one
of its edges.
G ∨ e denotes the equivalence class of Gf0 ∨ e called the cut graph G along e and is a rank D
w-colored graph.
G/e denotes the equivalence class of Gf0/e, called the contraction of 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 vi 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
8 R.C. Avohou
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 vi.
Equivalence class of stranded graphs. We now define the equivalence class of stranded
graphs by performing a sequence of operations corresponding to the following:
– 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);
– 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).
– any permutation of the pre-edge points within a pre-edge (see Fig. 9: v1 is obtained from
v0 after permuting the points 1 and 2 in the pre-edge {1, 2, 3} and renaming e1 → ẽ1).
– any move of the pre-edges on the frontier vertex (see Fig. 9: v2 is obtained from v0 after
moving a pre-edge {7, 8} on the vertex frontier and also its edge e3 remains incident to
that pre-edge at the same pre-edge points).
1
2 3
4
5
6
7 8
10
9
1'
2'
3'
9'
10'
7' 8'
4'
5'
6'
1
2
3
4
5
6
7 8
10
9
1'
2'
3'
7' 8'
4'
5'
6'
9'
10'
1
2 3
4
5
6
7
8
10
9
9'
10'
7'
8'1'
2'
3'
4'
5'
6'
v0
e1
e2
e3
e4
v1
ẽ1
e2
e3
e4
v2
e1
e2
e3
e4
Figure 9. Three vertices v0, v1 and v2 and their incident stranded edges corresponding to equivalent
configurations of stranded graphs, if the rest of each graph is kept fixed.
Consider a representative Gf0 of a rank 3 w-colored graph G(V, E , f0). We denote by V (Gf0),
E(Gf0), k(Gf0), f(Gf0), C∂(Gf0), E∂(Gf0) and F∂(Gf0), the number of vertices, edges, connected
Polynomial Invariants for Arbitrary Rank D Weakly-Colored Stranded Graphs 9
components, half-edges, connected components of the boundary graphs, edges of the boundary
graph and faces of the boundary graph of Gf0 . r(Gf0) = V (Gf0)− k(Gf0), n(Gf0) = E(Gf0)− r(Gf0)
the rank and nullity of Gf0 and Bint(Gf0), Bext(Gf0), the numbers of internal and external bubbles
in Gf0 .
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 Gf0 be any representative of G a rank 3 w-colored graph. Then
γ3(Gf0) = 3(V (Gf0)− E(Gf0)) + 2[Fint(Gf0)−Bint(Gf0)−Bext(Gf0)] ≤ 0.
Definition 2.16 (topological invariant for rank 3 w-colored graph). Let G(V, E , f0) be a rank 3
w-colored graph. The generalized topological invariant associated with G is given by the follo-
wing function associated with any of its representatives Gf0 (using the above notations)
TG(x, y, z, s, w, q, t) = TGf0 (x, y, z, s, w, q, t)
=
∑
AbGf0
(x− 1)r(Gf0 )−r(A)(y − 1)n(A)z5k(A)−γ3(A)sC∂(A)wF∂(A)qE∂(A)tf(A), (2.1)
with γ3(A) = 3(V (A)− E(A)) + 2[Fint(A)−Bint(A)−Bext(A)].
It is important to show that considering different representatives Gf0(G) and G′f0(G′) of 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 Gf0(G) and those of G′f0(G′). We can then map each
A b Gf0(G) onto A′ b G′f0(G′) such that A′ = (A\DGf0(G)) ∪DG′f0(G′) . We now verify that r(Gf0(G)),
r(A), n(A) and 5k(A)− (3V + 2Fint(A)) are independent of the representative. The exponents
Bint(A), Bext(A), C∂(A), f(A), E∂(A) and F∂(A) only depend on A\DGf0(G) = A′\DG′
f0(G′)
therefore are not dependent on the representative.
Proposition 2.17 (polynomial invariant). TG = TGf0 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 G be a rank 3 w-colored
graph. Then, for a regular edge e of any of the representative Gf0 of G, we have
TGf0 = TGf0∨e + TGf0/e.
For a bridge e, we have
TGf0∨e = z8s(wq)3t2TGf0/e and TGf0 =
[
(x− 1)z8s(wq)3t2 + 1
]
TGf0/e.
For a trivial p-inner loop e, p = 0, 1, 2, we have
TGf0 = TGf0∨e + (y − 1)z4p−7TGf0/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
TGf0
(
x, y, z, z−2, w, q, t
)
= T′Gf0
(x, y, z, w, q, t),
TGf0
(
x, y, z, z−2s2, s−1, s, s−1
)
= T′′Gf0
(x, y, z, s),
TGf0
(
x, y, z, z2z−2, z−1, z, z−1
)
= T′′′Gf0
(x, y, z).
10 R.C. Avohou
T′Gf0
, T′′Gf0
and T′′′Gf0
satisfy also the contraction/cut rule. Furthermore TGf0 maps to Tutte
polynomial by putting variables z = w = q = t = 1. The mapping of TGf0 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
T̃G(x, {βe}, {zi}i=1,2,3, s, w, q, t) = T̃Gf0 (x, {βe}, {zi}i=1,2,3, s, w, q, t)
=
∑
AbGf0
xr(A)
(∏
e∈A
βe
)
z
Fint(A)
1 z
Bint(A)
2 z
Bext(A)
3 sC∂(A)wF∂(A)qE∂(A)tf(A),
for {βe}e∈E labeling the edges of the graph Gf0 .
For all non-loop edge e, T obeys the rule T̃G = T̃G∨e + xβeT̃G/e, which can be shown using
standard techniques.
3 The polynomial invariant for 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 contrac-
tion/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 in-
variants of all 3-bubbles, the invariant of all 4-bubbles or may mix both to find a new invariant.
G1,f0(G1) b1
00̄ 00̄
b2
00̄
Figure 10. A 3-bubble b1 and a 4-bubble b2 of G1,f0(G1).
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 Gf0 of any rank 4 w-colored
graph: a d-bubble (closed or open) in Gf0 is denoted by bd, the set of d-bubbles is Bd, and its
cardinal Bd. Vbd , Ebd , Fint;bd and Bp
bd
are respectively the set of vertices, edges, internal faces
and p-bubbles (p ≤ d) of bd of cardinal Vbd , Ebd , Fint;bd and Bp
bd
respectively.
Lemma 3.1 (rank 4 trivial loop contraction). Let G a w-colored graph and Gf0 any of its
representative with boundary ∂Gf0, e be a trivial loop of Gf0, and G′f0 = Gf0/e the result of the
Polynomial Invariants for Arbitrary Rank D Weakly-Colored Stranded Graphs 11
contraction of Gf0 by e with boundary denoted by ∂G′f0. Let k denote the number of connected
components of Gf0, V its number of vertices, E its number of edges, Fint its number of faces, Bi
int
its number of closed i-bubbles and Bi
ext its number of open i-bubbles (i = 3, 4), C∂ the number of
connected component of ∂Gf0, f = V∂ its number of stranded half-edges, E∂ = Fext the number
of edges and F∂ the number of faces of ∂Gf0, and let k′, V ′, E′, F ′int, C
′
∂, B′iint, B
′i
ext(i = 3, 4),
C ′∂, f ′, E′∂, and F ′∂ denote the similar numbers for G′f0 and its boundary ∂G′f0.
If e is a 4-inner loop, then
k′ = k + 3, V ′ = V + 3, E′ = E − 1, F ′int = Fint,
C ′∂ = C∂ , f ′ = f, E′∂ = E∂ , F ′∂ = F∂ ,
B′iint = Bi
int − {i−14 , B′iext = Bi
ext, i = 3, 4. (3.1)
If e is a 3-inner loop, then
k′ = k + 3, V ′ = V + 3, E′ = E − 1, F ′int = Fint,
C ′∂ = C∂ , f ′ = f, E′∂ = E∂ , F ′∂ = F∂ ,
B′iint = Bi
int − {i−13 , B′iext = Bi
ext, i = 3, 4. (3.2)
If e is a trivial p-inner loop such that p = 0, 1, 2, then
k′ = k + 3, V ′ = V + 3, E′ = E − 1, F ′int = Fint,
C ′∂ = C∂ , f ′ = f, E′∂ = E∂ , F ′∂ = F∂ ,
B′3int +B′3ext = B3
int +B3
ext + βp, B′4int +B′4ext = B4
int +B4
ext + β′p, (3.3)
where βp = 6− 3p, β′p = 8− 3p and {pn = 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 ≤ 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 im-
mediately 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 Gf0 or G′f0 are the same
performing the first operation. If we remove the two inner strands, the 3-bubbles using the
outer strands in Gf0 get split in two parts in G′f0 . We then obtain one more bubble in G′f0 . This
compensates the one we have lost previously. Hence B′3int +B′3ext = B3
int +B3
ext.
12 R.C. Avohou
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′4int +B′4ext = B4
int +B4
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′3int +B′3ext = B3
int +B3
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′4int +B′4ext = B4
int +B4
ext + 5.
Case of the 0-inner loop. By implementing the above techniques we can prove also B′3int +
B′3ext = B3
int +B3
ext + 6 and B′4int +B′4ext = B4
int +B4
ext + 8. �
Lemma 3.2 (cut/contraction of special edges). Let Gf0 be a representative of G a rank 4 w-
colored graph and e an edge in Gf0.
If e is a bridge, we have
k(Gf0 ∨ e) = k(Gf0/e) + 1, V (Gf0 ∨ e) = V (Gf0/e) + 1,
E(Gf0 ∨ e) = E(Gf0/e), f(Gf0 ∨ e) = f(Gf0/e) + 2, (3.4)
Fint(Gf0 ∨ e) = Fint(Gf0/e), B3
int(Gf0 ∨ e) = B3
int(Gf0/e),
B4
int(Gf0 ∨ e) = B4
int(Gf0/e), (3.5)
C∂(Gf0 ∨ e) = C∂(Gf0/e) + 1, E∂(Gf0 ∨ e) = E∂(Gf0/e) + 4,
F∂(Gf0 ∨ e) = F∂(Gf0/e) + 6, (3.6)
B3
ext(Gf0 ∨ e) = B3
ext(Gf0/e) + 6, B4
ext(Gf0 ∨ e) = B4
ext(Gf0/e) + 4. (3.7)
If e is a trivial p-inner loop, p = 0, 1, 2, 3, we have
k(Gf0 ∨ e) = k(Gf0/e)− 3, V (Gf0 ∨ e) = V (Gf0/e)− 3, E(Gf0 ∨ e) = E(Gf0/e),
f(Gf0 ∨ e) = f(Gf0/e) + 2, (3.8)
Fint(Gf0 ∨ e) + C∂(Gf0 ∨ e) = Fint(Gf0/e) + C∂(Gf0/e)− 3,
E∂(Gf0 ∨ e) = E∂(Gf0/e) + 4, (3.9)
B3
int(Gf0 ∨ e) +B3
ext(Gf0 ∨ e) = B3
int(Gf0/e) +B3
ext(Gf0/e)− (6− 3p), (3.10)
B4
int(Gf0 ∨ e) +B4
ext(Gf0 ∨ e) = B4
int(Gf0/e) +B4
ext(Gf0/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 Fint(Gf0 ∨ e) = Fint(Gf0/e), B3
int(Gf0 ∨ e) = B3
int(Gf0/e)
and B4
int(Gf0 ∨ e) = B4
int(Gf0/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∂(Gf0 ∨ e) = C∂(Gf0/e) + 1, E∂(Gf0 ∨ e) = E∂(Gf0/e) + 4 (the cut of e
divides each external face into two different open strands) and F∂(Gf0 ∨ e) = F∂(Gf0/e) + 6
since C∂(Gf0/e) = C∂(Gf0), E∂(Gf0/e) = E∂(Gf0) and F∂(Gf0/e) = F∂(Gf0) which are direct from
Lemma 2.12. For the number of external bubbles, there are six 3-bubbles and four 4-bubbles
in Gf0 passing through the bridge. These bubbles are present in Gf0/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 fi in e made with outer strands. For
Polynomial Invariants for Arbitrary Rank D Weakly-Colored Stranded Graphs 13
p = 0, 1, 2, 3, we have fi, 1 ≤ i ≤ 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 fi’s.
Suppose that 4− p of fi’s are closed. Cutting e entails
Fint(Gf0 ∨ e) = Fint(Gf0)− 4, C∂(Gf0 ∨ e) = C∂(Gf0) + 1, E∂(Gf0 ∨ e) = E∂(Gf0) + 4,
B3(Gf0 ∨ e) = B3(Gf0), B4(Gf0 ∨ e) = B4(Gf0), F∂(Gf0 ∨ e) = F∂(Gf0) + 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 fi’s are closed and one is open. Cutting e implies
Fint(Gf0 ∨ e) = Fint(Gf0)− 3, C∂(Gf0 ∨ e) = C∂(Gf0), E∂(Gf0 ∨ e) = E∂(Gf0) + 4,
B3(Gf0 ∨ e) = B3(Gf0), B4(Gf0 ∨ e) = B4(Gf0), F∂(Gf0 ∨ e) = F∂(Gf0) + 3.
Suppose that 4− p− 2 of the fi’s are closed and two are open. Cutting e gives
Fint(Gf0 ∨ e) = Fint(Gf0)− 2, C∂(Gf0 ∨ e) = C∂(Gf0)− 1, E∂(Gf0 ∨ e) = E∂(Gf0) + 4,
B3(Gf0 ∨ e) = B3(Gf0), B4(Gf0 ∨ e) = B4(Gf0), F∂(Gf0 ∨ e) = F∂(Gf0).
Suppose that 4− p− 3 of the fi’s are closed and three are open. Cutting e gives
Fint(Gf0 ∨ e) = Fint(Gf0)− 1, C∂(Gf0 ∨ e) = C∂(Gf0)− 2, E∂(Gf0 ∨ e) = E∂(Gf0) + 4,
B3(Gf0 ∨ e) = B3(Gf0), B4(Gf0 ∨ e) = B4(Gf0), F∂(Gf0 ∨ e) = F∂(Gf0)− 3.
Note that this case does not apply for p = 2.
For p = 0 an additional situation applies: assume that all four fi’s are open. Cutting e gives
Fint(Gf0 ∨ e) = Fint(Gf0), C∂(Gf0 ∨ e) = C∂(Gf0)− 3, E∂(Gf0 ∨ e) = E∂(Gf0) + 4,
B3(Gf0 ∨ e) = B3(Gf0), B4(Gf0 ∨ e) = B4(Gf0), F∂(Gf0 ∨ e) = F∂(Gf0)− 6.
Lemma 3.1 relates the same numbers for Gf0/e and Gf0 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 G of a rank 4 w-colored graph G, we have∑
b3∈B3
Vb3 ≥ 6V,
∑
b3∈B3
Eb3 = 6E,
∑
b3∈B3
Fint;b3 = 3Fint. (3.12)
Moreover,∑
b4∈B4
B3
b4 = 2B3, 3B4 ≤ 2B3, B4 ≥ 4. (3.13)
Proof. Each vertex of Gf0 can be decomposed at least in 6 vertices (6 vertices is the minimum
given by the simplest vertex of the form G1,f0(G1) 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 Gf0 splits into 6 ribbon edges, and each internal face
of Gf0 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 b3 in Gf0 , b3 is made with 3 colors of Gf0 .
Since Gf0 is made with 5 colors, b3 is contained exactly in two 4-bubbles obtained by adding to
the three colors in b3 one of the two remaining colors of Gf0 . Hence, the first equation in (3.13)
follows. Using again the color prescription, each 4-bubble has at least three 3-bubbles, B3
b4 ≥ 3.
Summing each member of this relation on the set of 4-bubbles, we end the proof the second
equation in (3.13). �
14 R.C. Avohou
Now, we can introduce a parametrized invariant on this category of graph.
Proposition 3.4. Let Gf0 be any representative of a rank 4 w-colored graph G. There exist some
positive rational numbers α3 and α4 such that
γ4;(α3,α4)(Gf0) = 6(V − E) + 3Fint − 2(1 + α3)B
3 + (3α3 − α4)B
4
is a negative integer.
Proof. Consider a representative Gf0 of a rank 4 w-colored graph. The 3-bubbles of Gf0 are
connected rank 2 stranded graphs or ribbon graphs with half-edges. Consider a 3-bubble b3
of Gf0 and b̃3 its underline ribbon graph. Using the Euler formula, one has
Vb3 − Eb3 + Fint;b3 + C∂
(
b3
)
− 2 = −κ ≤ 0,
with κ the genus of b̃3. Hence,
Vb3 − Eb3 + Fint;b3 ≤ 2. (3.14)
A summation on all the 3-bubbles of Gf0 gives∑
b3∈B3
(Vb3 − Eb3) +
∑
b3∈B3
Fint;b3 − 2B3 ≤ 0.
From Lemma 3.3, we have
6(V − E) + 3Fint − 2B3 ≤ 0, 3B4 − 2B3 ≤ 0, −B4 + 4 ≤ 0. (3.15)
Consider some positive rational numbers α3 and α4 such that−2(1+α3)B
3+(3α3−α4)B
4 is an
integer. Multiplying the two last relations in (3.15) by α3 and α4, respectively, we obtain 3α3B
4−
2α3B
3 ≤ 0 and −α4B
4 + 4α4 ≤ 0. Combining these two last relations with the first relation
in (3.15), we obtain
6(V − E) + 3Fint − 2(1 + α3)B
3 + (3α3 − α4)B
4 + 4α4 ≤ 0, (3.16)
i.e., γ4;(α3,α4)(Gf0) is a negative integer. �
Clearly, the quantity γ4;(α3,α4)(·) is a negative integer for all non negative integers α3 and α4.
Furthermore, γ4;(α3,α4)(·) is still a negative integer if α3 and α4 are equal to specific positive
rational numbers.
We consider the combinatorial object 6(V −E)+3Fint−2(1+α3)B
3+(3α3−α4)B
4 as a gene-
rālized Euler characteristic. Indeed, fixing 3α3 −α4 > 0 (since 1 +α3 > 0), this integer is remi-
niscent of a weighted form of the Euler characteristic, if one considers the Bd’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 G(V, E , f0) be a rank 4
w-colored graph and α3 and α4 some positive rational numbers. The generalized topological
invariant associated with G is given by the following function associated with any of its repre-
sentatives G (using the above notations)
TG;(α3,α4)(x, y, z, s, w, q, t) = TGf0 ;(α3,α4)(x, y, z, s, w, q, t)
=
∑
AbGf0
(x− 1)r(G)−r(A)(y − 1)n(A)z9k(A)−γ4;(α3,α4)(A)sC∂(A)wF∂(A)qE∂(A)tf(A),
with γ4;(α3,α4)(A) = 6(V (A)−E(A)) + 3Fint(A)− 2(1 +α3)B
3(A) + (3α3−α4)B
4(A) a negative
integer.
Polynomial Invariants for Arbitrary Rank D Weakly-Colored Stranded Graphs 15
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 G be a rank 4 w-colored graph
and α3 and α4 some positive rational numbers. Then, for a regular edge e of any of the
representative Gf0 of G, we have
TGf0 ;(α3,α4) = TGf0∨e;(α3,α4) + TGf0/e;(α3,α4). (3.17)
For a bridge e, we have TGf0∨e;(α3,α4) = z15+4α4sw6q4t2TGf0/e;(α3,α4) and
TGf0 ;(α3,α4) = [(x− 1)z15+4α4sw6q4t2 + 1]TGf0/e;(α3,α4). (3.18)
For a trivial p-inner loop e, p = 0, 1, 2, 3, we have
TGf0 ;(α3,α4) = TGf0∨e;(α3,α4) + (y − 1)z−15+6p+3α3(4−p)+α4(3p−8)TGf0/e;(α3,α4). (3.19)
Proof. Let Gf0 be a representative of a rank 4 w-colored graph 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 Gf0 . From Proposition 2.14, we can define G ∨ e and G/e and
conclude that the resulting polynomials TGf0∨e;(α3,α4) and TGf0/e;(α3,α4) are independent on the
representative Gf0 ∨ e and Gf0/e, respectively.
Let us prove the equation (3.17). Consider an ordinary edge e of Gf0 , the set of spanning
c-subgraphs which do not contain e being the same as the set of spanning c-subgraphs of Gf0 ∨e,
the number of open and closed i-bubbles (i = 3, 4) on each subgraph is the same, it is direct
to get
∑
AbGf0 ;e/∈A
(·) = TGf0∨e;(α3,α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∑
AbGf0 ;e∈A
(·) = TGf0/e;(α3,α4).
We now concentrate on the bridge case and (3.18). Cutting a bridge yields, from the sum∑
AbGf0 ;e/∈A
, the product (x − 1)TGf0∨e;(α3,α4). Using the mapping between {A b Gf0 ; e ∈ A} and
{A b Gf0/e}, we obtain
∑
AbGf0 ;e∈A
(·) = TGf0/e;(α3,α4). We now investigate the relation between
TGf0∨e;(α3,α4) and TGf0/e;(α3,α4). There is a bijection between A b Gf0 ∨ e and A′ b Gf0/e where
each A and A′ are both uniquely related to some A0 b Gf0 as A = A0 ∨ e and A′ = A0/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
∑
AbGf0 ;e/∈A
(·) = TGf0∨e;(α3,α4) should be direct. Focus now on the second sum.
Consider a trivial p-inner loop e in Gf0 . Then e is a trivial p-inner loop in all A b Gf0
containing e. Contracting e generates p discs and 4− p non trivial vertices. Using Lemma 3.1,
the nullity is n(A) = n(A′) + 1 which ensures the factor y − 1, and the exponent of z becomes
9k(A)−
[
6(V (Gf0)− E(A)) + 3Fint(A)− 2(1 + α3)B
3(A) + (3α3 − α4)B
4(A)
]
= 9(k(A′)− 3)−
[
6[V (Gf0/e)− 3)− (E(A′) + 1)] + 3Fint(A
′)
− 2(1 + α3)(B
3(A′)− βp) + (3α3 − α4)(B
4(A′)− β′p)
]
= 9k(A′)−
[
6(V (Gf0)− E(A′)) + 3Fint(A
′)− 2(1 + α3)B
3(A′)
+ (3α3 − α4)B
4(A′)
]
− 15 + 6p+ 3α3(4− p) + α4(3p− 8),
16 R.C. Avohou
where βp = 6 − 3p, β′p = 8 − 3p, A and A′ refer to the subgraphs related by bijection
between spanning c-subgraphs of {A b Gf0 ; e ∈ A} and {A′ b Gf0/e}. Finally, one gets
(y − 1)z−15+6p+3α3(4−p)+α4(3p−8)TGf0/e;(α3,α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
∑
b3 C∂(b3).
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 G
denoted C∂(G) and the sum
∑
b3 C∂(b3). This certainly needs to be investigated in the context
of w-colored stranded graphs.
4 The polynomial invariant for 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 Gf0 of a rank n w-colored graph G. ∀ 3 ≤ p ≤ d ≤ n,∑
bd∈Bd
Vbd ≥ {d−1n V,
∑
bd∈Bd
Ebd = {d−1n E,
∑
bd∈Bd
Fint;bd = {d−2n−1Fint, (4.1)
∑
bd∈Bd
Bp
bd
= {d−pn−p+1B
p, {p−1d−1B
d ≤ {d−pn−p+1B
p. (4.2)
Proof. Consider a vertex v of a representative Gf0 of a rank n w-colored graph; v can be
decomposed, at least, in {d−1n (d ≤ n) vertices which could belong to a d-bubble (this number is
the minimum given by the simplest vertex of the graph G1,f0(G1) in Fig. 11). We then prove the
first relation in (4.1). From the coloring, each edge of Gf0 decomposes into {d−1n edges belonging
to a d-bubble. Each internal face of Gf0 is shared by {d−2n−1 d-bubbles. Thus we have the remaining
equations in (4.1).
Let us prove (4.2). Consider the d-bubbles in Gf0 . Each p-bubble bp (p ≤ d) in Gf0 , is a
p-bubble of {d−pn−p+1 d-bubbles of Gf0 . Indeed, consider a p-bubble in Gf0 , 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 {p−1d−1 p-bubbles, that
is Bp
bd
≥ {p−1d−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 Gf0 be any representative of a rank n ≥ 4 w-colored graph. There exist
some positive rational numbers α = {αk}k=3,...,n such that
γn;α(Gf0) =
n(n− 1)
2
(V − E) + (n− 1)Fint − (2 + (n− 2)α3)B
3
+
n∑
k=4
[
(k − 1)αk−1 − (n− k + 1)αk
]
Bk
is a negative integer.
Polynomial Invariants for Arbitrary Rank D Weakly-Colored Stranded Graphs 17
Proof. Consider a representative of a rank n w-colored graph. The 3-bubbles of Gf0 are ribbon
graphs. Each of them satisfies (3.14) and the sum over all the 3-bubbles of Gf0 gives∑
b3∈B3
(Vb3 − Eb3) +
∑
b3∈B3
Fint;b3 − 2B3 ≤ 0.
From Lemma 4.1, we have
n(n− 1)
2
(V − E) + (n− 1)Fint − 2B3 ≤ 0,
kBk+1 − (n− k + 1)Bk ≤ 0, ∀ k = 3, . . . , n− 1, −Bn + n ≤ 0. (4.3)
We multiply the second relation in (4.3) by a positive integer αk, k = 3, . . . , n− 1 and the last
relation by a positive integer αn such that the quantity
−(2 + (n− 2)α3)B
3 +
n∑
k=4
[
(k − 1)αk−1 − (n− k + 1)αk
]
Bk
is an integer. We obtain
kαkB
k+1 − (n− k + 1)αkB
k ≤ 0, ∀ k = 3, . . . , n− 1, −αnBn + nαn ≤ 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
n−1∑
k=3
[
kαkB
k+1 − (n− k + 1)αkB
k
]
− αnBn + nαn ≤ 0. (4.5)
Adding relation (4.5) to the first relation in (4.3) achieves the proof. �
One may wonder why the number B2 is not used in the above summation. B2 denotes
the number of 2-bubbles which is equal to Fint + C∂ . One notes that the quantity C∂ is not
used in the invariant, we have introduced a different variable for internal faces and boundary
components.
The number γn;α(·) is a generalized and weighted Euler characteristics. If one envisages to
have an alternating sum of positive integers, we must require the following conditions:
(k − 1)αk−1 − (n− k + 1)αk > 0 if k is even,
(k − 1)αk−1 − (n− k + 1)αk < 0 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 γn;α(·) can be prolonged to the lowest
ranks, n = 2 and n = 3. Consider a representative Gf0 of rank n w-colored stranded graphs G.
For n = 2, Gf0 is a half-edged ribbon graph. Consider the underlying ribbon graph 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 b G. In the case of half-edged ribbon graphs, the invariant is 2k(A)−(V (A)−E(A)+
Fint(A)) for each A b Gf0 . Since this quantity is always non negative, we have for a connected
graph Gf0 ,
V (Gf0)− E(Gf0) + Fint(Gf0) ≤ 2, (4.6)
where V , E and Fint are, respectively, the number of vertices, edges and internal faces. We set
γ2(Gf0) = V − E + Fint.
18 R.C. Avohou
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 Gf0 are connected rank 2 or ribbon graphs. Each of them
satisfies (4.6) and a summation on all the 3-bubbles of Gf0 gives∑
b3∈B3
(Vb3 − Eb3) +
∑
b3∈B3
Fint;b3 − 2B3 ≤ 0.
Using now Lemma 4.1, we have
3(V − E) + 2Fint − 2B3 ≤ 0, −B3 + 3 ≤ 0. (4.7)
Consider a positive rational number α3 such that (2 + α3)B
3 is an integer. We multiply the
second relation in (4.7) by α3 and obtain −α3B
3 + 3α3 ≤ 0. We add this relation to the first
relation in (4.7) and get
3(V − E) + 2Fint − (2 + α3)B
3 ≤ −3α3. (4.8)
We can then set
γ3;α3(G) = 3(V − E) + 2Fint − (2 + α3)B
3.
The expression γ3;0(·) 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 G(V, E , f0) be a rank n
w-colored graph and α = {αk}k=3,...,n some positive rational numbers. The generalized topo-
logical invariant associated with G is given by the following function associated with any of its
representatives Gf0 .
TG;α(x, y, z, s, w, q, t) = TGf0 ;α(x, y, z, s, w, q, t)
=
∑
AbGf0
(x− 1)r(Gf0 )−r(A)(y − 1)n(A)z
(n−1)(n+2)
2
k(A)−γn;α(A)sC∂(A)wF∂(A)qE∂(A)tf(A), (4.9)
with
γn;α(A) =
n(n− 1)
2
(V (A)− E(A)) + (n− 1)Fint(A)− (2 + (n− 2)α3)B
3(A)
+
n∑
k=4
[
(k − 1)αk−1 − (n− k + 1)αk
]
Bk(A)
a negative integer.
Remark that Lemma 3.3 finds an extension for any rank n w-colored graph.
G1,f0(G1)
00̄ 0̄
b
0
Figure 11. A 3-bubble b of the graph G1,f0(G1) made with n strands.
Let us introduce the following lemma used in the proof of our main result.
Polynomial Invariants for Arbitrary Rank D Weakly-Colored Stranded Graphs 19
Lemma 4.4 (cut/contraction of special edges). Let Gf0 be a representative of G a rank n w-
colored graph and e an edge in Gf0. Then, if e is a bridge in the above notations, we have
k(Gf0 ∨ e) = k(Gf0/e) + 1, V (Gf0 ∨ e) = V (Gf0/e) + 1, E(Gf0 ∨ e) = E(Gf0/e),
f(Gf0 ∨ e) = f(Gf0/e) + 2, (4.10)
Fint(Gf0 ∨ e) = Fint(Gf0/e), Bp
int(Gf0 ∨ e) = Bp
int(Gf0/e), ∀ 3 ≤ p ≤ n, (4.11)
C∂(Gf0 ∨ e) = C∂(Gf0/e) + 1, E∂(Gf0 ∨ e) = E∂(Gf0/e) + n,
F∂(Gf0 ∨ e) = F∂(Gf0/e) + {2n, (4.12)
Bp
ext(Gf0 ∨ e) = Bp
ext(Gf0/e) + {n−p+1
n , ∀ 3 ≤ p ≤ 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 Fint(Gf0 ∨ e) = Fint(Gf0/e), B
p
int(Gf0 ∨ e) = Bp
int(Gf0/e) ∀ 3 ≤ p ≤ 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∂(Gf0 ∨ e) = C∂(Gf0/e) + 1, E∂(Gf0 ∨ e) = E∂(Gf0/e) +n (the cut of e divides each external face
into two different external strands) and F∂(Gf0 ∨ e) = F∂(Gf0/e) + {2n since C∂(Gf0/e) = C∂(Gf0),
E∂(Gf0/e) = E∂(Gf0) and F∂(Gf0G/e) = F∂(Gf0) from Lemma 2.12. For the number of external
bubbles, there are {n−p+1
n p-bubbles in Gf0 passing through the bridge. These bubbles are clearly
in Gf0/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 G be a rank n w-colored graph
and and α = {αk}k=3,...,n some positive rational numbers. Then, for a regular edge e of any of
the representative Gf0 of G, we have
TGf0 ;α = TGf0∨e;α + TGf0/e;α. (4.14)
For a bridge e, we have
TGf0∨e;α = z(n−1)(n+1)+nαnsw
n(n−1)
2 qnt2TGf0/e;α
and
TGf0 ;α =
[
(x− 1)z(n−1)(n+1)+nαnsw
n(n−1)
2 qnt2 + 1
]
TGf0/e;α.
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 ≥ 4).
Proof. Consider a representative Gf0 of a rank n w-colored graph G. Following the proof
of (3.17) in Theorem 3.6 and replacing (3, 4)-bubbles by i-bubbles (i ≥ 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, α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.
20 R.C. Avohou
There are certainly some relations for trivial p-inner self-loops (p = 0, . . . , 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 T′Gf0 ;α
, T′′Gf0 ;α
and T′′′Gf0 ;α
also satisfy the
contraction/cut rule. Furthermore TGf0 ;α 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 Gf0 of rank n w-colored graph G. In the polynomial invariant
introduced in (4.9), we can add other variables yi (i = 0, . . . , n) for the number of i-bubbles of
the boundary graph ∂Gf0 . An extended form of the polynomial introduced in (4.9) is given by
TG;α(x, y, z, {yi}i=0,...,n) = TGf0 ;α(x, y, z, {yi}i=0,...,n)
=
∑
AbGf0
(x− 1)r(Gf0 )−r(A)(y − 1)n(A)z
(n−1)(n+2)
2
k(A)−γn;α(A)
(
n∏
i=0
y
Bi(∂(A))
i
)
. (4.15)
Definition 4.6 (multivariate form). The multivariate form associated with (4.15) is defined by:
T̃G
(
x, {βe}, {zi}i=2,...,n−1, {yi}i=0,...,n, {qi}i=3,...,n
)
= T̃Gf0
(
x, {βe}, {zi}i=2,...,n−1, {yi}i=0,...,n, {qi}i=3,...,n
)
=
∑
AbGf0
xr(A)
(∏
e∈A
βe
)(
n∏
i=2
z
Biint(A)
i
)(
n∏
i=3
z
Biext(A)
i
)(
n∏
i=0
y
Bi(∂(A))
i
)
, (4.16)
for {βe}e∈E labeling the edges of the graph Gf0 .
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
T̃G = T̃G∨e + xβeT̃G/e.
5 Example
Consider the graph G of Fig. 12. Let us prove that the polynomial invariant TG;(α3,α4) satisfies
the recurrence relation.
e11 1̄0 0̄
2 2̄
3 3̄
4 4̄
1 1̄0 0̄
2 2̄
3 3̄
4
4̄
1 1̄
0 0̄
4 4̄
3 3̄
e1
e1
e2
Gf0 ∨ e2 Gf0/e2
Gf0
Figure 12. A representative Gf0 of a w-colored graph, the cut graph Gf0 ∨ e2 and the contracted graph
Gf0/e2 with respect to e2.
Polynomial Invariants for Arbitrary Rank D Weakly-Colored Stranded Graphs 21
Using the spanning c-subgraph summation, we get
TGf0 ;(α3,α4)(x, y, z, s, w, q, t) = (y − 1)z28+7α3+5α4sw11q12t6 + 2z31+10α3+6α4sw14q16t8
+ (x− 1)z37+10α3+10α4s2w20q20t10.
We must check that
TGf0 ;(α3,α4) = TGf0∨e2;(α3,α4) + TGf0/e2;(α3,α4).
This is the case, since
TGf0∨e2;(α3,α4)(x, y, z, s, w, q, t) = z31+10α3+6α4sw14q16t8
+ (x− 1)z37+10α3+10α4s2w20q20t10,
and
TGf0/e2;(α3,α4)(x, y, z, s, w, q, t) = (y − 1)z28+7α3+5α4sw11q12t6 + z31+10α3+6α4sw14q16t8.
The different expressions of γ4;(α3,α4)(·) in the above polynomial are −19− 7α3− 5α4, −22−
10α3 − 6α4 and −28− 10α3 − 10α4. Putting α3 = 1
2 and α4 = 3
2 , each of these expressions is a
negative integer.
As a final remark, the parameters αi which label the γn invariant are positive rational num-
bers. We may ask a unique prescription to determine those parameters to get a unique γ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 α3 = 1/2 and α4 = 3/2 in the above
example before getting γn as an integer for all subgraphs. Thus, for each graph, we claim that
we have 2E 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(2E−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 α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
min
{
Bx ≤ 0, x ∈ Zn+1
}
,
where B = (B0, . . . , Bn) ∈ Nn+1 and x = (a0α0, . . . , anαn) with ai the binomial coefficient
appearing in γn. Thus studying this kind of problem could be interesting to fix our parameters
and uniquely determine the γn invariant. This deserves to be elucidated.
A Determination of the invariant by the sum of invariants
of consecutive bubbles
Consider a representative Gf0 of a rank n w-colored stranded graphs G.
For n = 2, 3, this method is not different from the previous one.
22 R.C. Avohou
Case n = 4. The 4-bubbles of Gf0 are rank 3 graphs. Each of them satisfies (4.8) and a sum
over all these 4-bubbles gives
3
∑
b4∈B4
(Vb4 − Eb4) + 2
∑
b4∈B4
Fint;b4 − (2 + α3)
∑
b4∈B4
B3
b4 + 3α3B
4 ≤ 0.
From Lemma 4.1, one gets
3× 4(V − E) + 2× 3Fint − 2(2 + α3)B
3 + 3α3B
4 ≤ 0, −B4 + 4 ≤ 0. (A.1)
Let us multiply the second relation in (A.1) by a positive rational number α4 such that −2(2 +
α3)B
3 + (3α3 − α4)B
4 is an integer. We obtain −α4B
4 + 4α4 ≤ 0. Once again, we add this
relation to the first relation in (A.1) and obtain
3× 4(V − E) + 2× 3Fint − 2(2 + α3)B
3 + (3α3 − α4)B
4 ≤ −4α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 ≥ 4 w-colored graph, we have
n!
2
(V − E) + (n− 1)!Fint − (n− 2)!(2 + α3)B
3
+
n∑
k=4
(n− k + 1)!
[
(k − 1)αk−1 − αk
]
Bk ≤ −nα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
(n+ 1)!
2
(V − E) + n!Fint − (n− 1)!(2 + α3)B
3
+
n+1∑
k=4
(n− k + 2)!
[
(k − 1)αk−1 − αk
]
Bk ≤ −(n+ 1)α(n+1).
The (n+ 1)-bubbles of G are rank n graphs. Each of them satisfies (A.3) and a summation on
all the (n+ 1)-bubbles of G gives
n!
2
∑
bn+1∈Bn+1
(Vbn+1 − Ebn+1) + (n− 1)!Fint;bn+1 − (n− 2)!(2 + α3)
∑
bn+1∈Bn+1
B3
bn+1
+
n∑
k=4
(n− k + 1)!
[
(k − 1)αk−1 − αk
] ∑
bn+1∈Bn+1
Bk
bn+1 + nαnB
n+1 ≤ 0.
From Lemma 4.1, we have
(n+ 1)
n!
2
(V − E) + n(n− 1)!Fint − (n− 1)(n− 2)!(2 + α3)B
3
+
n∑
k=4
(n− k + 2)(n− k + 1)!
[
(k − 1)αk−1 − αk
]
Bk + nαnB
n+1 ≤ 0,
−Bn+1 + n+ 1 ≤ 0. (A.4)
Polynomial Invariants for Arbitrary Rank D Weakly-Colored Stranded Graphs 23
Let us multiply the second relation in (A.4) by a positive rational number αn+1 such as
−(n−1)(n−2)!(2+α3)B
3 +
n∑
k=4
(n−k+2)(n−k+1)!
[
(k−1)αk−1−αk
]
Bk+(nαn−αn+1)B
n+1
is an integer. We obtain
−αn+1B
n+1 + (n+ 1)αn+1 ≤ 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.
http://arxiv.org/abs/1301.1987
http://dx.doi.org/10.1016/j.ejc.2013.08.001
http://arxiv.org/abs/1212.5961
http://dx.doi.org/10.1088/0264-9381/27/15/155012
http://arxiv.org/abs/1002.3592
http://dx.doi.org/10.1140/epjc/s10052-010-1487-z
http://arxiv.org/abs/0911.1719
http://dx.doi.org/10.1007/978-1-4612-0619-4
http://dx.doi.org/10.1112/plms/83.3.513
http://dx.doi.org/10.1007/s002080100297
http://dx.doi.org/10.1007/978-1-4614-6971-1
http://dx.doi.org/10.1007/978-1-4614-6971-1
http://dx.doi.org/10.1088/0264-9381/27/23/235023
http://arxiv.org/abs/1006.0714
http://dx.doi.org/10.1007/s00023-010-0035-6
http://arxiv.org/abs/0911.1945
http://dx.doi.org/10.1007/s00220-011-1226-9
http://arxiv.org/abs/0907.2582
http://dx.doi.org/10.1007/s00023-011-0118-z
http://dx.doi.org/10.1007/s00023-011-0118-z
http://arxiv.org/abs/1102.5759
http://dx.doi.org/10.3842/SIGMA.2012.020
http://arxiv.org/abs/1109.4812
http://dx.doi.org/10.4171/JNCG/49
http://arxiv.org/abs/0811.0186
http://dx.doi.org/10.1103/PhysRevD.85.024010
http://arxiv.org/abs/1104.5471
http://dx.doi.org/10.1063/1.3605312
http://arxiv.org/abs/1012.1798
1 Introduction
2 Weakly-colored graphs and the rank 3 polynomial invariant
3 The polynomial invariant for 4D w-colored graphs
4 The polynomial invariant for nD w-colored graphs
5 Example
A Determination of the invariant by the sum of invariants of consecutive bubbles
References
|