Mutant knots and intersection graphs
Mutant knots and intersection graphs
S. V. Chmutov∗, S. K. Lando †
April 10, 2007
Abstract
We prove that if a finite order knot invariant does not distinguish mutant knots,
then the corresponding weight system depends on the intersection graph of a
chord diagram rather than on the diagram itself. The converse statement is
easy and well known. We discuss relationship between our results and certain
Lie algebra weight systems.
1 Introduction
Below, we use standard notions of the theory of finite order, or Vassiliev, invariants
of knots in 3-space; their definitions can be found, for example, in [6] or [14]. All
knots are assumed to be oriented.
Two knots are said to be mutant if they differ by a rotation/reflection of a tangle
with four endpoints; if necessary, the orientation inside the tangle may be replaced
by the opposite one. Here is a famous example of mutant knots, the Conway (11n34)
knot C of genus 3, and Kinoshita–Terasaka (11n42) knot KT of genus 2 (see [1]).
C = KT =
Note that the change of the orientation of a knot can be achieved by a mutation in
the complement to a trivial tangle.
Most known knot invariants cannot distinguish mutant knots. Neither the (col-
ored) Jones polynomial, nor the HOMFLY polynomial, nor the Kauffman two variable
polynomial distinguish mutants. All Vassiliev invariants up to order 10 do not dis-
tinguish mutants as well [17] (up to order 8 this fact was established by a direct
computation [5, 6]). However, there is a Vassiliev invariant of order 11 distinguishing
C and KT [16, 17]. It comes from the colored HOMFLY polynomial.
∗The Ohio State University, Mansfield.
†Institute for System Research RAS and the Poncelet Laboratory, Independent University of
Moscow, partly supported by the grant ACI-NIM-2004-243 (Noeuds et tresses), RFBR 05-01-01012-
a, NWO-RFBR 047.011.2004.026 (RFBR 05-02-89000-NWOa), GIMP ANR-05-BLAN-0029-01.
http://arxiv.org/abs/0704.1313v1
The main combinatorial objects of the Vassiliev theory of knot invariants are
chord diagrams. To a chord diagram, its intersection graph (also called circle graph)
is associated. The vertices of the graph correspond to chords of the diagram, and two
vertices are connected by an edge if and only if the corresponding chords intersect.
The value of a Vassiliev invariant of order n on a singular knot with n double
points depends only on the chord diagram of the singular knot. Hence any such
invariant determines a function, a weight system, on chord diagrams with n chords.
Conversely, any weight system induces, in composition with the Kontsevich integral,
which is the universal finite order invariant, a finite order invariant of knots. Such
knot invariants are called canonical. Canonical invariants span the whole space of
Vassiliev invariants.
Direct calculations for small n show that the values of these functions are uniquely
determined by the intersection graphs of the chord diagrams. This fact motivated
the intersection graph conjecture in [5] (see also [6]) which states that any weight
system depends on the intersection graph only. This conjecture happened to be false,
because of the existence of a finite order invariant that distinguishes two mutant knots
mentioned above and the following fact.
The knot invariant induced by a weight system whose values depend only on the
intersection graph of the chord diagrams cannot distinguish mutants.
A justification of this statement, due to T. Le (unpublished), looks like follows
(see details in [6]). If we have a knot (in general position) with a distinguished two-
string tangle, then all the terms in the Kontsevich integral of the knot having chords
connecting the tangle with its exterior vanish.
Our goal is to prove the converse statement thus establishing an equivalence be-
tween finite order knot invariants nondistinguishing mutants and weight systems de-
pending on the intersection graphs of chord diagrams only.
Theorem 1 If a finite order knot invariant does not distinguish mutants, then the
corresponding weight system depends only on the intersection graphs of chord dia-
grams.
Together, the two statements can be combined as follows.
A canonical knot invariant does not distinguish mutants if and only if its weight
system depends on the intersection graphs of chord diagrams only.
Recently, B. Mellor [15] extended the concept of intersection graph to string links.
We do not know whether our Theorem 1 admits an appropriate generalization.
Section 2 is devoted to the proof of Theorem 1. In Sec. 3, we discuss relationship
between intersection graphs and the weight systems associated to the Lie algebra sl(2)
and the Lie algebra gl(1|1).
The paper was written during the second author’s visit to the Mathematical De-
partment of the Ohio State University. He expresses his gratitude to this institution
for warm hospitality and excellent working conditions. The authors are grateful to
S. Duzhin, K. J. Supowit, and A. Vaintrob for useful discussions.
2 Proof
2.1 Representability of graphs as the intersection graphs of
chord diagrams
Not every graph can be represented as the intersection graph of a chord diagram. For
example, the following graphs are not intersection graphs.
A characterization of those graphs that can be realized as intersection graphs is given
by an elegant theorem of A. Bouchet [4].
On the other hand, distinct diagrams may have coinciding intersection graphs.
For example, next three diagrams have the same intersection graph :
A combinatorial analog of the tangle in mutant knots is a share [5, 6]. Informally,
a share of a chord diagram is a subset of chords whose endpoints are separated into
at most two parts by the endpoints of the complementary chords. More formally,
Definition 1 A share is a part of a chord diagram consisting of two arcs of the outer
circle possessing the following property: each chord one of whose ends belongs to
these arcs has both ends on these arcs.
Here are some examples:
A share Not a share Two shares
The complement of a share also is a share. The whole chord diagram is its own share
whose complement contains no chords.
Definition 2 A mutation of a chord diagram is another chord diagram obtained by
a rotation/reflection of a share.
For example, three mutations of the share in the first chord diagram above produce
the following chord diagrams:
Obviously, mutations preserve the intersection graphs of chord diagrams.
Theorem 2 Two chord diagrams have the same intersection graph if and only if they
are related by a sequence of mutations.
This theorem is contained implicitly in papers [3, 8, 11] where chord diagrams
are written as double occurrence words, the language better suitable for describing
algorithms than for topological explanation.
Proof of Theorem 2.
The proof of this theorem uses Cunningham’s theory of graph decompositions [9].
A split of a (simple) graph Γ is a disjoint bipartition {V1, V2} of its set of vertices
V (Γ) such that each part contains at least 2 vertices, and there are subsets W1 ⊆ V1,
W2 ⊆ V2 such that all the edges of Γ connecting V1 with V2 form the complete
bipartite graph K(W1,W2) with the parts W1 and W2. Thus for a split {V1, V2} the
whole graph Γ can be represented as a union of the induced subgraphs Γ(V1) and
Γ(V2) linked by a complete bipartite graph.
Another way to think about splits, which is sometimes more convenient and which
we shall use in the pictures below, looks like follows. Consider two graphs Γ1 and Γ2
each having a distinguished vertex v1 ∈ V (Γ1) and v2 ∈ V (Γ2), respectively, called
markers. Construct the new graph Γ = Γ1 ⊠(v1,v2) Γ2 whose set of vertices is
V (Γ) = {V (Γ1)− v1} ⊔ {V (Γ2)− v2}
and whose set of edges is
E(Γ) = {(v′1, v
1) ∈ E(Γ1) : v
1 6= v1 6= v
1} ⊔ {(v
2) ∈ E(Γ2) : v
2 6= v2 6= v
{(v′1, v
2) : (v
1, v1) ∈ E(Γ1) and (v2, v
2) ∈ E(Γ2)} .
Representation of Γ as Γ1⊠(v1,v2)Γ2 is called a decomposition of Γ, Γ1 and Γ2 are called
the components of the decomposition. The partition {V (Γ1)−v1, V (Γ2)−v2} is a split
of Γ. Graphs Γ1 and Γ2 might be decomposed further giving a finer decomposition
of the initial graph Γ. Pictorially, we represent a decomposition by pictures of its
components where the corresponding markers are connected by a dashed edge.
A prime graph is a graph with at least three vertices admitting no splits. A de-
composition of a graph is said to be canonical if the following conditions are satisfied:
(i) each component is either a prime graph, or a complete graph Kn, or a star Sn,
which is the tree with a vertex, the center, adjacent to n other vertices;
(ii) no two components that are complete graphs are neighbors, that is, their mark-
ers are not connected by a dashed edge;
(iii) the markers of two components that are star graphs connected by a dashed edge
are either both centers or both not centers of their components.
W. H. Cunningham proved [9, Theorem 3] that each graph with at least six vertices
possesses a unique canonical decomposition.
Let us illustrate the notions introduced above by two examples of canonical de-
composition of the intersection graphs of chord diagrams. We number the chords and
the corresponding vertices in our graphs, so that the unnumbered vertices are the
markers of the components. The first example is our example from page 3:
A chord diagram
The intersection graph
1������������
6 5 4
The canonical decomposition
The second example represents the chord diagram of the double points in the plane
diagram of the Conway knot C from page 1. The double points of the shaded tangle
are represented by the chords 1,2,9,10,11.
8 6 9 10
Chord diagram
Intersection graph
Canonical decomposition
The key observation in the proof of Theorem 2 is that components of the canoni-
cal decomposition of any intersection graph admit a unique representation by chord
diagrams. For a complete graph and star components, this is obvious. For a prime
component, this was proved by A. Bouchet [3, Statement 4.4] (see also [11, Section
6] for an algorithm finding such a representation for a prime graph).
Now to describe all chord diagrams with a given intersection graph, we start with
a component of its canonical decomposition. There is only one way to realize the
component by a chord diagram. We draw the chord corresponding to the marker as a
dashed chord and call it the marked chord. This chord indicates the places where we
must cut the circle removing the marked chord together with small arcs containing
its endpoints. As a result we obtain a chord diagram on two arcs. Repeating the
same procedure with a neighbor component of the canonical decomposition, we get
another chord diagram on two arcs. We have to sew these two diagrams together by
their arcs in an alternating order. There are four possibilities to do this, and they
differ by mutations of the share corresponding to the second (or, alternatively, the
first) component. This completes the proof of Theorem 2. �
To illustrate the last stage of the proof consider our standard example and take
the star 2-3-4 component first and then the triangle component. We get
�� CUT
Because of the symmetry, the four ways of sewing these diagrams produce only two
distinct chord diagrams with a marked chord:
repeating the same procedure with the marked chord for the last 1-6 component of
the canonical decomposition, we get
1 ���� CUT
Sewing this diagram into the previous two in all possible ways we get four mutant
chord diagrams from page 3.
As an enjoyable exercise we leave to the reader to work out our second example
with the chord diagram of the diagram of the Conway knot and find the mutation
producing the chord diagram of the plane diagram of the Kinoshita–Terasaka knot
using the canonical decomposition.
2.2 Proof of Theorem 1
Suppose we have a Vassiliev knot invariant v of order at most n that does not dis-
tinguish mutant knots. Let D1 and D2 be chord diagrams with n chords whose
intersection graphs coincide. We are going to prove that the values of the weight
system of v on D1 and D2 are equal.
By Theorem 2, it is enough to consider the case when D1 and D2 differ by a
single mutation in a share S. Let K1 be a singular knot with n double points whose
chord diagram is D1. Consider the collection of double points of K1 corresponding
to the chords occurring in the share S. By the definition of a share, K1 has two arcs
containing all these double points and no others. By sliding the double points along
one of these arcs and shrinking the other arc we may enclose these arcs into a ball
whose interior does not intersect the rest of the knot. In other words, we may isotope
the knot K1 to a singular knot so as to collect all the double points corresponding to
S in a tangle TS. Performing an appropriate rotation of TS we obtain a singular knot
K2 with the chord diagram D2. Since v does not distinguish mutants, its values on
K1 and K2 are equal. Theorem 1 is proved. �
To illustrate the proof, let D1 be the chord diagram from our standard example.
Pick a singular knot representing D1, say
K1 = 61 2 3
5 D1 =
To perform a mutation in the share containing the chords 1,5,6, we must slide the
double point 1 close to the double points 5 and 6, and then shrink the corresponding
arcs:
Sliding the double point 1
Shrinking the arcs
Forming the tangle TS
Now doing an appropriate rotation of the tangle TS we obtain a singular knot K2
representing the chord diagram D2.
3 Lie algebra weight systems
and intersection graphs
Kontsevich [12] generalized a construction of Bar-Natan [2] of weight systems defined
by a Lie algebra and its representation to a universal weight system, with values in
the universal enveloping algebra of the Lie algebra. In [18], Vaintrob extended this
construction to Lie superalgebras.
Our main goal in this section is to prove
Theorem 3 The universal weight systems associated to the Lie algebra sl(2) and
to the Lie superalgebra gl(1|1) depend on the intersection graphs of chord diagrams
rather than on the diagrams themselves.
It follows immediately that the canonical knot invariants corresponding to these
two algebras do not distinguish mutants. The latter fact is already known, but we
did not manage to find appropriate references; instead, we give a direct proof on the
intersection graphs side.
Note that for more complicated Lie algebras the statement of Theorem 3 is no
longer true. For example, the universal sl(3) weight system distinguishes between the
Conway and the Kinoshita–Terasaka knots.
In fact, for each of the two algebras we prove more subtle statements.
Theorem 4 The universal weight system associated to the Lie algebra sl(2) depends
on the matroid of the intersection graph of a chord diagram rather than on the inter-
section graph itself.
This theorem inevitably leads to numerous questions concerning relationship be-
tween weight systems and matroid theory, which specialists in this theory may find
worth being investigated.
Weight systems have a graph counterpart, so-called 4-invariants of graphs [13].
The knowledge that a weight system depends only on the intersection graphs does
not guarantee, however, that it arises from a 4-invariant. In particular, we do not
know, whether this is true for the universal sl(2) weight system. Either positive
(with an explicit description) or negative answer to this question would be extremely
interesting. For gl(1|1), the answer is positive.
Theorem 5 The universal weight systems associated to the Lie superalgebra gl(1|1)
is induced by a 4-invariant of graphs.
In the first two subsections below, we recall the construction of universal weight
systems associated to Lie algebras and the notion of 4-invariant of graphs. The next
two subsections are devoted to separate treating of the Lie algebra sl(2) and the Lie
superalgebra gl(1|1) universal weight systems.
3.1 Weight systems via Lie algebras
Our approach follows that of Kontsevich in [12]. In order to construct a weight system,
we need a complex Lie algebra endowed with a nondegenerate invariant bilinear form
(·, ·). The invariance requirement means that (x, [y, z]) = ([x, y], z) for any three
elements x, y, z in the Lie algebra. Pick an orthonormal basis a1, . . . , ad, (ai, aj) = δij ,
d being the dimension of the Lie algebra. Any chord diagram can be made into an
arc diagram by cutting the circle at some point and further straightening it. For an
arc diagram of n arcs, write on each arc an index i between 1 and d, and then write
on both ends of the arc the letter ai. Reading all the letters left to right we obtain
a word of length 2n in the alphabet a1, . . . , ad, which is an element of the universal
enveloping algebra of our Lie algebra. The sum of all these words over all possible
settings of the indices is the element of the universal enveloping algebra assigned to
the chord diagram. This element is independent of the choice of the cutting point of
the circle, as well as the orthonormal basis. It belongs to the center of the universal
enveloping algebra and satisfies the 4-term relation, whence can be extended to a
weight system. The latter is called the universal weight system associated to the Lie
algebra and the bilinear form, and it can be specialized to specific representations
of the Lie algebra as in the original Bar-Natan’s approach. Obviously, any universal
weight system is multiplicative: its value on a product of chord diagrams coincides
with the product of its values on the factors.
The simplest noncommutative Lie algebra with a nondegenerate invariant bilinear
form is sl(2). It is 3-dimensional, and the center of its universal enveloping algebra
is the ring C[c] of polynomials in a single variable c, the Casimir element. The
corresponding universal weight system was studied in detail in [7]. It attracts a lot
of interest because of its equivalence to the colored Jones polynomials.
In [18], Kontsevich’s construction was generalized to Lie superalgebras, and this
construction was elaborated in [10] for the simplest non-commutative Lie superalgebra
gl(1|1). The center of the universal enveloping algebra of this algebra is the ring of
polynomials C[c, y] in two variables. The value of the corresponding universal weight
system on a chord diagram with n chords is a quasihomogeneous polynomial in c
and y, of degree n, where the weight of c is set to be 1, and the weight of y is set to
be 2.
3.2 The 4-bialgebra of graphs
By a graph, we mean a finite undirected graph without loops and multiple edges.
Let Gn denote the vector space freely spanned over C by all graphs with n vertices,
G0 = C being spanned by the empty graph. The direct sum
G = G0 ⊕ G1 ⊕ G2 ⊕ . . .
carries a natural structure of a commutative cocommutative graded Hopf algebra.
The multiplication in this Hopf algebra is induced by the disjoint union of graphs,
and the comultiplication is induced by the operation taking a graph G into the sum
GU ⊗GŪ , where U is an arbitrary subset of vertices of G, Ū its complement, and
GU denotes the subgraph of G induced by U .
The 4-term relation for graphs is defined in the following way. By definition, the
4-term element in Gn determined by a graph G with n vertices and an ordered pair
A,B of its vertices connected by an edge is the linear combination
G−G′AB − G̃AB + G̃
where
• G′AB is the graph obtained by deleting the edge AB in G;
• G̃AB is the graph obtained by switching the adjacency to A of all the vertices
adjacent to B in G;
• G̃′AB is the graph obtained by deleting the edge AB in G
AB (or, equivalently,
by switching the adjacency to A of all the vertices adjacent to B in G′AB).
All the four terms in a 4-term element have the same number n of vertices. The
quotient of Gn modulo the span of all 4-term elements in Gn (defined by all graphs
and all ordered pairs of adjacent vertices in each graph) is denoted by Fn. The direct
F = F0 ⊕F1 ⊕F2 ⊕ . . .
is the quotient Hopf algebra of graphs, called the 4-bialgebra. The mapping taking a
chord diagram to its intersection graph extends to a graded Hopf algebra homomor-
phism γ from the Hopf algebra of chord diagrams to F .
Being commutative and cocommutative, the 4-bialgebra is isomorphic to the
polynomial ring in its basic primitive elements, that is, it is the tensor product
S(P1)⊗ S(P2)⊗ . . . of the symmetric algebras of its homogeneous primitive spaces.
3.3 The sl(2) weight system
Our treatment of the universal weight system associated with the Lie algebra sl(2)
is based on the recurrence formula for computing the value of this weight system on
chord diagrams due to Chmutov and Varchenko [7]. The recurrence states that if a
chord diagram contains a leaf, that is, a chord intersecting only one other chord, then
the value of the sl(2) universal weight system on the diagram is (c − 1/2) times its
value on the result of deleting the leaf, and, in addition,
− − + = 2 − 2
meaning that the value of the weight system on the chord diagram on the left-hand
side coincides with the linear combinations of its values on the chord diagrams indi-
cated on the right.
Now, in order to prove Theorem 3 for the universal sl(2) weight system, we must
prove that mutations of a chord diagram preserve the values of this weight system.
Take a chord diagram and a share in it. Apply the above reccurence formula to a
chord and two its neighbors belonging to the chosen share. The recurrence relation
does not affect the complementary share, while all the instances of the modified first
share are simpler than the initial one (each of them contains either fewer chords or
the same number of chords but with fewer intersections). Repeating this process, we
can replace the original share by a linear combination of the simplest shares, chains,
which are symmetric meaning that they remain unchanged under rotations. The sl(2)
case of Theorem 3 is proved. �
Now let us turn to the proof of Theorem 4. For elementary notions of matroid
theory we refer the reader to any standard reference, say to [19]. Recall that a matroid
can be associated to any graph. It is easy to check that the matroid associated to the
disjoint union of two graphs coincides with that for the graph obtained by identifying
a vertex in the first graph with a vertex in the second one. We call the result of
gluing a vertex in a graph G1 to a vertex in a graph G2 a 1-product of G1 and G2.
The converse operation is 1-deletion. Of course, the 1-product depends on the choice
of the vertices in each of the factors, but the corresponding matroid is independent
of this choice.
Similarly, let G1, G2 be two graphs, and pick vertices u1, v1 in G1 and u2, v2 in G2.
Then the matroid associated to the graph obtained by identifying u1 with u2 and v1
with v2 coincides with the one associated to the graph obtained by identifying u1 with
v2 and u2 with v1. The operation taking the result of the first identification to that
of the second one is called the Whitney twist on graphs.
Both the 1-product and the Whitney twist have chord diagram analogs. For two
chord diagrams with a distinguished chord in each of them, we define their 1-product
as a chord diagram obtained by replacing the distinguished chords in the ordinary
product of chord diagrams chosen so as to make them neighbors by a single chord
connecting their other ends. The Whitney twist also is well defined because of the
following statement.
Lemma 1 Suppose the intersection graph of a chord diagram is the result of identi-
fying two pairs of vertices in two graphs G1 and G2. Then both graphs G1 and G2 are
intersection graphs, as well as the Whitney twist of the original graph.
The assertion concerning the graphs G1 and G2 is obvious. In order to prove that
the result of the Whitney twist also is an intersection graph, let c1, c2 denote the
two chords in a chord diagram C such that deleting these chords makes C into an
ordinary product of two chord diagrams C1, C2. By reflecting the diagram C2 and
restoring the chords c1 and c2 we obtain a chord diagram whose intersection graph is
the result of the desired Whitney twist. The lemma is proved.
According to the Whitney theorem, two graphs have the same matroid iff they
can be obtained from one another by a sequence of 1-products/deletions and Whitney
twists. Therefore, Theorem 4 follows from
Lemma 2 (i) The value of the universal sl(2) weight system on the 1-product of chord
diagrams coincides with the product of its values on the factors divided by c. (ii) The
value of the universal sl(2) weight system remains unchanged under the Whitney twist
of the chord diagram.
Statement (i) is proved in [7]. The proof of statement (ii) is similar to that of
Theorem 3. Consider the part C2 participating in the Whitney twist and apply to
it the recurrence relations. Note that the relations do not affect the complementary
diagram C1. Simplifying the part C2 we reduce it to a linear combination of the
simplest possible diagrams, chains, which are symmetric under reflection. Reflecting
a chain preserves the chord diagram, whence the value of the sl(2) weight system.
Theorem 4 is proved. �
3.4 The gl(1|1) weight system
Define the (unframed) Conway graph invariant with values in the ring of polynomi-
als C[y] in one variable y in the following way. We set it equal to (−y)n/2 on graphs
with n vertices if the adjacency matrix of the graph is nondegenerate, and 0 otherwise.
Recall that the adjacency matrix AG of a graph G with n vertices is an n× n-matrix
with entries in Z2 obtained as follows. We choose an arbitrary numbering of the
vertices of the graph, and the entry aij is 1 provided the i th and the j th vertices
are adjacent and 0 otherwise (diagonal elements aii are 0). Note that for odd n, the
adjacency matrix cannot be nondegenerate, hence the values indeed are in the ring of
polynomials. The Conway graph invariant is multiplicative: its value on the disjoint
union of graphs is the product of its values on the factors.
Clearly, the Conway graph invariant is a 4-invariant. Moreover, it satisfies the 2-
term relation, which is more restrictive than the 4-term one: its values on the graphsG
and G̃AB coincide for any graph G and any pair of ordered vertices A,B in it. Indeed,
consider the graph as a symmetric bilinear form on the Z2-vector space whose basis is
the set of vertices of the graph, the adjacency matrix being the matrix of the bilinear
form in this basis. In these terms, the transformation G 7→ G̃AB preserves the vector
space and the bilinear form, but changes the basis A,B,C, · · · → A + B,B,C, . . . .
Thus, it preserves the nondegeneracy property of the adjacency matrix.
The subspace F1 is spanned by the graph p1 with a single vertex (whence no
edges), which is a primitive element. Since F is the polynomial ring in its primitive
elements, each homogeneous space Fn admits a decomposition into the direct sum of
two subspaces, one of which is the subspace of polynomials in primitive elements of
degree greater than 1, and the other one is the space of polynomials divisible by p1.
We define the framed Conway graph invariant as the only multiplicative 4-invariant
with values in the polynomial ring C[c, y] whose value on p1 is c, and on the projection
of any graph to the subspace of p1-independent polynomials along the subspace of
p1-divisible polynomials coincides with the Conway graph invariant of the graph.
The values of the framed Conway graph invariant can be computed recursively.
Take a graph G and consider its projection to the subspace of graphs divisible by p1.
On this projection, the framed Conway graph invariant can be computed because of
its multiplicativity. Now add to the result the value of the (unframed) Conway graph
invariant on the graph. Now we can refine the statement of theorem 5.
Theorem 6 The gl(1|1) universal weight system is the pullback of the framed Conway
graph invariant to chord diagrams under the homomorphism γ.
Proof. The proof follows from two statements in [10]. Theorem 3.6 there states
that setting c = 0 in the value of the gl(1|1) universal weight system on a chord
diagram we obtain the result of deframing this weight system. Theorem 4.4 asserts
that this value is exactly the Conway invariant of the chord diagram. The latter
coincides with the Conway graph invariant of the intersection graph of the chord
diagrams defined above. Since the deframing for chord diagrams is a pullback of the
deframing for graphs, we are done. �
References
[1] The knot Atlas, http://katlas.math.toronto.edu/wiki/Main_Page
[2] D. Bar-Natan, On Vassiliev knot invariants, Topology, 34, 423–472 (1995)
[3] A. Bouchet Reducing prime graphs and recognizing circle graphs, Combinatorica,
7, no. 3, 243–254 (1987)
[4] A. Bouchet Circle graph obstructions, J. Combin. Theory Ser. B 60, no. 1, 107–
144 (1994)
[5] S. V. Chmutov, S. V. Duzhin, S. K. Lando Vassiliev knot invariants I. Introduc-
tion, Advances in Soviet Mathematics, vol. 21, 117-126 (1994)
[6] S. Chmutov, S. Duzhin, J. Mostovoy, CDBooK. Introduction to Vassiliev Knot
invariants. (a preliminary draft version of a book about Chord Diagrams.)
http://www.math.ohio-state.edu/~chmutov/preprints/
[7] S. V. Chmutov, A. N. Varchenko, Remarks on the Vassiliev knot invariants com-
ing from sl2, Topology 36, no. 1, 153–178 (1997)
[8] B. Courcelle Circle graphs and Monadic Second-order logic, Preprint, June 2005,
http://www.labri.fr/perso/courcell/ArticlesEnCours/CircleGraphsSubmitted.pdf
[9] W. H. Cunningham, Decomposition of directed graphs, SlAM J. Algor. Discrete
Math.,3, no. 2, 214–228 (1982)
[10] J. M. Figueroa-O’Farrill, T. Kimura, A. Vaintrob, The universal Vassiliev in-
variant for the Lie superalgebra gl(1|1), Comm. Math. Phys. 185, no. 1, 93–
127 (1997)
[11] C. P. Gabor, K. J. Supowit, W.-L. Hsu, Recognizing circle graphs in polynomial
time, Journal of the ACM (JACM) (3), 36, no. 3, 435–473 (1989)
[12] M. Kontsevich, Vassiliev’s knot invariants, Adv. Soviet Math., 16, Part 2, AMS,
Providence RI, 137–150 (1993)
[13] S. K. Lando, On a Hopf algebra in graph theory, J. Comb. Theory Series B, 80,
no. 1, 104–121 (2000)
[14] S. K. Lando, A. K. Zvonkin, Graphs on surfaces and their applications, Springer
(2004)
[15] B. Mellor, Intersection graphs for string links, J. Knot Theory Ramif. 15, no. 1,
53-72 (2006).
[16] H. R. Morton, P. R. Cromwell, Distinguishing mutants by knot polynomials, J.
Knot Theory Ramif. 5 225–238 (1996)
[17] J. Murakami, Finite type invariants detecting the mutant knots, Knot Thoery.
A volume dedicated to Professor Kunio Murasugi for his 70th birthday. Edi-
tors: M. Sakuma et al., Osaka University, March 2000. Preprint is available at
http://www.f.waseda.jp/murakami/papers/finitetype.pdf
[18] A. Vaintrob, Vassiliev knot invariants and Lie S-algebras, Math. Res. Lett. 1,
no. 5, 579–595 (1994)
[19] D. J. A. Welsh, Matroid theory, Academic Press, London (1976)
	Introduction
	Proof
	Representability of graphs as the intersection graphs of chord diagrams
	Proof of Theorem ??
	Lie algebra weight systems and intersection graphs
	Weight systems via Lie algebras
	The 4-bialgebra of graphs
	The sl(2) weight system
	The gl(1|1) weight system
