KNOT THEORY FOR SELF-INDEXED GRAPHS

MATÍAS GRAÑA AND VLADIMIR TURAEV

Abstract. We introduce and study so-called self-indexed graphs. These are (oriented) finite graphs endowed with a map from the set of edges to the set of vertices. Such graphs naturally arise from classical knot and link diagrams. In fact, the graphs resulting from link diagrams have an additional structure, an integral flow. We call a self-indexed graph with integral flow a comte. The analogy with links allows us to define transformations of comtes generalizing the Reidemeister moves on link diagrams. We show that many invariants of links can be generalized to comtes, most notably the linking number, the Alexander polynomials, the link group, etc. We also discuss finite type invariants and quandle cocycle invariants of comtes.

1. Introduction

1.1. Outline. By a self-indexed graph, we mean a finite oriented graph provided with a map from the set of edges to the set of vertices. In this paper we show that the study of such graphs is closely related to the study of knots and links in Euclidean 3-space ℝ^{3}. This connection allows us to view self-indexed graphs as a generalization of links and to apply to them a number of well understood tools of knot theory.

Knot theory studies smooth embeddings of n = 1, 2, ... copies of the circle S^{1} into ℝ^{3}. Two such embeddings are isotopic if they can be smoothly deformed into each other in the class of embeddings. An isotopy class of such embeddings is called an oriented n-component link in ℝ^{3}. (The orientation of the link is determined by the counterclockwise orientation on S^{1}.) One-component links are called knots. Knots and links are usually presented by their generic projections to the plane ℝ^{2} where one should keep track of under/overcrossings and the circle orientations, cf. Figure 5. Such projections are called oriented link diagrams. We refer to the monographs [BZ, R] for more on knots and links.

We show in this paper that every oriented link diagram gives rise to a self-indexed graph with an integral flow. Recall that an integral flow on an oriented graph is an assignment of an integer to each arrow such that the algebraic sum of the integers incident to any vertex is zero. We call a self-indexed graph with a flow a comte. The word comte is the French word for count (nobleman). We use it in our context in analogy with Russian and German, where the word graph has two meanings: the standard one used in the graph theory and a count (nobleman). Since count has a precise meaning in mathematics, we use its French translation.

We introduce certain transformations of comtes generalizing the Reidemeister moves on link diagrams. Since every two diagrams of an oriented link are related by the Reidemeister moves, we conclude that every oriented link in ℝ^{3} determines a comte, at least up to our moves. As we shall see, this mapping from the set of links to the set of comtes (modulo the moves) is essentially injective. However, the class of comtes is much wider than the class of links. The theory of comtes can be viewed as a larger, combinatorial paradigm for knot theory.

We shall show that many standard notions of knot theory extend to comtes. This inlcudes the link group, the link quandle, the state sum quandle cocycle invariants, the linking number, the Alexander polynomials, etc. The case of quandle cocycle invariants of comtes is treated in more detail. We generalize quandles to so-called self-indexed q-graphs, define a homology theory for them, and use it to present state sums on comtes as a sort of double integral. These state sums are invariant under some of our moves, and they are invariant under all of the moves if the q-graph comes from a quandle. Indeed, this paper began by the observation that quandle cocycle invariants could be defined for self-indexed graphs with flows.

We also briefly discuss finite type invariants of comtes and show that a virtual link in the sense of Kauffman [K] gives rise to a comte. (However, the resulting map from the set of virtual links to the set of comtes is not injective.)

1.2. Definitions. By a graph we mean a 4-tuple (V, E, s, t), where V and E are finite sets (resp. of vertices and arrows (=edges)), and s, t : E → V are maps (the source and the target). Note that we allow loops (i.e., edges e with s(e) = t(e)) and multiple edges (i.e., edges with the same endpoints). Each graph gives rise to a finite 1-dimensional cellular complex, called its topological realization. Its 0-cells are the vertices of the graph and its 1-cells are numerated by the arrows of the graph so that the 1-cell corresponding to an arrow e is an oriented interval leading from s(e) to t(e). As usual, we shall pictorially present graphs by their topological realizations.

The work of M.G. was supported by CONICET (Argentina).

A graph (V, E, s, t) endowed with a map ℓ : E → V is said to be self-indexed. Note that we impose no conditions on the map ℓ, for instance one can take ℓ = s or ℓ = t, or let ℓ be a constant map. The value of ℓ on an edge is called the label of this edge. We draw edges of a self-indexed graph as on the left-hand side of the following figure, where a stands for the label of the edge.

[figure: b; c; a; b; c; a, I]

An (integral) flow on a graph (V, E, s, t) is a map I : E → ℤ such that for each vertex v ∈ V, the sum of outgoing flows is equal to the sum of incoming flows:

(1.2.1)  ∑_{e:s(e)=v} I(e) = ∑_{e:t(e)=v} I(e).

A self-indexed graph with a flow is called a comte. We draw flows as on the right-hand side of the previous figure, where I stands for the value of the flow on the edge.

Given two self-indexed graphs G = (V, E, s, t, ℓ) and G′ = (V′, E′, s′, t′, ℓ′), a homomorphism f : G → G′ is a pair of maps f_{V} : V → V′, f_{E} : E → E′ commuting with s, t, ℓ. More precisely, the following diagrams should commute:

E ⟶^{f_{E}} E′  E ⟶^{f_{E}} E′  E ⟶^{f_{E}} E′
s↓  ↓_{s′}  ^{t}↓  ↓_{t′}  ^{ℓ}↓  ↓_{ℓ′}
V ⟶^{f_{V}} V′,  V ⟶^{f_{V}} V′,  V ⟶^{f_{V}} V′.

Clearly, self-indexed graphs and their homomorphisms form a category.

1.3. Moves on self-indexed graphs and comtes. We define several transformations of comtes also called moves. In all these transformations vertices may coincide, but arrows referred to (and drawn) as different must be different.

R0 A vertex of valence 1 which is not the label of any arrow can be deleted together with the incident

arrow, see Figure 0. Observe that necessarily the flow of the arrow is 0. R1 An arrow labeled by its source or its target can be contracted, see Figure 1. The source and target are identified. An arrow pointing from a vertex to itself and labeled by this vertex can be deleted. R2 Two arrows with the same label and the same source (resp. target) can be replaced by one arrow as in Figure 2(a) (resp. Figure 2(b)). The targets (resp. sources) of the arrows are identified and the flows are added.

R3 In presence of an arrow with label a, source b and target t, any of the four arrows in a square with

sides labeled b, a, t, a can be removed, see Figure 3. The flow is modified as in the figure. We say that two comtes are isotopic if they can be related by a sequence of isomorphisms, moves R0–R3

and the inverse moves. By abuse of language, we shall use the same word comte for an isotopy class of comtes.

We can consider the same transformations for self-indexed graphs, just by ignoring the flows. We say that two self-indexed graphs are isotopic if they can be related by a sequence of isomorphisms, moves R0–R3 (with flows forgotten) and the inverse moves.

1.4. Comte of a link. We now explain how every oriented link diagram in ℝ^{2} gives rise to a comte. Viewed as a subset of the plane, the diagram consists of a finite number of disjoint embedded oriented arcs. The set V of these arcs will be the set of vertices of our comte. Each crossing of the diagram gives rise to three arcs a, b, c ∈ V: the arc a contains the overpass, the arc b contains the underpass lying on the right of a, and c contains the underpass lying on the left of a, see Figure 4. Consider an arrow from b to c labeled by a with a flow +1 if the crossing is positive and −1 if the crossing is negative. (Note that the direction of this arrow from b to c is induced by the orientation of the arcs b, c if the crossing is positive, and is reversed for

A comte G without arrows labeled by b

t, 0

a b ⇌ a G

A comte G without arrows labeled by b

t, 0

a b ⇌ a G

Figure 0. Move R0

a b

a, I ⇌

a = b

⇌
a b

b, I

a a, I ⇌

a

Figure 1. Move R1

[figure: a; s; t; b, I_{1}; b, I_{2}; ⇌; a; s = t; b, I_{1} + I_{2}]

Figure 2(a). Move R2(a)

[figure: a; t; s; b, I_{1}; b, I_{2}; ⇌; a; s = t; b, I_{1} + I_{2}]

Figure 2(b). Move R2(b)

a negative crossing.) The set V with such arrows corresponding to all crossings of the diagram is the comte determined by the diagram.

We draw in Figure 5 the comtes associated to several simple knot and link diagrams. As an exercise the reader may verify that the topological realization of the comte determined by a diagram of an n-component link is a disjoint union of n circles.

It is easy to observe that two oriented link diagrams in ℝ^{2} presenting isotopic oriented links in ℝ^{3} give rise to isotopic comtes. Indeed, such diagrams are related by a finite sequence of oriented Reidemeister moves. We need only to prove that under these moves the comte changes by a sequence of our moves R0–R3 and the inverse moves. The action of the first (resp. second, third) Reidemeister move on the comte can be achieved with R1 (resp. R2 + R0, R3 + R0). We check it for the second Reidemeister move with both strands oriented in the same direction in Fig. 6 and leave the other cases to the reader. Thus the isotopy class of the comte derived from an oriented link diagram depends only on the (isotopy class of the) link itself. In this way we obtain a map from the set of (isotopy classes of) oriented links in ℝ^{3} to the set of isotopy classes of comtes. Forgetting the flows, we obtain a map from the set of oriented links in ℝ^{3} to the set of isotopy classes of self-indexed graphs.

[figure: b; t; a, I_{0}; c; u; s; r; t, I_{2}; a, I_{1}; b, I_{3}; a, I_{4}; ⇌; b; t; a, I_{0}; c; u; s; r; t, I_{2} + I_{4}; a, I_{1} + I_{4}; b, I_{3} − I_{4}; ⇌; b; t; a, I_{0}; c; u; s; r; t, I_{2} + I_{3}; a, I_{1} + I_{3}; a, I_{4} − I_{3}; ⇌; b; t; a, I_{0}; c; u; s; r; t, I_{2} − I_{1}; a, I_{4} + I_{1}; b, I_{3} + I_{1}; ⇌; b; t; a, I_{0}; c; u; s; r; a, I_{4} + I_{2}; a, I_{1} − I_{2}; b, I_{3} + I_{2}]

Figure 3. Move R3

b c

a, 1

a b c

;

b c

a, −1

c a

b

Figure 4. How to pass from a link to a comte

Remark 1.4.1. The move R3 can be split as a composition of moves R3(a) and R3(b) below. It is sometimes easier to work with R3(a) and R3(b) rather than with R3.

R3(a) In presence of an arrow with label a, source b and target t, we remove any of the four arrows, with a 0 flow, in a square with sides labeled b, a, t, a, see Figure 7(3a) (where the relation is depicted for one of the sides; analogous figures should be drawn for the other three sides).

[figure: b; a; c; ↭; c; b, −1; b; a, −1; a; c, −1; b; a; c; ↭; c; b, 1; b; a, 1; a; c, 1; a; b; c; d; ↭; a; c, 1; d; b, −1; c; a, 1; b; d, −1; b; a; ↭; a; b, −1; b; a, −1; a; b; c; d; e; f; ↭; a; b; e, −1; f, 1; d; c; b, −1; a, 1; f; e; c, −1; d, 1]

Figure 5. Several link diagrams and their comtes

[figure: a; b; c; d; ⇌; a; b=d; ↭; c; d; a, −1; b; a, 1; ⇌; c; b=d; a, 0; ⇌; b=d]

Figure 6. Second Reidemeister move ↭ R2+R0

R3(b) In presence of an arrow with label a, source b and target t, we shift the flow in a square with sides labeled b, a, t, a, see Figure 7(3b).

[figure: b; t; a, I_{0}; c; u; s; r; t, I_{2}; a, I_{1}; b, I_{3}; a, 0; ⇌; b; t; a, I_{0}; c; u; s; r; t, I_{2}; a, I_{1}; b, I_{3}]

Figure 7(3a). Relation R3(a) for one of the sides

2. Isotopy invariants of self-indexed graphs and comtes

In this section we generalize a number of well-known invariants of links to self-indexed graphs and comtes. We begin with invariants which do not depend on flows.

[figure: b; t; a, I_{0}; c; u; s; r; t, I_{2}; a, I_{1}; b, I_{3}; a, I_{4}; ⇌; b; t; a, I_{0}; c; u; s; r; t, I_{2} + J; a, I_{1} + J; b, I_{3} − J; a, I_{4} − J]

Figure 7(3b). Relation R3(b)

2.1. The group of a self-indexed graph. Let G = (V, E, s, t, ℓ) be a self-indexed graph. We define the group of G to be the group generated by elements of V modulo the relations ab = ca whenever there is an

arrow b⟶^{a}c in G.

Lemma 2.1.1. The group of G is preserved under the moves R0–R3 (with flows forgotten).

Proof. For R0, simply notice that the group for the LHS has one more generator, b, and one more relation, b = tat^{−1}. Hence one can drop b from the set of generators, as on the RHS. The arrows in R1 give relations of the type aa = ba, i.e., a = b, and therefore b can be dropped from the set of generators. The loop in the second line in Fig. 1 contributes the relation aa = aa which is tautological. In move R2(a) we have on both sides the same relations s = bab^{−1} = t. Move R2(b) is analogous. In move R3, on the first line of RHS of Fig. 7(3a) we have u = aca^{−1}, s = tut^{−1}, r = bcb^{−1}, t = aba^{−1}. Hence

s = taca^{−1}t^{−1} = aba^{−1}aca^{−1}ab^{−1}a^{−1} = abcb^{−1}a^{−1} = ara^{−1},

which is precisely the relation on the LHS determined by the forth arrow of the square. For the other sides of the square the computations are analogous. □

Abelianizing the group of a self-indexed graph G = (V, E, s, t, ℓ) we obtain a free abelian group with (free) generators bijectively corresponding to the components of G. Here by components of G we mean the equivalence classes of the equivalence relation in V generated by b ∼ c whenever there is an arrow b⟶c in G. It is clear that the components of G bijectively correspond to the components of its topological realization |G|. Thus, the abelianized group of G is nothing but H_{0}(|G|; ℤ). Clearly, the number of components of G is invariant under the moves R0–R3.

Note finally that the group of a link in ℝ^{3} is isomorphic to the group of its self-indexed graph.

2.2. The quandle of a self-indexed graph. We show that each self-indexed graph gives rise to a quandle. We first recall the relevant definitions.

A rack is a pair (X, ▷) where X is a set and ▷ : X × X → X is a binary operation such that • the function x▷? : X → X is bijective for all x ∈ X, and

• x ▷ (y ▷ z) = (x ▷ y) ▷ (x ▷ z) for all x, y, z ∈ X. A rack (X, ▷) is a quandle if

• x ▷ x = x for all x ∈ X. For a set V, the free quandle of V coincides with the union of the conjugacy classes of elements of V inside

the free group generated by V. The functor which assigns the free quandle to a set is left adjoint to the forgetful functor from quandles to sets.

The quandle of a self-indexed graph G = (V, E, s, t, ℓ) is the free quandle of V quotiented out by the relations a ▷ b = c for each arrow b⟶^{a}c in G.

Lemma 2.2.1. The quandle of G is preserved under the moves R0–R3.

Proof. The same as that for the group of G. □

The quandle of the self-indexed graph of an oriented link coincides with the quandle of the link, as defined in [J] and [Ma].

As an application of quandles, we show that the self-indexed graph is an almost complete invariant of an oriented link. For an oriented link L, we denote by \overline{L} its mirror image with reversed orientation on all components. It is easy to see that the self-indexed graphs of L and \overline{L} coincide. (It suffices to present L by a diagram and to consider its mirror image with respect to a plane orthogonal to the plane of the diagram.) This shows that the self-indexed graph can not distinguish L from \overline{L}. However, this is the only source of links with the same self-indexed graphs. To state the relevant result, we call two oriented links L_{1}, L_{2} weakly isotopic if L_{1} is isotopic to L_{2} or to \overline{L}_{2}. A link is splittable if it is a disjoint union of two non-empty links. For instance, all knots are non-splittable.

Corollary 2.2.2. If two non-splittable oriented links L_{1}, L_{2} in ℝ^{3} have isotopic self-indexed graphs, then L_{1}, L_{2} are weakly isotopic.

Proof. Suppose first that L_{1}, L_{2} are knots. Since the quandles of L_{1}, L_{2} are determined by their self-indexed graphs, these quandles are isomorphic to each other. But the quandle is a full invariant of oriented knots up to weak isotopy (cf. [J], [Ma]). Therefore L_{1} is weakly isotopic to L_{2}. The same argument works for non-splittable links. □

We don’t know whether the comte always distinguishes L from \overline{L}. Certain invariants of comtes suggest that this may be the case, cf. 2.5.1 below. Note also that a link is splittable if and only if its self-indexed graph is a disjoint union of two non-empty self-indexed graphs.

2.3. The Alexander module and Alexander polynomials of a self-indexed graph. Any finitely generated group π gives rise to a ℤ[H_{1}(π)]-module called its Alexander module. It can be computed by the Fox calculus from any presentation of π by generators and relations. This module gives rise to a sequence of elements of the group ring ℤ[H_{1}(π)/Tors] called the Alexander polynomials of π. In particular, the group of a self-indexed graph yields a module and a sequence of Alexander polynomials. We give here a direct definition of these module and polynomials.

Let G = (V, E, s, t, ℓ) be a self-indexed graph. Denote by Λ the ring of integer Laurent polynomials ℤ[t, t^{−1}]. The Alexander module A(G) of G is the Λ-module generated by V modulo the relations c = tb + (1 − t)a for each arrow b⟶^{a}c ∈ G.

Lemma 2.3.1. The module A(G) is invariant under the moves R0–R3 (with flows forgotten) on G.

Proof. Let us check, for instance, that the Alexander module is invariant under R3 (we do it for one of the sides, the other three being analogous). On the RHS of Figure 7(3a) we have the relations

r = tc + (1 − t)b, u = tc + (1 − t)a, s = tu + (1 − t)t, t = tb + (1 − t)a.

But then

s = t^{2}c + t(1 − t)a + t(1 − t)b + (1 − t)^{2}a = t^{2}c + t(1 − t)b + (1 − t)a
= tr + (1 − t)a,

which is exactly the fifth relation on the LHS. □

We now define the i-th Alexander polynomial Δ_{i}(G) of G for any i = 0, 1, 2, ... Present A(G) by #(V) generators and #(E) relations as above (where #(a set) is the number of elements of the set). Consider the corresponding (#(E) × #(V))-matrix over Λ. Let Δ_{i}(G) ∈ Λ be the greatest common divisor of all minors of rank #(V) − i of this matrix. By convention, if #(V) − i ≤ 0, then Δ_{i}(G) = 1; if #(V) − i ≥ #(E) + 1, then Δ_{i}(G) = 0. Clearly, Δ_{i}(G) is defined up to multiplication by monomials ±t^{k} with k ∈ ℤ and Δ_{i+1}(G) divides Δ_{i}(G) for all i. These polynomials are preserved under the moves R0–R3 on G. For the self-indexed graph of an oriented link L, this sequence of polynomials coincides with the (1-variable) Alexander polynomials of L.

Example 2.3.2. Consider the self-indexed graph

G = (c ⟵^{b} a ⟶^{c} b).

The relations c = ta + (1 − t)b and b = ta + (1 − t)c give the matrix of relations

( \begin{matrix}t & −1 & 1 − t \\ t & 1 − t & −1 \end{matrix} ) .

Its minors of size 2 are t(1 − t) + t = −t(t − 2). Thus, Δ_{1}(G) = t − 2. As a consequence, we see that G is not isotopic to the self-indexed graph of a knot. Indeed, the Alexander polynomials of knots (and links) are invariant under the conjugation t ↦ t^{−1}.

Substituting t = 1 one easily obtains that for any self-indexed graph G, the sum of coefficients of Δ_{1}(G) is 0 if G has ≥ 2 components and is ±1 if G is connected.

We can similarly define the Alexander module (and Alexander polynomials) of G with n variables where n is the number of components of G. Namely, let us enumerate these components by 1, 2, …, n. The (multivariable) Alexander module is the ℤ[t_{1}^{±}, …, t_{n}^{±}]-module generated by V modulo the relations c = t_{i}b−(1−t_{j})a for each arrow b⟶^{a}c where a belongs to the i-th component and b, c belong to the j-th component. It is again straightforward to check that this module is invariant under the moves R0–R3.

2.4. Linking numbers. We now introduce our first invariant of comtes depending on the flow. We say that an arrow of a self-indexed graph belongs to a certain component of this graph if its source (and then its target) belongs to this component. Note that arrows with the same label may belong to different components.

Let G = (V, E, s, t, ℓ) be a comte with flow I and components L_{1}, …, L_{n} (i.e., V = ∪_{i=1}^{n}L_{i}). For 1 ≤ i, j ≤ n, i ≠ j, the linking number lk_{ij} of L_{i} with L_{j}, is the sum of flows of arrows belonging to L_{j} with label in L_{i}. In other words,

lk_{ij} = ∑_{\begin{matrix}a∈E \\ s(a)∈L_{j} \\ ℓ(a)∈L_{i} \end{matrix}} I(a).

It is straightforward to check that the linking numbers are invariant under the moves R0–R3. For the comte of a link we recover the usual linking numbers. We warn, however, that linking numbers for comtes need not be symmetric, i.e., in general lk_{ij} ≠ lk_{ji}.

Example 2.4.1. The comte in Fig. 8 has three components L_{1} = {a, b}, L_{2} = {c}, and L_{3} = {d}. The linking numbers are zero, except for lk_{21} = 2.

[figure: a; b; c, 1; c, 1; c; d]

Figure 8. A comte with non-symmetric linking numbers

2.5. Quandle cocycle invariants of comtes. For a quandle X, a quandle 2-cocycle of X with values in an abelian group A (written multiplicatively) is a function f : X × X → A such that

f(x ▷ y, x ▷ z)f(x, z) = f(x, y ▷ z)f(y, z)

and f(x, x) = 1 for all x, y, z ∈ X. We show that each such f gives rise to an isotopy invariant of comtes.

Let G = (V, E, s, t, ℓ) be a self-indexed graph with flow I. A coloring of G by X is a function C : V → X such that for each arrow b⟶^{a}c in G we have C(a) ▷ C(b) = C(c). Assume that X is finite. Set

(2.5.1)  Φ(G, I, X, f) = ∑_{colorings ; C} ∏_{\begin{matrix}arrows \\ b⟶^{a,I}c \end{matrix}} f(C(a), C(b))^{I} ∈ ℤA,

where the product is taken in A (or in the ring ℤA), while the addition is that in ℤA. This is a refinement of the invariant counting the colorings of G by X. Indeed, if we take the map ϵ : ℤA → ℤ, ϵ(∑_{g∈A} n_{g}g) = ∑ n_{g}, then ϵ(Φ(G, I, X, f)) is the number of such colorings.

It is straightforward to see that Φ(G, I, X, f) is invariant under moves R0–R3. By the condition (1.2.1), this invariant does not depend on the choice of f in its cohomology class in H^{2}(X; A). We shall generalize this invariant in §4.3.

For the comte (G, I) of an oriented link L, the invariant Φ(G, I, X, f) coincides with the invariant Φ_{f}(L) defined in [CJKLS].

Remark 2.5.1. Any rack (in particular a quandle) X yields a self-indexed graph (X, X × X, s, t, ℓ), where s(x, y) = y, t(x, y) = x ▷ y and ℓ(x, y) = x for any x, y ∈ X. It is clear that a coloring of a self-indexed graph G by a quandle X is nothing but a homomorphism from G to the self-indexed graph determined by X (it is also the same as a quandle homomorphism from the quandle of G to X).

3. Virtual links and finite type invariants

3.1. The comte of a virtual link. Virtual links generalize the usual (oriented) links by admitting link diagrams with, possibly, “virtual” crossings, see [K]. The virtual links are the equivalence classes of such diagrams modulo an appropriate version of the Reidemeister moves. Another approach to virtual links uses the classical Gauss diagrams of links. A Gauss diagram consists of several oriented circles and arrows with distinct endpoints on the circles, see Figure 9 for a Gauss diagram on one circle. Each arrow should be provided with a sign ±1. Again, there are analogs of the Reidemeister moves for Gauss diagrams and virtual links are the equivalence classes of Gauss diagrams modulo these moves. Note that usual links can be encoded in terms of Gauss diagrams, but not every Gauss diagram arises from a link. Thus, virtual links can be thought as a generalization of links in which all Gauss diagrams are allowed.

We now associate a comte with every virtual link. Pick a Gauss diagram G representing this link. Cut the union of the circles of G at all arrowheads. This gives a finite number of oriented arcs a, b, c, ... which will be the vertices of our comte. Each arrow x of G gives rise to an edge of this comte as follows. There are two circle arcs, say b, c, adjacent to the headpoint of x where we choose the notation so that b is incoming and c is outgoing. We introduce an edge b⟶^{a}c if x has sign + and an edge c⟶^{a}b if x has sign −, where the label a is the circle arc containing the tail of x. The flow of this edge is defined to be the sign ±1 of x.

[figure: +; −; +; a; b; c; ↭; a; b; c; c, −1; c, 1; b, 1]

Figure 9. Gauss diagram and its comte

In the process of converting a virtual link into a comte, we loose some information. Specifically, two virtual links obtained from each other by swapping two arrowtails whenever there is no arrowhead between them, (see Figure 10) give rise to the same comtes. In the definition of virtual links in terms of link projections with virtual crossings, there are two analogs of the third Reidemeister move for three strands crossing at three points, two of which are virtual crossings. The two similar moves where only one of the crossings is virtual are not allowed. If one adds these two moves then the theory becomes empty, as any knot would become equivalent to the unknot. By passing to the comte, we are adding one of the two forbidden moves. Virtual links considered modulo one of these forbidden moves are called by L. Kauffman welded links.

[figure]

Figure 10. Move added when converting a virtual link into a comte

3.2. Finite type invariants. We outline a version of the theory of finite knot invariants for self-indexed graphs. Note that the flows seem to play no role in this context.

For a self-indexed graph G = (V, E, s, t, ℓ) and an arrow a ∈ E, we define G/a to be the self-indexed graph (V′, E′, s′, t′, ℓ′), where V′ = V/s(a) = t(a), E′ = E − {a}, and s′, t′, ℓ′ are the obvious maps induced by s, t, ℓ. If b is another arrow in G, then clearly (G/a)/b = (G/b)/a. Thus, for any set of arrows T ⊂ E, we can unambiguously define a self-indexed graph G/T by induction on the number of elements of T.

In analogy with [GPV], we define a self-indexed graph with semi-virtual arrows to be a pair (G, S), where G is a self-indexed graph and S ⊆ E is a set of arrows in G. The arrows belonging to S are called semivirtual arrows of (G, S). We draw semi-virtual arrows by dashed lines, as on the LHS of Fig. 11. Self-indexed e a

c d

f

b

d f

b

f a

c =

e a

c d

f

b

d f

b

f a

c −

e a

c

f

b

c

f a

c

b

Figure 11. A semi-virtual arrow

graphs with semi-virtual arrows yield a convenient way of encoding certain linear combinations of self-indexed graphs. Namely, each self-indexed graph with semi-virtual arrows (G, S) gives rise to the formal sum

[G, S] = ∑_{T ⊆S}(−1)^{#(T)} G/T ∈ ℤ𝔊

where 𝔊 is the set of isomorphism classes of self-indexed graphs and ℤ𝔊 is the abelian group freely generated by 𝔊.

Let ν be a map from 𝔊 to an abelian group A. We say that ν is an invariant of finite type if there exists an integer n ≥ 0 such that the linear extension ℤ𝔊 → A of ν vanishes on [G, S] for all self-indexed graphs (G, S) with n semi-virtual arrows. The minimal n with that property is called the degree of ν. For instance, an invariant of degree 1 assigns the same element of A to all self-indexed graphs. Of course, in our context we are interested only in those ν which are preserved under the transformations R0-R3.

3.3. Remark. Other objects from knot theory have their counterparts in the world of self-indexed graphs and comtes. This includes knotted graphs in ℝ^{3}, braids, and tangles. It would be interesting to reformulate further classical knot invariants, in particular the Conway and Jones polynomials, in terms of comtes. The authors plan to consider some of these questions in another publication.

4. Homology of self-indexed q-graphs

In this section we generalize the quandle cocycle invariants of comtes, replacing quandles by so-called self-indexed q-graphs. We also introduce a homology theory for the self-indexed q-graphs generalizing the homology of quandles.

4.1. Homology of self-indexed graphs. For each m ≥ 1, consider the graph y_{m} obtained as the 1-skeleton of the unit cube in ℝ^{m−1}. More precisely, let {e_{1}, …, e_{m−1}} be the canonical basis of ℝ^{m−1}. The vertices of y_{m} are the points (i_{1}, …, i_{m−1}) ∈ ℝ^{m−1} such that i_{j} ∈ {0, 1}. There is an arrow in y_{m} pointing form a vertex v to a vertex w iff w − v = e_{s} for some s. We now label the vertices and arrows of y_{m} by sequences of positive integers. The labels are defined by induction on m. The only vertex of y_{1} has label 1. Assume that y_{m} is labeled. Consider the intersection of y_{m+1} with the hyperplane {x_{1} = 0} and copy to it the labels from y_{m} with a shift: if a vertex or an arrow of y_{m} has a label j_{1}, j_{2}, …, j_{r}, then its copy in the hyperplane has the label j_{1} + 1, j_{2} + 1, …, j_{r} + 1. All the arrows of y_{m+1} parallel to e_{1} are labeled with 1. The labels of vertices and arrows of y_{m+1} lying in the hyperplane {x_{1} = 1} are those of the hyperplane {x_{1} = 0} with a 1 added at the beginning: if a vertex or an arrow v of {x_{1} = 0} has a label j_{1}, j_{2}, …, j_{r}, then its parallel translation v + e_{1} has the label 1, j_{1}, j_{2}, …, j_{r}.

We provide the disjoint union Y_{n} = ⨿_{m=1}^{n}y_{m} with the structure of a self-indexed graph: the map from the set of arrows of Y_{n} to the set of its vertices is defined by assigning to each arrow the only vertex with the same label. We draw y_{m} for m = 1, 2, 3, 4 in Figure 12. The whole figure is then a drawing of Y_{4}.

We consider 2n embeddings of Y_{n} in Y_{n+1}. They are the only homomorphisms compatible with the embeddings of y_{n} to y_{n+1} given by

D_{s}^{0}(i_{1}, …, i_{n−1}) = (i_{1}, …, i_{s−1}, 0, i_{s}, …, i_{n−1})
D_{s}^{1}(i_{1}, …, i_{n−1}) = (i_{1}, …, i_{s−1}, 1, i_{s}, …, i_{n−1}),

where s = 1, 2, …, n. These homomorphisms are the faces of Y_{n+1}. We can give an explicit description by considering the labels in the free quandle of the set {1, 2, …, n + 1}. The label j_{1}, …, j_{r} corresponds in this

[figure: y_{1}; 1; y_{2}; 2; 12; 1; y_{3}; 3; 23; 13; 123; 2; 12; 1; 1; y_{4}; 4; 24; 34; 234; 14; 124; 134; 1234; 2; 12; 2; 12; 1; 1; 1; 1; 23; 123; 3; 13]

Figure 12. Graph Y_{4} = y_{1} ∪ y_{2} ∪ y_{3} ∪ y_{4}.

description to j_{1} ▷ (j_{2} ▷ (⋯ ▷ j_{r})). Then

D_{s}^{0}(j_{1} ▷ (⋯ ▷ (j_{r−1} ▷ j_{r}))) = i_{1} ▷ (⋯ ▷ (i_{r−1} ▷ i_{r})),  with i_{t} = \begin{cases}j_{t} + 1 & if j_{t} ≥ s, \\ j_{t} & if j_{t} < s, \end{cases}

D_{s}^{1}(j_{1} ▷ (⋯ ▷ (j_{r−1} ▷ j_{r}))) = i_{1} ▷ (⋯ ▷ (i_{r−1} ▷ i_{r})),  with i_{t} = \begin{cases}s ▷ (j_{t} + 1) & if j_{t} ≥ s, \\ j_{t} & if j_{t} < s. \end{cases}

For instance, let us consider the embedding D_{2}^{1} : Y_{3} → Y_{4}. We get D_{2}^{1}(3) = 2 ▷ 4, D_{2}^{1}(1 ▷ 3) = 1 ▷ (2 ▷ 4), D_{2}^{1}(2 ▷ 3) = (2 ▷ 3) ▷ (2 ▷ 4) = 2 ▷ (3 ▷ 4), D_{2}^{1}(1 ▷ (2 ▷ 3)) = 1 ▷ ((2 ▷ 3) ▷ (2 ▷ 4)) = 1 ▷ (2 ▷ (3 ▷ 4)). Thus, D_{2}^{1} sends y_{3} to the “rear” face of y_{4}. Analogously, it sends y_{2} to the “top” face of y_{3}, with vertices 23, 123; and it sends y_{1} to itself.

We now define a homology theory for self-indexed graphs.

Definition 4.1.1. Let G = (V, E, s, t, ℓ) be a self-indexed graph. Let C_{n}(G) be the free abelian group generated by all homomorphisms f : Y_{n} → G. Define the boundary map ∂ : C_{n}(G) → C_{n−1}(G) by

∂(f) = ∑_{s=1}^{n−1}(−1)^{s}(fD_{s}^{0} − fD_{s}^{1}).

This gives a chain complex C_{•}(G). For an abelian group A, set

C_{•}(G, A) = C_{•}(G) ⊗ A, C^{•}(G, A) = Hom(C_{•}(G), A).

Consequently, we obtain homology and cohomology theories from these chain complexes.

We warn that our homology has nothing to do with Kontsevich’s graph homology theory. In his theory one fixes a species (or an operad) and graphs are used to define a basis for a chain complex. Here we fix a self-indexed graph and the basis is given by certain homomorphisms.

4.2. Self-indexed r-graphs and q-graphs. A self-indexed graph G = (V, E, s, t, ℓ) is an r-graph if (1) two different arrows pointing out from the same vertex have different labels, and

(2) two different arrows pointing into the same vertex have different labels. We say that G is a q-graph if furthermore

(3) each vertex a ∈ V has an arrow a⟶^{a}a with label, source and target a. If b⟶^{a}c is an arrow in a self-indexed r-graph, then we write c = a · b.

For instance, the self-indexed graph of a rack is a self-indexed r-graph. The self-indexed graph of a quandle is a self-indexed q-graph. However, there are many more self-indexed r-graphs and self-indexed q-graphs than racks and quandles (see for instance Example 4.2.1).

If G is a self-indexed r-graph, then a homomorphism f : Y_{n} → G is uniquely determined by f(1), …, f(n) (though it is not true that any sequence f(1), …, f(n) gives rise to a homomorphism). In this case, we denote f by < f(1), …, f(n) >. The definition of the boundary C_{n}(G) → C_{n−1}(G) can be re-written as

∂(< a_{1}, …, a_{n} >) = ∑_{s=1}^{n−1}(−1)^{s}(< a_{1}, …, a_{s−1}, a_{s+1}, …, a_{n} > − < a_{1}, …, a_{s−1}, a_{s} · a_{s+1}, …, a_{s} · a_{n} >).

If G is a self-indexed q-graph, we define C_{n}^{Q}(G) to be C_{n}(G) quotiented out by the morphisms < a_{1}, …, a_{n} > such that a_{i} = a_{i+1} for some i. This gives a quotient chain complex C_{•}^{Q}(G). Set

C_{•}^{Q}(G, A) = C_{•}^{Q}(G) ⊗ A, C_{Q}^{•}(G, A) = Hom(C_{•}^{Q}(G), A).

We obtain (co)homology theories from these chain complexes. We refer to cycles and cocycles in C_{•}^{Q}, C_{Q}^{•} as q-cycles and q-cocycles.

It is easy to see that if G is the self-indexed graph of a rack then any n-tuple < a_{1}, …, a_{n} > gives rise to a homomorphism and the chain complex C_{•}(G) coincides with the usual chain complex of the rack. Also, if G is the self-indexed graph of a quandle, then C_{•}^{Q}(G) coincides with the usual chain complex of the quandle (cf. [CJKLS]).

Our (co)homology of G in general is not invariant under the moves R0–R3 on G. For instance, let G_{2} and G_{3} be the self-indexed graphs respectively in the middle and RHS of Figure 14 below. If Ḡ_{2} and Ḡ_{3} denote the self-indexed graphs obtained by adding the arrows i⟶^{i}i for i = a, b, c, then we have H_{3}(Ḡ_{2}) = ℤ^{4}, while H_{3}(Ḡ_{3}) = ℤ^{5}. However, these two self-indexed graphs are isotopic.

We classified self-indexed r-graphs with 3 vertices. Modulo isomorphism, there are 6663 such self-indexed graphs, among which 70 are self-indexed q-graphs. We computed their homology with integer coefficients up to degree 5. There are 280 different values for self-indexed r-graphs and 28 for self-indexed q-graphs. We just give an example here.

Example 4.2.1. Let V = {a, b, c} and consider arrows i⟶^{i}i for i = a, b, c, and b⟶^{a}b, c⟶^{a}c, a⟶^{b}c, c⟶^{b}a, a⟶^{c}b. The homology up to degree 5 of this self-indexed graph is H_{1} = ℤ, H_{2} = ℤ^{2}, H_{3} = ℤ^{4}, H_{4} = ℤ^{7}, H_{5} = ℤ^{11}, from where it seems that the n-th Betti number of this self-indexed graph is \frac{1}{2}n(n − 1) + 1. Note that there is no rack with such homology, as Betti numbers of racks grow exponentially (see [EG]).

4.3. Quandle cocycle invariants re-examined. Fix a self-indexed graph G. Any n-chain I ∈ C_{n}(G) uniquely expands as

I = ∑_{τ:Y_{n}→G} I_{τ} τ.

For an n-cochain f ∈ C^{n}(G, A) with values in an abelian group A, set

∫_{G} I f = ∑_{τ:Y_{n}→G} I_{τ} f(τ).

Similarly, for a homomorphism of self-indexed graphs σ : G′ → G, an n-chain I on G′ and an A-valued n-cochain f on G, set

∫_{σ} I f = ∫_{G′} I (σ^{∗}f) = ∑_{τ:Y_{n}→G′} I_{τ} f(σ ∘ τ).

It is clear that if J is an (n + 1)-chain on G′, then

(4.3.1)  ∫_{σ}(∂J) f = ∫_{σ} J (∂^{∗}f).

Therefore ∫_{σ} induces a bilinear pairing H_{n}(G′) ⊗ H^{n}(G; A) → A.

We can use this formalism to define a state sum on a pair (a self-indexed graph G′, a chain I ∈ C_{n}(G′)). For a cochain f ∈ C^{n}(G, A), set

(4.3.2)  ∫∫ I f = ∑_{homomorphisms σ:G′→G} ∫_{σ} I f ∈ ℤA.

The sum here is the sum in the ring ℤA, while the integral on the RHS is given by sums in A. If I is a cycle and f is a cocycle, then ∫∫ I f depends only on their (co)homology classes, since by (4.3.1),

∫∫ (∂J) f = ∫∫ J (∂^{∗}f).

This relation holds also if G is a q-graph and f ∈ C_{Q}^{•}(G; A).

Corollary 4.3.1. The state sum ∫∫ I f defines a pairing ∫∫ : H_{n}(G′) × H^{n}(G; A) → ℤA (which, we warn, is not bilinear). If G is a q-graph, then this state sum defines also a pairing ∫∫ : H_{n}(G′) × H_{Q}^{n}(G; A) → ℤA.

□

4.4. Degree 2. We focus now on the case n = 2. Fix an abelian group A. Note that a flow on a self-indexed graph G′ is the same thing as a cycle in C_{2}(G′). If a self-indexed q-graph G is derived from a quandle, then, as remarked above, a cocycle in C_{Q}^{2}(G; A) is just a 2-cocycle of this quandle with values in A. Thus, let (G′, I) be a comte, let X be a finite quandle, let G be its self-indexed q-graph and let f ∈ Z_{Q}^{2}(G; A). It follows from definitions that under these assumptions

∫∫ I f = Φ(G′, I, G, f).

Proposition 4.4.1. Let G be a self-indexed q-graph and f ∈ Z_{Q}^{2}(G; A) a cocycle. The state sum ∫∫ I f does not change under the moves R1, R2 on the comte (G′, I). If G is derived from a quandle, then ∫∫ I f does not change under all the moves R0–R3 on (G′, I). Also ∫∫ I f = ∫∫ I f′ if f is cohomologous to f′.

Proof. The invariance of ∫∫ I f under the moves R2(a) and R2(b) follow from G being a self-indexed r-graph: if the LHS in Fig. 2(a) is part of G′, then any homomorphism G′ → G must send s and t to the same vertex. The invariance of ∫∫ I f under R1 follows from G being a self-indexed q-graph: if an arrow e of G′ is labeled by one of its endpoints, then any homomorphism G′ → G must send both endpoints to the same vertex. Also, since f is a q-cocycle, any arrow labeled with its source gives no contribution to the state sum invariant.

Now, suppose G is the self-indexed graph of a quandle. The invariance of ∫∫ I f under R0 follows since the flow on the deleted arrow is 0 (note that any homomorphism defined on the self-indexed graph on the RHS of Fig. 0 can be extended in a unique way to the self-indexed graph on the LHS). For the move R3(a), let G′ contain a subgraph as on the RHS of Fig. 7(3a). The condition x ▷ (y ▷ z) = (x ▷ y) ▷ (x ▷ z) implies that any graph homomorphism σ : G′ → G uniquely extends to a homomorphism from the self-indexed graph on the LHS to G (and analogously for the other edges in the square). Since the flow on the edge is assumed to be 0, the state sum does not change. As for R3(b), this is an immediate consequence of the 2-cocycle condition.

The last assertion is a consequence of Corollary 4.3.1. □

Remark 4.4.2. The requirement on G to be a quandle is necessary to have a bijection of the sets of graph homomorphisms for the self-indexed graphs on both sides of Fig. 0 and Fig. 7(3a). In order for ∫∫ I f to be invariant under R3, it would be enough to assume that G has the property that whenever one has a subgraph as on the RHS of Fig. 7(3a), the fourth arrow exists in G, as on the LHS of Fig. 7(3a). However, in this case ∫∫ I f would not be necessarily invariant under R0. In particular, considered for knots, it would not be invariant under the second and the third Reidemeister moves.

4.5. Examples. The smallest indecomposable quandle with H_{Q}^{2} ≠ 0 can be identified with the vertices of a tetrahedron. We denote its elements {0, 1, 2, 3}. Each vertex i acts by a rotation of the tetrahedron by an angle of \frac{2π}{3} fixing i, (see Figure 13, where the action of 0 is drawn).

[figure: 1; 2; 3; 0; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; .; 0▷?; 0▷?] Figure 13

Alternatively, one can think of this quandle as the affine (=Alexander) quandle over the field with 4 elements 𝔽_{4}, and the automorphism determined by ω ∈ 𝔽_{4} − {0, 1}. Specifically, x ▷ y = (1 − ω)x + ωy. An isomorphism f : tetrahedron → 𝔽_{4} is given by f(0) = 0, f(1) = 1 f(2) = ω, f(3) = 1 + ω (see [AG]). This quandle has a nontrivial 2-cocycle with values in the cyclic group with two elements, C_{2}. Let σ be the generator of C_{2}; we can write the cocycle as

f(< x, y >) = σ^{1−δ(xy(x−y))},

where δ(z) = 1 if z = 0 and δ(z) = 0 otherwise.

We compute the invariant of comtes derived from this 2-cocycle for the comtes G_{1}, G_{2}, G_{3} in Figure 14. It is easy to see that ∫∫ I_{1} f = 4 + 12σ and ∫∫ I_{2} f = ∫∫ I_{3} f = 4. Indeed, G_{2} and G_{3} are related by a sequence of moves R1, R3(a), R3(b), R3(a), R1.

[figure: a; b; c; c, 1; a, 1; b, 1; G_{1}, I_{1}; a; b; c; c, 1; a, 1; b, 1; b, 0; G_{2}, I_{2}; a; b; c; c, 1; c, 1; b, 0; b, 0; G_{3}, I_{3}] Figure 14

4.6. Acknowledgements. This work was written at IRMA, Strasbourg, while M.G. visited V.T. M.G. is deeply indebted to the whole IRMA for its warm hospitality; his thanks go also to L. Kauffman for correspondence about welded knots. V.T. would like to thank S. Matveev for useful correspondence on the quandles of links.

References

[AG] N. Andruskiewitsch and M. Graña From racks to pointed Hopf algebras, Adv. Math., to appear. Also in

         math.QA/0202084

[BZ] G. Burde and H. Zieschang, Knots, de Gruyter Studies in Mathematics, 5. Walter de Gruyter & Co., Berlin, 1985.

[CJKLS] J. S. Carter, D. Jelsovsky, S. Kamada, L. Langford and M. Saito, State-sum invariants of knotted curves and surfaces from quandle cohomology, Trans. Amer. Math. Soc., to appear. Also in math.GT/9903135.

[EG] P. Etingof and M. Graña On rack cohomology, J. Pure Appl. Algebra 177 (2003), no. 1, 49–59.

[GPV] M. Goussarov, M. Polyak and O. Viro, Finite-type invariants of classical and virtual knots, Topology 39 (2000), 1045–1068.

[J] D. Joyce, A Classifying Invariant of Knots, The Knot Quandle, J. Pure Appl. Alg. 23 (1982), 37–65.

[K] L. Kauffman, Virtual knots theory, European J. Combin. 20 (1999), no. 7, 663–690. Also in math.GT/9811028.

[Ma] S. Matveev, Distributive groupoids in knot theory, (Russian) Mat. Sb. (N.S.) 119(161) (1982), no. 1, 78–88. English translation: Math. USSR-Sb. 47 (1984), no. 1, 73–83.

[R] D. Rolfsen, Knots and links, Corrected reprint of the 1976 original. Mathematics Lecture Series, 7, Publish or Perish, Inc., Houston, TX, 1990.

IRMA–CNRS, 7 rue René Descartes

67084 Strasbourg Cedex

France

M.G. permanent address:

Depto de Matemática - FCEyN - Universidad de Buenos Aires

Ciudad Universitaria Pab. I

1428 Buenos Aires

Argentina