Документ взят из кэша поисковой машины. Адрес оригинального документа : http://dfgm.math.msu.su/files/0articles/Ilyutko/ilyutko-JKTR.pdf
Дата изменения: Fri Aug 21 18:41:38 2009
Дата индексирования: Sat Apr 9 23:07:39 2016
Кодировка:

Journal of Knot Theory and Its Ramifications Vol. 18, No. 6 (2009) 791823 c World Scientific Publishing Company

INTRODUCTION TO GRAPH-LINK THEORY

DENIS PETROVICH ILYUTKO Department of Mechanics and Mathematics, Moscow State University, 119991, GSP-1, Moscow, Leninskiye Gory, Russia dilyutko@yahoo.com VASSILY OLEGOVICH MANTUROV Moscow State Regional University, Chair of Geometry, Moscow, 105005, Radio St., 10a, Russia vomanturov@yandex.ru Accepted 18 February 2009 ABSTRACT The present paper is an introduction to a combinatorial theory arising as a natural generalization of classical and virtual knot theory. There is a way to encode links by a class of "realizable" graphs. When passing to generic graphs with the same equivalence relations we get "graph-links". On one hand graph-links generalize the notion of virtual link, on the other hand they do not detect link mutations. We define the Jones polynomial for graph-links and prove its invariance. We also prove some a generalization of the KauffmanMurasugiThistlethwaite theorem on "minimal diagrams" for graph-links. Keywords : Knot; virtual knot; graph-link; Kauffman bracket; Jones polynomial. Mathematics Sub ject Classification 2000: 57M25

1. Intro duction The discovery of virtual knot theory by Kauffman [1] in mid 1990s was an important step in generalizing combinatorial and topological knot theoretical techniques into a larger domain (knots in thickened surfaces), which is an important step towards generalization of these techniques for knots in arbitrary manifolds. It turned out that some invariants (Kauffman bracket polynomial) can be generalized for virtual knots immediately [1], and some other theories (Khovanov homology theory) need a complete revision of the original construction for a generalization for the case of virtual knots [2]. On the other hand, virtual knots sharpened several problems and elicited some phenomena which do not appear in the classical knot theory [3], e.g. the existence of a virtual knot with non-trivial Jones polynomial and trivial fundamental group
791

792

D. P. Ilyutko & V. O. Manturov

emphasizes the difficulty of extracting the Jones polynomial information out of the knot group. In the present paper, we introduce a new class of ob jects closely connected to both classical and virtual knots: graph-links. Likewise virtual knots appear out of non-realizable Gauss co de and thus generalize classical knots (which have realizable Gauss codes), graphs-links come out of intersection graphs: we may consider graphs which realize chord diagrams, and, in turn, virtual links, and pass to arbitrary simple graphs which correspond to some mysterious ob jects generalizing links and virtual links. Here we refer to the paper by Traldi and Zulli [4]. They were considering similar ob jects generalizing virtual knots, but their starting point of generalization was different. There is a way of co ding all knots by Gauss diagrams and there is another way of coding all links by rotating circuits (see, e.g. [5]). Thus, the class of ob jects described in the present paper is different than the one described by Traldi and Zulli. The rotating circuit approach to both classical and virtual links has several advantages in comparison to the Gauss diagram approach: for classical links, it do es not carry nugatory information, it is easier to recognize planarity, and a single circle diagram can enco de a link of arbitrarily many components. On the other hand, while passing from a chord diagram to its intersection graph we forget a lot of information, for example, mutant knots are invisible at the level of intersection graphs. Thus, our graph knots are a sort of "simplified generalized virtual knots". Though one can hardly imagine a picture of such a link for a non-realizable graph, in the present paper we construct an invariant Kauffman bracket corresponding to them and Jones polynomial. This bracket counts the "number of non-existing circles of a non-realizable chord diagram". The point is that for a graph-link there is no link diagram in the usual sense: we do not have crossings and edges connecting them. In the same sense, we can not say how state circles look like. Nevertheless, we can count the number which in the classical case coincides with the number of circles. In this sense we say "count the number of non-existing circles". The invariance of the bracket agrees with the fact that it do es not detect knot mutation. To construct the Kauffman bracket of a graph-link, one has to count non-existing circles, but to manage with the Khovanov homology, one should also know how these non-existing circles in different Kauffman states of the diagram interfere. In general, the problem seems to be unmanageable (e.g. since the Khovanov homology does detect link mutation, Wehrli [6]), but the question is: to which extent one can generalize (or categorify) the Kauffman bracket of a knot. We shall address this question in a sequel of the present paper. We also use various metho ds involving Kauffman bracket for detecting the minimal crossing number (minimal vertex number) of a graph-knot, and give a few examples.

Introduction to Graph-Link Theory

793

2. Preliminaries. Basic Constructions 2.1. Atoms and virtual links First of all, note that in this part of the paper we restrict ourselves to a large class of graph-links corresponding to so-called "orientable atoms". Note that classical knots satisfy that condition, i.e. classical diagrams form a subset in the set of all virtual diagrams, such that the atom corresponding to any classical diagram is orientable. We shall deal with the most general ob ject in a sequel of the present paper. A short version of this general theory is sketched in [7]. Definition 2.1. An atom [8] is a pair (M, ) consisting of a closed 2-manifold M and a finite graph embedded in M together with a coloring of M \ in a checkerboard manner. An atom is called orientable (connected) if the surface M is orientable (connected). Here is called the frame of the atom. By genus (atoms and their genera were also studied by Turaev [9], and atom genus is also called the Turaev genus [9]) (Euler characteristic, orientation) of the atom we mean that of the surface M . Remark 2.2. Throughout the paper, we shall deal with two types of graphs: fourvalent graphs with fixed structure of opposite half-edges at vertices (atom frames or shadows of links) and intersection-type graphs of arbitrary valency. Four-valent graphs are always assumed connected, and the intersection-type graphs may not be connected, though they are assumed to have no lo ops and no multiple edges. Given an atom. Assume there is an embedding of its frame into R2 in such a way that the structure of opposite half-edges at vertices is preserved. Then we can take the "black angle" structure of the atom to restore the crossings on the plane (see ahead). In [10] it is proved that the link isotopy type do es not depend on the particular choice of embedding of the frame into R2 with the structure of opposite edges preserved. The reason is that such embeddings are quite rigid. Definition 2.3. An atom is called height or vertical if its frame is embeddable in R2 so that the opposite half-edge structure is preserved. However, not all atoms can be obtained from classical knots. It may be impossible to embed the frame of an abstract atom into R2 so that the opposite half edge structure is preserved. However, if it is impossible to embed a graph into R2 , we may immerse it by marking artefacts of the immersion (we assume the immersion to be generic) by small circles. This leads to a connection between atoms and virtual knots which perfectly agrees with virtual knot theory proposed by Kauffman in [1]. Definition 2.4. A virtual diagram is a 4-valent diagram in R2 where each crossing is either endowed with a classical crossing structure (with a choice for underpass and overpass specified) or just said to be virtual and marked by a circle.

794

D. P. Ilyutko & V. O. Manturov

B A

B A

Fig. 1.

The detour move.

Definition 2.5. A virtual link is an equivalence class of virtual diagrams mo dulo generalized Reidemeister moves. The latter consist of usual Reidemeister moves referring to classical crossings and the detour move that replaces one arc containing only virtual intersections and self-intersections by another arc of such sort in any other place of the plane, see Fig. 1. Remark 2.6. Throughout the paper, each virtual diagram has at least one classical crossing. Remark 2.7. All virtual diagrams (corresponding to atoms or to graphs) are constructed mo dulo detour moves. This simplifies the verification of the invariance. As the detour move do es not affect the Kauffman bracket polynomial, we make no difference between virtual diagrams obtained from each other by detours. The encoding by chord diagrams and graphs will not see detours at all, so we will be able to check only classical Reidemeister moves to establish any invariance. Given a virtual diagram L, let us construct the atom A(L) asso ciated with L. Vertices of A(L) are in one-to-one correspondence with classical crossings of the diagram L. Classical crossings of L are connected to each other by branches of L which may intersect each other in virtual crossings. In each classical crossing we have four emanating edges x1 ,x2 ,x3 ,x4 in clockwise-ordering such that the pair (x1 ,x3 ) forms an undercrossing and the pair (x2 ,x4 ) forms an overcrossing. These edges are in one-to-one correspondence with edges of A(L) that connect the corresponding vertices. The 1-cycles of the frame pasting black and white cells are constructed as follows. Each boundary of a 2-cell is a rotating circuit on a frame: a circuit which passes every edge at most once and switches at each vertex from an edge to an adjacent (non-opposite) one. Black cells are glued to the angles formed by (x1 ,x2 )

Introduction to Graph-Link Theory

795

x3 x2
Fig. 2.

x4 x1
Gluing the cells.

and (x3 ,x4 ), and white cells are glued to the angles formed by (x2 ,x3 ) and (x1 ,x4 ), see Fig. 2. As a result we get an atom. Example 2.8. Let L be the virtual diagram depicted in Fig. 3 and A(L) be the atom associated with L, see Fig. 4. Considering the frame of A(L) and counting its Euler characteristic , one gets 2 vertices, 4 edges, and 3 cells, so = 1. This means that the corresponding surface is the pro jective plane.

Fig. 3.

Virtual trefoil.

Fig. 4.

Non-orientable atom.

796

D. P. Ilyutko & V. O. Manturov

Let us consider the inverse operation. Having an atom, we may try to construct a virtual diagram. To do that, we should take a generic immersion of the atom's frame in R2 , put virtual crossings at the intersection points of images of different edges and restore classical crossings at images of vertices "as above". Obviously, since we disregard virtual crossings, and one could expect the well-definiteness of the "operation" atomvirtual diagram (up to detours). However, this is not the case. Indeed, for every vertex of the atom with four emanating half-edges a, b, c, d (ordered cyclically on the atom) we may get two different clo ckwise-orderings on the plane of immersion, (a, b, c, d) and (a, d, c, b). This leads to a move called virtualization. Definition 2.9. By a virtualization of a classical crossing of a virtual diagram we mean a lo cal transformation shown in Fig. 5. The above statements summarize as Prop osition 2.10. (See, e.g. [11].) Let L1 and L2 be two virtual links obtained from the same atom by using different immersions of its frame. Then L1 differs from L2 by a sequence of (detours and ) virtualizations. Note that many famous invariants of classical and virtual knots (Kauffman bracket, Khovanov homology [2, 12], KhovanovRozansky homology [13, 14]) do not change under the virtualization, which supports the virtualization conjecture: Conjecture (Virtualization conjecture). If for two classical links L and L there is a sequence L = L0 ··· Ln = L of virtualizations and generalized Reidemeister moves then L and L are classical ly equivalent (isotopic). Note that the usual virtual equivalence implies classical equivalence for classical links, see [15]. This means that classical links constitute a proper subset of virtual links. 2.2. Thickened surface interpretation of virtual links Virtual links, being defined diagrammatically, have a topological interpretation. They correspond to links in oriented thickened surfaces Sg в I with fixed I -bundle structure up to stabilizations/destabilizations. Pro jecting Sg to R2 (with the condition, however, that all neighborhoods of crossings are pro jected with respect to

Fig. 5.

Virtualization.

Introduction to Graph-Link Theory

797

the orientation, we get a diagram on R2 from a generic diagram on Sg ): besides the usual crossings arising naturally as pro jections of classical crossings, we get virtual crossings, which arise as artefacts of the pro jection: two strands lie in different places on Sg but they intersect on the plane because they are forced to do so. We shall use the following construction. Having a virtual link diagram K , we take all classical crossings of it and associate with a neighborho o d of a crossing two crossing bands -- a "piece of 2-surface", as shown in Fig. 6, and with a virtual crossing we asso ciate a pair of skew bands, as shown in the lower picture of Fig. 6. If we connect these crossings and bands by (non-overtwisted) bands going along edges, we get a 2-surface with boundary. Gluing its boundary components by discs, we get an orientable closed surface M (K ). There is an obvious pro jection of (a part of ) M (K ) to R2 in such a way that classical crossings of the link diagram drawn in M (K ) generate the diagram of K (with virtual crossings at intersections of skew bands). Then we get a link in M (K ) в I representing the virtual link K . This approach was proposed by Kauffman [1], Kamada and Kamada [16]. Remark 2.11. Note that a thickened surface interpretation differs from the presentation by atoms. A thickened surface representation asso ciates with a virtual diagram and a diagram on a 2-dimensional surface with the overcrossing and undercrossing structure specified. An atom (a checkerboard colorable surface, see ahead) asso ciates with a virtual diagram with no further structure specified: the overcrossing and undercrossing structure can be read out of the cell coloring structure. An atom need not be orientable, while a thickened surface need not be checkerboard colorable. On the other hand, atom does not feel virtualization, whence the thickened surface do es. Later, we will consider only connected thickened surfaces and call the genus of it the underlying genus of a representative for a virtual knot K . For more details, see, e.g. [11].

Fig. 6.

The local structure.

798

D. P. Ilyutko & V. O. Manturov

2.3. Chord diagrams and intersection graphs Definition 2.12. A chord diagram is a cubic graph consisting of a selected oriented cycle (the circle) and several non-oriented edges (chords) connecting points on the circle in such a way that every point is incident to at most one chord. A chord diagram is labeled if every chord is endowed with a sign "+" or "-". If no signs are indicated, we assume the chord diagram has all chords with sign "+". Two chords of a chord diagram are called linked if the ends of one chord lie in different connected components of the circle without the end-points of the second chord. Definition 2.13. A graph is labeled if every vertex is endowed with a sign "+" or "-". Let D be a labeled chord diagram D. The labeled intersection graph, see [17], G(D) is the labeled graph: (1) whose vertices are in one-to-one correspondence with chords of D, (2) the label of each vertex corresponding to a chord coincides with that of the chord, and (3) two vertices are connected by an edge if and only if the corresponding chords are linked. A labeled chord diagram is a d-diagram if the corresponding intersection graph is bipartite. Some remarks are in order. Remark 2.14. Note that d-diagrams are precisely those enco ding classical link diagrams [10]: a chord diagram is embeddable in R2 if and only if it is a d-diagram, and embeddability of a chord diagram yields the planarity of the corresponding four-valent graph (a shadow of the link, which thus has no virtual crossings). Remark 2.15. To avoid confusion between framing and labeling throughout the paper, we consider only labeled chord diagram with positive framing as each virtual link corresponds to an orientable atom and we forget about framing. Remark 2.16. In fact, chord diagrams with all positive chords enco de all orientable atoms with one white cell: this white cell corresponds to the A-state of the virtual diagram, and chords show how this cell approaches itself in neighborho o ds of crossings (atom vertices). If we want to deal with all atoms and restrict ourselves for the case of one circle, we should take this circle to correspond to some other state of the atom, which is encoded by labelings of the chords. Having a labeled chord diagram D, one can construct a virtual link diagram K (D) (up to virtualization) as follows. Let us immerse this diagram in R2 by taking an embedding of the circle and placing some chords inside the circle and the other ones outside the circle. After that we remove neighborho o ds of each of the chord ends and replace them by a pair of lines with a classical crossing in the following way. A crossing can be smoothed in two ways: A and B as in the Kauffman bracket polynomial. We require that the initial piece of the circle corresponds to the A-smo othing if the chord is positive and to the B -smo othing if it is negative: A: , B: . Note that from d-diagrams we get classical links.

Introduction to Graph-Link Theory

799

Conversely, having a connected virtual diagram K (with at least one classical crossing) with oriented atom, one can get a labeled chord diagram. Indeed, one takes a circuit of K which is a map from S 1 to the shadow of K . This map is bijective outside classical and virtual crossings, has exactly two inverse images at each classical and virtual crossing, goes transversally at each virtual crossing and turns from an edge to an adjacent (non-opposite) edge at each classical crossing. Connecting the two inverse images of each classical crossing by an edge we get a chord diagram (orientation of the circle is chosen arbitrarily), where the sign of the chord is "+" if the circuit locally agrees with the A-smo othing, and "-" if it agrees with the B -smoothing. It can be easily checked that this operation is indeed inverse to the operation of constructing a virtual link out of a chord diagram: if we take a chord diagram D, and construct a virtual diagram K (D) out of it, then for some circuit the chord diagram corresponding to K (D) will coincide with D. The rule for setting classical crossings here agrees with the rule described above because of the orientability of the atom. This proves the following Theorem 2.17 [11]. Any connected virtual diagram with an orientable atom is obtained from a certain labeled chord diagram. We restrict our attention to connected virtual diagrams with orientable atoms. The following two theorems show that the set of all such diagrams gives us another class which is wider than the class of classical links but narrower than the one of all virtual links. Theorem 2.18. Any two equivalent (in the class of al l virtual diagrams ) connected virtual diagrams are equivalent in the class of connected virtual diagrams. Pro of. Having a disconnected diagram, we can make it connected by adding crossings by second Reidemeister moves. After performing a necessary move to make the diagram connected, we may perform the inverse Reidemeister move (and, possibly, perform another move in another place). It is easy to see that the pro cess can be organized in such a way that the "auxiliary" crossings do not affect the original moves we have to perform, and in the final diagram all auxiliary crossings are removed. This completes the proof. Theorem 2.19. Any two equivalent (in the class of al l virtual diagrams ) virtual diagrams K1 and K2 with orientable atoms are equivalent in the class of virtual diagrams with orientable atoms. This theorem was independently proved by Viro and the second named author of the present paper, but the pro of was not published. This theorem signifies the consistency of the class of ob jects we are dealing with: virtual links with orientable atoms constitute a proper part of all virtual links.

800

D. P. Ilyutko & V. O. Manturov

Pro of. Consider a thickened surface presentation of virtual links [1, 16, 18]. It can be easily checked that the orientability of the atom corresponding to a virtual link diagram depends only on the Z2 -homology class of the corresponding link surface presentation (the pro of is left to reader as the exercise). Consequently, if we perform a move which do es not change the genus of the corresponding surface, we do not change the orientability of the atom. Obviously, the detours do not affect the surface presentation and hence orientability of the atom. A straightforward check shows neither the first nor the third Reidemeister move changes the genus of the underlying surface, thus, do es affect the orientability of the atom. The second Reidemeister move may either increase the genus or decrease the genus or leave it as it is. For the case of the second Reidemeister move not changing the genus, the orientability is not changed. Moreover, we may pass from an orientable atom to a non-orientable atom only in the case when we increase the genus of the thickened surface representation by a second Reidemeister move. Now, assume K1 and K2 are virtual diagrams with orientable atoms. We use the same notation for the corresponding knots in thickened surfaces: K1 and K2 . It follows from Kuperberg's theorem that there is the following sequence of transformations: we first transform K1 to its minimal representative K1 having minimal genus. Then, we transform K2 to its minimal representative K2 which has the same genus as K1 and is isotopic inside the surface of that genus to K1 . The latter means that K1 and K2 are connected by a sequence of genus-preserving Reidemeister moves. So, since both K1 and K2 have orientable atoms, the whole chain of diagrams K1 ··· K1 ··· K2 ··· K2 corresponds to a sequence of orientable atoms, which completes the pro of. The Reidemeister moves give a combinatorial description of the relationship between the different diagrams of a given virtual link. Thus, a virtual link is an equivalence class of virtual link diagrams modulo Reidemeister moves. The ob jects we are going to deal with will also be equivalence classes of certain diagrams mo dulo certain Reidemeister moves. We shall start with chord-moves then pass to graphlinks which are equivalence classes of certain graphs mo dulo graph-moves. The following definition describes the set of moves corresponding to usual set of Reidemeister moves for planar diagrams. Definition 2.20. 1. The first Reidemeister chord-move is an addition/removal of an isolated chord labeled "+" or "-" (an isolated chord, not linked with any others). 2. The second Reidemeister chord-move is an addition/removal of two parallel chords a, b labeled "+" and "-", so that for any other chord c a is linked with c if and only if b is linked with c. 3. The third Reidemeister chord-move is shown in Fig. 7. All the chords except for three chords shown in Fig. 7 are fixed and their ends lie on the "dotted" parts of the circle.

Introduction to Graph-Link Theory

801

C A
Fig. 7.

C+ -B A

+B

The third Reidemeister chord-move.

B A bC D
Fig. 8.

B -b -a A D
The fourth chord-move.

D C A C

a

-b B

-a

4. This move corresponds to a circuit change. Two chord diagrams representing the same virtual diagram can be obtained from one another by only the fourth chord-moves. The fourth chord-move is shown in Fig. 8. The move takes four segments of the chord diagram denoted by A, B , C, D and transforms the diagram as follows. We perform the surgery along the chords with signs a and b, a, b {±}. This surgery cuts the diagram into four pieces A, B , C, D each containing some chord ends, and reconnects them by a pair of vertical lines and a pair of horizontal lines (middle picture). The two chords we are operating with change their labels. After that we redraw the figure to get a "round circle" of the chord diagram (rightmost picture) and get a shuffle of the segments A, B , C, D with all chord ends lying on them. Remark 2.21. Using the second and fourth chord-moves, we can replace each chord labeled "-" by three chords labeled "+" as shown in Fig. 9. The chords having their ends on the "dotted" parts of the circle are fixed. Theorem 2.22. Let K1 and K2 be two connected virtual diagrams with orientable atoms, and D1 and D2 be two labeled chord diagrams obtained from K1 and K2 , respectively. If K1 and K2 are equivalent in the class of connected diagrams with orientable atoms then D1 is obtained from D2 by 1 - 4 chord-moves.

+ A B A +
Fig. 9. The sign changing.

+

B

802

D. P. Ilyutko & V. O. Manturov

Pro of. First of all, recall that we do not make difference between diagrams obtained from each other by detours. By construction virtual diagram obtained from a given chord diagram is defined up to detours. Secondly, when we construct a chord diagram from a virtual diagram K , we fix a circuit of K which is a map from S 1 to the shadow of K . The independence from the choice of a circuit is guaranteed by the fourth chord-move 4. Indeed, assume two labeled chord diagrams D1 and D2 represent the same virtual diagram (up to detours). Then D1 and D2 can be obtained from each other by a change of rotating circuit. We have to rotate the circuit for D1 at some collection of m vertices (chords of D1 ) to get the circuit for D2 . It is easy to see that there is a couple of linked chords among them (otherwise there is no circuit, but a collection of circuits after a surgery). Take a pair of intersecting chords and change the circuit respectively. This will be precisely one fourth move. We get a diagram D1 which differs from D2 at some collection of m - 2 vertices. Repeating the pro cess above, we get to D2 from D1 in a finite number of steps. Without loss of generality, we can assume the following: (1) K1 and K2 are distinguished from each other by classical Reidemeister moves, (2) we have rotating circuits of K1 and K2 for each K1 and K2 , and (3) all the moves are performed in the class of connected virtual diagrams with orientable atoms. Under such assumptions the classical first and second Reidemeister moves on virtual link are equivalent to the first and second Reidemeister chord-moves. As for the third Reidemeister move on virtual diagrams, it is sufficient to consider only one variant provided that we have the whole collection of the first and second Reidemeister moves, see [19]. At the level of chord diagrams, it is again sufficient to consider only one way of representing this third Reidemeister move (shown in Fig. 10) provided that we have all second Reidemeister chord-moves and the

B C A C

B +

+

-

A

C A
Fig. 10.

C B

+ A

+B

The third Reidemeister move and the third chord-move.

Introduction to Graph-Link Theory

803

fourth chord-move. Under such assumptions the one classical third Reidemeister move on virtual link is equivalent to the third Reidemeister chord-move, Fig. 10. This completes the proof. Now, we are going to deal with labeled graphs. It is not necessary for a labeled graph to be represented as the intersection graph of any chord diagram. For such graphs we shall mimic graph version of Reidemeister moves (see below) as if these graphs were really corresponding to chord diagrams and, hence, to virtual knots. Definition 2.23. Let G be of vertices for G. We define A(G) = (aij )i,j =1,...,n be the vertices i and j are incident, a labeled graph on n vertices. Fix an enumeration the adjacency matrix A(G) over Z2 as follows. Set adjacency matrix of G, i.e. aij = 1 if and only if the and aij = 0 otherwise. Besides, we seta aii = 0.

Assume we are given a labeled chord diagram. Define the surgery along a set of chords as follows. For every chord, we draw a parallel chord near it and remove the arc of the circle between adjacent ends of the chord as in Fig. 11. By a small perturbation, the picture in R2 is transformed into a one-manifold in R3 . This manifold m(D) is the result of surgery, see Fig. 12. Surprisingly, the number of the connected components of m(D) can be determined from of the intersection graph.

Fig. 11.

A surgery of the circuit along a chord.

Fig. 12.

The manifold m(D ).

a The case a ii = 1 corresp onds to framed chords with framing 1, which, in turn, corresp ond to non-orientable atoms, that we shall consider in another paper.

804

D. P. Ilyutko & V. O. Manturov

Theorem 2.24 [20, 21]. Let D be a (labeled ) chord diagram, and let G be its (labeled ) intersection graph. Then the number of connected components of m(D) equals corank A(G)+ 1, where A(G) is the adjacency matrix of G. Remark 2.25. Theorems 2.24 allows us to define "the number of circles" for a graph even when the given graph is not a intersection graph. 3. The Kauffman Bracket Polynomial The Kauffman bracket polynomial [1, 22] is a very useful mo del for understanding the Jones polynomial [23]. The Kauffman bracket polynomial asso ciates with a virtual link diagram a Laurent polynomial in one variable a. After a small normalization (multiplication by a power of (-a)) it gives an invariant for virtual links. This invariant can be read out of the atom corresponding to a knot diagram. Namely, take an atom A with n vertices corresponding to a virtual diagram L with n classical crossings. By a state we mean a choice of a pair of black or white angles at every vertex of A. Every such choice gives rise to a collection of closed curves on A whose boundaries contain all edges of A, see Fig. 13, and at each crossing the curves turn locally from one edge to an adjacent edge sharing the same angle of the prefixed color. Thus, having 2n states of the atom, we define the Kauffman bracket polynomial of it as A (a) =
s

a

(s)- (s)

(-a2 - a

-2 (s)-1

)

,

(3.1) and (s) denote the (s) = n) and (s) invariant under virof the corresponding

where the sum is taken over all states s of the diagram, (s) number of white and black angles in the state (thus, (s) + denotes the number of curves in the state. As mentioned above, the Kauffman bracket polynomial is tualization. Thus, it is not surprising that it can be read out atom.

State curves

Knot diagram

Fig. 13.

State curves drawn on an atom.

Introduction to Graph-Link Theory

805

If the atom A is obtained from a (framed) chord diagram C , then one can construct the Kauffman bracket polynomial C (A) . Thus, one obtains a function f on (framed) chord diagrams valued in Laurent polynomials in a. This function is interesting because it is connected to the Vassiliev invariants of knots and J -invariants of closed curves (see [5, 24]). Throughout the paper, we consider "intersection-type" graphs without lo ops and multiple edges (simple graphs). Assume now we have a labeled graph (a graph with each vertex labeled either positively or negatively). Then it may or may not be represented by an intersection graph of a chord diagram (see [25] for details). Moreover, if such a chord diagram exists, it should not be unique, see, e.g. Fig. 14. This non-uniqueness usually corresponds to so called mutations of virtual knots. The mutation operation (shown in the top of Fig. 15) cuts a piece of a knot diagram inside a box, turns it by a half-twist and returns to the initial position. Note that the virtualization is a special case of mutation. The mutation operation is expressed in terms of chord diagrams in almost the same way: one cuts a piece of diagram with four ends and exchanges the top and the bottom parts of it (see bottom picture of Fig. 15). More precisely, this operation corresponds to the mutation from both Gauss diagram and rotating circuit points of view. In the bottom part of Fig. 15 chords whose end points belong to the "dotted" area remain the same; the other chords (having their end-points in the "dotted" segments) are reflected as a whole. It is well-known that the Kauffman bracket polynomial do es not detect mutations, see, e.g. [11]. Thus, one might guess that the corresponding Kauffman bracket polynomial can be read out of the intersection graph. Surprisingly, the Kauffman bracket polynomial can be defined in a meaningful way even for those labeled graphs which can not be represented as intersection graphs of chord diagrams (the initial definition was given in [5], but graph-links and Reidemeister moves for graphs were not defined and there was no approach to prove any invariance).

Fig. 14.

Two chord diagrams with the same intersection graph.

806

D. P. Ilyutko & V. O. Manturov

R

R

Fig. 15.

Mutation and its chord diagram presentation.

Indeed, we are able to calculate how many circles we have in each state, we can apply Eq. (3.1) to calculate the Kauffman bracket polynomial of a graph. Let G be a (simple) labeled finite graph with the set of vertices V (G) and the set of edges E (G). Suppose s V (G). Set G(s) to be the subgraph of the graph G with the set of vertices V (G(s)) = s and the set of edges E (G(s)) such that {u, v } E (G(s)), where u, v s, if and only if {u, v } E (G). Definition 3.1. We call a subset of V (G) a state of the graph G. A state is called the A-state if it consists of all the vertices of G labeled "-" and no vertex labeled "+". Analogously, a state is called the B -state if it consists of all vertices of G labeled "+" and no vertex labeled "-". The opposite state for a state s is the set of vertices complementary to s (the opposite state to the A-state is the B -state). Two states are called neighboring if they differ only in one vertex, which belongs to one state and not to the other state. The distance between two states is equal to the number of the vertices in which two states differ. A state s is called singlecircle state if corank A(G(s)) = 0. We define the number of circles in a state s as corank A(G(s)) + 1. Remark 3.2. Note that k + l n +2, here k and l are the numbers of circles in the A-state and the B -state, respectively. Definition 3.3. Let G be a simple finite labeled graph with the set of vertices V (G), |V (G)| = n. Define the Kauffman bracket polynomial of G as G (a) =
s

a

(s)- (s)

(-a2 - a

-2 corank A(G(s))

)

,

Introduction to Graph-Link Theory

807

where the sum is taken over all states s (subset of the set of vertices) of the graph G, (s) is equal to the sum of the vertices labeled "-" from s and of the vertices labeled "+" from V (G)\s, (s) = n - (s). Recall that all matrices are over Z2 and corank Anвn = n - rank A. 4. Graph-Links One can construct the intersection graph from a chord diagram. Therefore, we can define graph-moves corresponding to the chord-moves. As a result we obtain a new ob ject -- an equivalence class of labeled graphs under formal moves. Definition 4.1. Let G be a graph and let v be its vertex. The set of all vertices adjacent to v is called neighborhood of a vertex v and denoted by N (v ) or NG (v ). Definition 4.2. g 1. The first Reidemeister graph-move is an addition/removal of an isolated vertex labeled "+" or "-". g 2. The second Reidemeister graph-move is an addition/removal of two nonadjacent vertices having the different signs and the same adjacency with others. g 3. The third Reidemeister graph-move is defined as follows. Let u, v , w be three vertices of G all having label "-" and u is adjacent only to v and w in G. Then we only change the adjacency of u with the vertices t N (v )\N (w) N (w)\N (v ) (for other pairs of vertices we do not change their adjacency). In addition, we change the labels of v and w to "+". The inverse operation is also called the third Reidemeister graph-move. g 4. The fourth graph-move is defined as follows. We take two adjacent vertices u labeled a and v labeled b, a, b {±1}. Then we change labels of u and v so that the label of u becomes -b and the label of v becomes -a. In addition, we change the adjacency for each pair (t, w) of vertices, where t N (u), w N (v )\N (u) and t N (v ), w N (u)\N (v ). The definition above together with the arguments of Theorem 2.22 yields Theorem 4.3. Let K1 and K2 be two connected virtual diagrams with orientable atoms, and G1 and G2 be two labeled intersection graphs obtained from K1 and K2 , respectively. If K1 and K2 are equivalent in the class of connected diagrams with orientable atoms then G1 and G2 are obtained from one another by g 1 - g 4 graph-moves. We defined the Kauffman bracket polynomial for an arbitrary simple labeled graph. Our goal is to show that it is invariant under some graph-moves, and then to normalize it in order to get the Jones polynomial. As a result, we get an invariant of graph-links, see ahead. Now we are going to define this ob ject and to check the invariance of the Kauffman bracket polynomial up to some factor.

808

D. P. Ilyutko & V. O. Manturov

Definition 4.4. A graph-link is an equivalence of simple labeled graphs mo dulo g 1 - g 4 graph-moves. Theorem 4.5. The Kauffman bracket polynomial of a labeled graph is invariant under g 2 - g 4 graph-moves. Pro of. Let G be a labeled graph with the set of vertices V (G) and let G be a graph obtained from G by some graph-move of the graph-moves g 2 - g 4. V (G) is the set of all vertices of G. (1) Let us consider the second graph-move g 2. Suppose that vertices u V (G) labeled "+" and v V (G) labeled "-" are added to G to get G. Enumerate all vertices of G by numbers from 1 to n, and enumerate all vertices of G by numbers from 1 to n + 2 so that the number of u is 1, the number of v is 2, and w V (G)\{u, v } has number i 3 if and only if w in G has number (i - 2). The adjacency matrix A(G) is 00 a a , A(G) = 0 0 a a A(G) where bold characters indicate row and column vectors. Let s V (G). Then corank A(G(s)) = corank A(G(s)), corank A(G(s {u})) = corank A(G(s {v })) = corank A(G(s {u, v })) - 1 and G (a) =
sV (G)

(a +a +a +a

2((s)+1)-(n+2)

(-a2 - a )

e -2 corank A(G(s))

)

2(s)-(n+2)

(-a2 - a
2

e -2 corank A(G(s{u})) e -2 corank A(G(s{v }))

2((s)+2)-(n+2) 2((s)+1)-(n+2)

(-a - a (-a2 - a
2

) )

e -2 corank A(G(s{u,v }))

)

=
sV (G)

(a +a

2(s)-n

(-a - a )

-2 corank A(G(s))

)

2(s)-n

(-a2 - a

e -2 corank A(G(s{u}))

(a

-2

+ a2 - a2 - a

-2

))

= G (a), here (s) is equal to the sum of the vertices labeled "-" from s and of the vertices labeled "+" from V (G)\s. (2) Let us consider the third graph-move g 3. There are two versions of the third graph-move we consider only one. Enumerate all vertices of G by numbers from

Introduction to Graph-Link Theory

809

1 to n so that the label of u is 1, the label of v is 2, and the label of w is 3. The vertices of G have the same numbers as the vertices of G do. The adjacency matrices A(G) and A(G) are 01 1 0 A(G) = 1 0 0a 10 0a , 0 b bB A(G) = a 0 0 0 (a + b) 0 00 a . 0 00 b +b a b B

Let s V = V (G)\{u, v , w}. Then corank A(G(s)) = corank A(G(s {u})) - 1 = corank A(G(s {u, v })) = corank A(G(s {u, w})) = corank A(G(s)), corank A(G(s {v, w})) = corank A(G(s {v, w})) = corank A(G(s {u, v })) = corank A(G(s {u, w})) = corank A(G(s {u, v , w})) - 1, corank A(G(s {v })) = corank A(G(s {v })), corank A(G(s {w})) = corank A(G(s {w})), corank A(G(s {u, v , w})) = corank A(G(s {u})), and G (a) =
sV

(a +a

2(s)-n

(-a2 - a

-2 corank A(G(s))

)

2((s)+1)-n 2

((-a2 - a ((-a2 - a (-a2 - a
2

-2 corank A(G(s{u}))

)

+(-a - a +a +(-a - a +a =
sV 2

-2 corank A(G(s{v }))

)

+(-a2 - a

-2 corank A(G(s{w }))

)

)

2((s)+2)-n

-2 corank A(G(s{u,v }))

)

-2 corank A(G(s{u,w }))

)

+(-a2 - a
2

-2 corank A(G(s{v,w }))

)

)

2((s)+3)-n

-2 corank A(G(s{u,v ,w }))

)

)
-2

(a +a

2(s)-n

(-a - a

-2 corank A(G(s))

)

(1 + a (-a2 - a

)+2a4 )

2((s)+1)-n 2

((-a2 - a

-2 corank A(G(s{v }))

)

+(-a - a

-2 corank A(G(s{w }))

)

)

810

D. P. Ilyutko & V. O. Manturov

+a +a =
sV

2((s)+2)-n 2((s)+3)-n

(-a2 - a (-a2 - a
2

-2 corank A(G(s{v,w }))

) )

-2 corank A(G(s{u,v ,w })) -2 corank A(G(s))

)

(a +a

2((s)+2)-n

(-a - a

)

2((s)+1)-n 2

((-a2 - a (-a2 - a (-a - a
2

-2 corank A(G(s{v }))

)

+(-a - a +a +a

-2 corank A(G(s{w }))

)

)

2((s)+2)-n 2((s)+3)-n

-2 corank A(G(s{v,w }))

) )

-2 corank A(G(s{u,v ,w }))

),

here (s) is equal to the sum of the vertices labeled "-" from s and of the vertices labeled "+" from V \s. Analogously for G, we get G (a) =
sV

(a +a +a

2((s)+2)-n

(-a2 - a

e -2 corank A(G(s))

)

2((s)+3)-n 2((s)+1)-n

(-a2 - a

e -2 corank A(G(s{u}))

)

((-a2 - a ((-a2 - a
2

e -2 corank A(G(s{v }))

)

+(-a2 - a +a +(-a2 - a +a +a =
sV 2(s)-n

e -2 corank A(G(s{w }))

)

)

2((s)+2)-n

e -2 corank A(G(s{u,v }))

)

e -2 corank A(G(s{u,w }))

)

) ) )

(-a - a

e -2 corank A(G(s{v,w }))

)

2((s)+1)-n

(-a2 - a

e -2 corank A(G(s{u,v ,w }))

)

(a +a +a

2((s)+2)-n

(-a2 - a

-2 corank A(G(s))

)

2((s)+3)-n 2((s)+1)-n 2

(-a2 - a

-2 corank A(G(s{u,v ,w }))

)

((-a2 - a

-2 corank A(G(s{v }))

)

+(-a - a +a
2(s)-n

-2 corank A(G(s{w }))

)

) (2a4 +1+ a2 (-a2 - a
-2

(-a2 - a

e -2 corank A(G(s{v,w }))

)

)))

= G (a). (3) Let us consider the fourth graph-move g 4. Enumerate all vertices of G by numbers from 1 to n as follows. The number of u is 1, the number of v is 2, then we enumerate the vertices disjoint with u and v , the vertices from N (u)\N (v ), the vertices from N (v )\N (u) and the vertices from N (u) N (v ). We define the numbers of the vertices of G to be the same as the numbers of

Introduction to Graph-Link Theory

811

the corresponding vertices in G. 010 1 0 0 0 0 A0 A(G) = 1 0 A1 0 1 A2 1 1 A3 0 1 0 A(G) = 1 0 1 1 0 0 0 1 1 0 0 A0 A1 A2 A3

The adjacency matrices A(G) and A(G) are 1 0 1 0 1 1 A1 A2 A3 , A4 A5 A6 A5 A7 A8 A6 A8 A9 A1 A2 A3 , A4 A5 +(1) A6 +(1) A5 +(1) A7 A8 +(1) A6 +(1) A8 +(1) A9 1 0 0 1 1 1

where bold characters indicate row and column vectors, (1) is the matrix consisting of 1, and Aj , j = 1,... , 9, are matrices. Let s V (G)\{u, v }. It is not difficult to see that corank A(G(s)) = corank A(G(s {u, v })), corank A(G(s {u, v })) = corank A(G(s)), corank A(G(s {u})) = corank A(G(s {u})), corank A(G(s {v })) = corank A(G(s {v })), and (s) for G equals (s {u, v }) for G, (s {u, v }) for G equals (s) for G, (s {u}) for G equals (s {u}) for G, (s {v }) for G equals (s {v }) for G. Collecting the terms in the Kauffman bracket polynomial of G and G (as above), we immediately get G (a) = G (a), which completes the pro of. The following theorem describes the difference of the Kauffman bracket polynomials under g 1 graph-move. Theorem 4.6. The Kauffman bracket polynomial of a labeled graph is multiplied by (-a±3 ) under g 1 graph-move. More precisely, it is multiplied by (-a-3 ) under an addition of vertex labeled "+" and by (-a3 ) under an addition of vertex labeled "-". Pro of. The graph G is obtained from G by addition of one isolated vertex u. Enumerate all vertices of G by numbers from 1 to n, and enumerate all vertices of G by numbers from 1 to n + 1 in such a way that the number of u is 1 and the

812

D. P. Ilyutko & V. O. Manturov

number of v V (G)\{u} is i 2 if and only if the number of v in G is i - 1. The adjacency matrix A(G) is A(G) = 0 0 0 A(G) ,

where bold characters indicate row and column vectors. Let s V (G), we have corank A(G(s)) = corank A(G(s)) = corank A(G(s {u})) - 1. Suppose the label of u is "+", we get G (a) =
sV (G) e -2 corank A(G(s))

(a +a

2((s)+1)-(n+1)

(-a2 - a )

)

2(s)-(n+1)

(-a2 - a
2

e -2 corank A(G(s{u})) -2 corank A(G(s))

)
-1

=
sV (G)

a
-3

2(s)-n

(-a - a

)

(a + a

(-a2 - a

-2

))

= -a

G (a),

here (s) is equal to the sum of the vertices labeled "-" from s and of the vertices labeled "+" from V (G)\s. Suppose the label of u is "-", we get G (a) =
sV (G)

(a +a

2(s)-(n+1)

(-a2 - a

e -2 corank A(G(s))

)

2((s)+1)-(n+1)

(-a2 - a

e -2 corank A(G(s{u}))

)

)
-2

=
sV (G)

a

2(s)-n

(-a2 - a

-2 corank A(G(s))

)

(a

-1

+ a(-a2 - a

))

= -a3 G (a), here (s) is equal to the sum of the vertices labeled "-" from s and of the vertices labeled "+" from V (G)\s. This completes the pro of.

5. Graph-Knots and the Jones Polynomial In this section, we define graph-knots which are analogous to virtual knots in virtual links, and normalize the Kauffman bracket polynomial, in order to get the Jones polynomial. To normalize the Kauffman bracket polynomial to be invariant (the Jones polynomial) for the case of links (virtual links), we have to intro duce the notion of writhe number (the number of crossings of type of type minus the number of crossings ). For a knot this number does not depend on the orientation, whence

Introduction to Graph-Link Theory

813

for a link it do es depend on relative orientations of the components. Below, we define graph-knots (which correspond to usual knots -- one-component links) and define the writhe number and hence the invariant Jones polynomial. A knot is a link having one component, i.e. the set of knots is a proper subset of set of links. Lemma 5.1. Let G and G be equivalent labeled graphs modulo g 1 - g 4. Then corank(A(G)+ E ) = corank(A(G)+ E ), here E is the identity matrix. Pro of. We will use the notations as the same in Theorems 4.5 and 4.6. (1) For the first graph-move g 1 the assertion of the lemma immediately follows from the view of A(G) = 0 0 0 A(G) .

(2) Consider the second graph-move g 2. Using elementary manipulations with matrices (over Z2 ), we get 10 A(G)+ E = 0 1 aa 0 1 a 11 0 1 A(G)+ E aa 0 1 0 1 a 1 a A(G)+ E 0 a a 0 a A(G)+ E 1 0 0 0 , A(G)+ E 0

i.e. corank(A(G)+ E ) = corank(A(G)+ E ). (3) Consider the third graph-move g 3. Using elementary manipulations with matrices, we get A(G)+ E = 1 0 0 a+b 1 1 1 0 0 1 0 a 1 1 1 0 0 0 1 b (a + b) a b 1 0 1 1 1 0 0 a

01 a b B+E

0 0 B+E a+b a 0 a = A(G)+ E, b

1 b b B+E

i.e. corank(A(G)+ E ) = corank(A(G)+ E ).

814

D. P. Ilyutko & V. O. Manturov

(4) For the fourth graph-move g 4 we have, by using the elementary manipulations with matrices, A(G)+ E = 1 1 0 1 0 1 1 1 0 0 1 1 1 1 1 1 0 0 A0 + E A1 A2 A3 0 0 A0 + E A1 A2 A3 A1 A2 A3 A4 + E A5 +(1) A6 +(1) A5 +(1) A7 + E A8 +(1) A6 +(1) A8 +(1) A9 + E 0 1 1 1 0 A1 A4 + E A5 A6 0 1 A2 A5 A7 + E A8 1 1 A3 A6 A8 A9 + E , 1 0 1

00 10 01 11

i.e. corank(A(G)+ E ) = corank(A(G)+ E ), which completes the pro of. Definition 5.2. A graph-link {G} is called graph-knot if corank(A(G )+ E ) = 0 for any representative G of the graph-link. Lemma 5.1 guarantees that the notion of graph-knot is well-defined. The following definition intro duces the writhe number for a graph-knot. That number allows us to normalize the Kauffman bracket polynomial. Definition 5.3. The writhe number of a labeled graph G with corank(A(G)+ E ) = 0 is defined as follows. Enumerate all vertices of G and Bi (G) = A(G) + E + Eii (all elements of Eii except for the one in the ith column and ith row which is one are 0) for each vertex vi V (G). The writhe number w(G) of G is
n

w(G) =
i=1

(-1)cor

ank Bi (G)

sign vi .

Lemma 5.4. The writhe number is invariant under g 2 - g 4 graph-moves. Pro of. Let G be a graph and w(G) be its writhe number. Let G be a graph equivalent to G. We have corank(A(G)+ E ) = 0 (Lemma 5.1).

Introduction to Graph-Link Theory

815

We will use the notation as in Theorem 4.5. (1) Consider the second graph-move g 2. Performing the same elementary manipulation as in Lemma 5.1, we immediately have the equality of coranks of the vertices different from u and v . As
n+2

w(G) =
i=1

(-1)cor

e ank Bi (G)

sign wi
e ank B2 (G)

= (-1)cor

e ank B1 (G)

sign u +(-1)cor

sign v + w(G),

then to complete the proof in this case it is sufficient to show that corank B1 (G) = corank B2 (G). The last fact is obvious. (2) Consider the third graph-move g 3. Performing the same elementary manipulation as in Lemma 5.1, we immediately have the equality of coranks of the vertices different from u, v and w. As
n

w(G) =
i=1

(-1)cor +(-1)cor
n

e ank Bi (G)

sign ti = (-1)cor

e ank B1 (G)

sign u

e ank B2 (G)

sign v +(-1)cor

e ank B3 (G)

sign v

+
i=4

(-1)cor

e ank Bi (G)

sign ti = (-1)cor
e corank B3 (G)

e ank B1 (G)+1

+(-1) and
n

e corank B2 (G)

n

+(-1)

+
i=4

(-1)cor

ank Bi (G)

sign t

i

w(G) =
i=1

(-1)cor +(-1)cor
n

ank Bi (G)

sign ti = (-1)cor

ank B1 (G)

sign u

ank B2 (G)

sign v +(-1)cor

ank B3 (G)

sign v +(-1)cor
ank B2 (G)+1

+
i=4

(-1)cor

ank Bi (G)

sign ti = (-1)cor
n

ank B1 (G)+1

+(-1)cor

ank B3 (G)+1

+
i=4

(-1)cor

ank Bi (G)

sign ti ,

then to complete the proof in this case it is sufficient to show that corank B1 (G) = corank B1 (G), corank B2 (G) + corank B3 (G) = 1 and corank B3 (G)+ corank B2 (G) = 1.

816

D. P. Ilyutko & V. O. Manturov

Let us prove the first and second equalities. We have: (a) B1 (G) = 0 0 0 a+b 0 1 1 0 0 1 0 a 1 1 0 1 0 1 0 0 1 b (a + b) a b 0 0 0 1 1 0 1 0 1 0 a b

ab

B+E a+b a 0 a = B1 (G), b B+E

b B+E

i.e. corank B1 (G) = corank B1 (G); (b) 0 1 = det(A(G)+ E ) = det B2 (G)+det 1 0 and 1 1 1 0 a 1 0 1 0 0 b ,

b B+E ,

0 1 0 B3 (G) =

1

1 1 0

1 0 1

0 0 b

a b B+E 1 0 0 0 1 0 0 0 0 (a + b) a b B+E 0 0

0 0 0

1

0 1 0 0

0 0 0

0 0 b

b B+E 0 1 0 0 0 0 a

a+b a b 1 0 0 0 1 0 0 0

1 0 0

00 b a b B+E

00 b 0 b B+E

,

i.e. 1 = corank B3 (G)+corank B2 (G). (3) Consider the fourth graph-move g 4. Performing the same elementary manipulation as in Lemma 5.1, we immediately have the equality of coranks of the vertices different from u, v .

Introduction to Graph-Link Theory

817

As
n

w(G) =
i=1

(-1)cor +(-1)cor

e ank Bi (G)

sign wi = (-1)cor
n

e ank B1 (G)

sign u sign wi signG v

e ank B2 (G)

sign v +
i=3

(-1)cor

e ank Bi (G)

= (-1)cor
n

e ank B1 (G)+1

signG u +(-1)cor signG wi

e ank B2 (G)+1

+
i=3

(-1)cor

ank Bi (G)

and
n

w(G) =
i=1

(-1)cor +(-1)cor

ank Bi (G)

signG wi = (-1)cor
n

ank B1 (G)

signG u signG wi ,

ank B2 (G)

signG v +
i=3

(-1)cor

ank Bi (G)

then to complete the proof in this case it is sufficient to show that corank B1 (G)+ corank B1 (G) 1 (mod 2) and corank B2 (G)+ corank B2 (G) 1 (mo d 2). Let us prove only the first equality. We have: 1 = det(A(G)+ E ) 1 1 0 1 0 1 0 1 0 0 1 1 0 0 A0 + E A1 A2 A3 0 0 A1 A4 + E A5 A6 0 1 A2 A5 A7 + E A8 0 1 A3 A6 A8 A9 + E ,

= det B1 (G)+det and B1 (G) =

0 1 0 0 1 1

1 1 0 1 0 1 0 1 0 0 1 1

0 0 A0 + E A1 A2 A3 1 1 0 1 0 1 0 0 A0 + A1 A2 A3

0 1 1 1 0 1 A1 A2 A3 A4 + E A5 +(1) A6 +(1) A5 +(1) A7 + E A8 +(1) A6 +(1) A8 +(1) A9 + E 0 0 0 0 1 1 E A1 A2 A3 , A4 + E A5 A6 A5 A7 + E A8 A6 A8 A9 + E

i.e. corank B1 (G)+corank B1 (G) 1 (mod 2), which completes the pro of.

818

D. P. Ilyutko & V. O. Manturov

The following lemma is evident. Lemma 5.5. The writhe number is changed by (±1) under g 1 graph-move. More precisely, it is changed by (-1) under an addition of vertex labeled "+" and by (+1) under an addition of vertex labeled "-". Definition 5.6. Let G be a graph-knot. Define the Jones polynomial as X (G) = (-a)-3w(G) G (a). Theorems 4.5, 4.6 and Lemmas 5.4, 5.5 immediately yield Theorem 5.7. The Jones polynomial X (G) is an invariant of graph-knots. 6. Minimal Representatives of Graph-Links One of the important problems in classical knot theory is to establish minimal crossing number of a certain link. In late 19's century, famous physicist and knot tabulator Tait [26] conjectured that alternating prime diagrams of classical links are minimal with respect to the number of classical crossings. This celebrated conjecture was solved only in 1987, after the notions of the Jones polynomial and the Kauffman bracket polynomial appeared. The first solution was obtained by Murasugi [27], then it was reproved by Thistlethwaite [28], Turaev [9], and others. Later, Thistlethwaite [29] established the minimality for a larger class of diagrams (socalled adequate diagrams). It turns out that many results in these directions generalize for virtual links (establishing the minimal number of classical crossings); these results were obtained by the second named author of the present paper. See [11] for the pro ofs and some further generalizations and other results concerning virtual knots. Definition 6.1. The difference between the leading degree and the lowest degree of non-zero terms of a polynomial P (x) is called the span of P (x) and is denoted by span P (x). The main reason of these minimality theorems and further crossing estimates come from the well-known KauffmanMurasugiThistlethwaite Theorem: Theorem 6.2. For a non-split classical link diagram K on n crossings we have span K 4n, whence for alternating non-split diagrams we have span K = 4n. Note that the span of the Kauffman bracket is invariant under all Reidemeister moves. In [11], this theorem is generalized for virtual diagrams. The estimate span K 4n can be sharpened to span K 4n - 4g , where g is the genus of the atom. A nice way to reprove the latter estimate can be also found in [30], where the authors interpreted atoms as a mo dification of Grothendieck's dessins d'enfant.

Introduction to Graph-Link Theory

819

In the present section, we establish minimality of graph-link representatives. We call a labeled graph G minimal if there is no representative of the graph-link corresponding to G having strictly smaller number of vertices than G has. Definition 6.3. A classical link diagram is called alternating if while passing along every component of it we alternate undercrossings and overcrossings. From the "atomic" point of view, alternating link diagrams are those having atom genus (Turaev genus) 0 (more precisely, diagram has genus 0 if it is a connected sum of several alternating diagrams). For virtual links, we have a notion of quasi-alternating diagram [11]: these are precisely diagrams obtained from classical alternating diagrams by (detours and) virtualizations. Definition 6.4. A virtual link diagram D is called split if there is a vertex X of the corresponding atom (M, ) such that \X is disconnected. Now, let us generalize the notions defined above for the case of graph-links. Definition 6.5. A labeled graph G on n vertices is alternating if k + l = n +2, where k is the number of circles in the A-state s1 , i.e. k = corank A(G(s1 )) + 1, and l is the number of circles in the B -state s2 of G, i.e. l = corank A(G(s2 )) + 1. Definition 6.6. A labeled graph G is adequate if the number of circles k in the A-state is lo cally minimal, that is, there is no neighboring state for the A-state with k + 1 circles, and the same is true for the number of circles l in the B -state. Remark 6.7. This definition of the adequate diagram generalizes (see, e.g. [29]) the classical definition of the adequate diagram: neither circle of the A-state nor the B -state splits into a pair of circles after one resmo othing. Definition 6.8. A labeled graph G is non-split if it has no isolated vertices. Definition 6.9. For a labeled graph G let the atom genus (Turaev genus) be 1 - (k + l - n)/2, where k and l are the numbers of circles in the A-state and the B -state of G, respectively. Note that this number agrees with the atom genus in the usual case: we just use = 2 - 2g , where is the Euler characteristic, and count by using the number of crossings n, number of edges 2n and the number of 2-cells (A-state circles and B -state circles). Lemma 6.10. For any graph G on n vertices we have span G 4n - 4g (G), here g (G) is the genus of the corresponding atom. Pro of. Indeed, the assertion of this lemma comes from the definition of the Kauffman bracket and the atom genus. Denote the number of circles in the A-state of G

820

D. P. Ilyutko & V. O. Manturov

by k , and denote the number of circles in the B -state of G by l. Then the leading term of the Kauffman bracket coming from the A-state has degree n +2(k - 1), and the lowest term coming from the B -state has degree -n - 2(l - 1). Now, it remains to see that no other state can give a term of degree strictly greater than that of the A-state. Similarly, no state contributes a term of degree strictly smaller than that of the B -state and the inequality follows. Lemma 6.11. For an adequate labeled graph G on n vertices we have span G = 4n - 4g (G), here g (G) is the genus of the corresponding atom. Pro of. Indeed, it is sufficient to check that the leading term coming from the A-state of G is not canceled by any other term coming from another state (the argument for the lowest term coming from the B -state is the same). To do that, let us consider the term a(s)- (s) (-a2 ) (s)-1 for a state s. For the A-state, we have = n, = 0, = k . If we switch one crossing to the B smo othing, then is decreased by 1, is increased by 1 and hence the degree of a- is decreased by two. We may compensate this only if the "number of circles" (s) (or the corresponding corank A(G(s)) + 1) is increased by 1. This may happen only if there is a state s adjacent to the A-state with corank A(G(s)) + 1 = k +1. Thus, the diagram is inadequate. Lemma 6.12. An alternating labeled graph G is adequate if and only if it has no isolated vertices. Pro of. The direction is obvious. Now, assume that the diagram G is inadequate, alternating and has no isolated vertices. Denote the number of circles of the A-state by k , and that of the B -state by l. Without loss of generality, assume that there is a state A with (n - 1) A-smoothings and one B -smo othing with number of circles equal to (k + 1). Consider the opposite state B . Obviously, the number of circles in this state is l - 1 (the total number can not exceed k + l). Denote the vertex of G where the A-state differs from A by X . Thus, the labeled graph G obtained by changing the label of the X has genus 0, too. Since G is alternating, all single-circle states are at the same distance from the A-state. On the other hand, all single-circle states are at the same distance from A . This means that these single-circle states (as subsets of {1,... ,n}) either both contain X or both do not contain X . Assume they all contain X . We argue that X is an isolated vertex. Indeed, if there were a vertex Y connected to X then, starting from a single-circle state containing X and changing it at X and Y , we would get another single-circle state not containing X . This completes the proof.

Introduction to Graph-Link Theory

821

Lemmas 6.106.12 together yield the following Theorem 6.13. Let G be an alternating labeled graph without isolated vertex. Then it is minimal, that is, there is no graph G with strictly smal ler number of vertices representing the same graph-link as G. Pro of. Assume the contrary. Then, we have 4n = span G = span G 4n - 4g (G ), where n is the number crossings of G , and g (G ) is the atom genus (Turaev genus) of G . The inequality n < n leads to a contradiction, which completes the pro of. Classical links are represented by d-diagrams; alternating links are represented by those d-diagrams where all chords of one family have sign "+" and all chords of the other family have sign "-". At the level of graphs, d-diagrams are bipartite graphs. Definition 6.14. We call any bipartite graph with arbitrary labeling pseudoclassical. It is easy to see that a labeled graph is alternating if and only if it is pseudoclassical, and all labels of one subset of disjoint vertices are "+" and all labels of the complement subset of vertices (which are pairwise disjoint as well) are "-". Example 6.15. Consider the graph BW3 consisting of the 7 vertices with the following incidences. For i, j = 1,... , 6, i is connected to j if and only if i - j ±1 (mo d 6), and 7 is connected to 2, 4, 6. Label all even vertices by "+", and label all o dd vertices by "-", see Fig. 16. This graph is alternating. By Theorem 6.13, BW3 is minimal. Note that this graph is not realizable as an intersection graph of a chord diagram, see [25]. We conjecture that the graph-link represented by BW3 has no "realizable" representatives which correspond to classical or virtual diagrams via chord diagrams. At least we know that it has no such representatives with the number of crossings less than or equal to 7.

2 + 1+ 6
Fig. 16.

3 7 5
The graph BW3 .

+4

822

D. P. Ilyutko & V. O. Manturov

Acknowledgments The authors are grateful to L. H. Kauffman, V. A. Vassiliev, A. T. Fomenko and L. Traldi for their interest to this work. The first named author was partially supported by grants of RF President NSh 660.2008.1, RFFI 070100648, RNP 2.1.1.7988.

References
[1] L. H. Kauffman, Virtual knot theory, European J. Combin. 20(7) (1999) 662690. [2] V. O. Manturov, Khovanov homology of virtual knots with arbitrary coefficients, Russ. Acad. Sci. Math. Izvestiya. 71(5) (2007) 967999. [3] R. A. Fenn, L. H. Kauffman and V. O. Manturov, Virtual knots -- unsolved problems, Fund. Math. 188 (2006) 293323. [4] L. Traldi and L. Zulli, A bracket p olynomial for graphs, preprint, arxiv.math: GT/0808.3392. [5] V. O. Manturov, Emb eddings of four-valent framed graphs into 2-surfaces, preprint, arxiv.math: GT/0804.4245 [6] S. Wehrli, Khovanov homology and Conway mutations, preprint, arxiv.math: GT/0301312. [7] D. P. Ilyutko and V. O. Manturov, Graph-link theory, to app ear in Doklady Math. [8] A. T. Fomenko, The theory of multidimensional integrable hamiltonian systems (with arbitrary many degrees of freedom). Molecular table of all integrable systems with two degrees of freedom, Adv. Sov. Math. 6 (1991) 135. [9] V. Turaev, A simple proof of the Murasugi and Kauffman theorems on alternating links, Enseign. Math. 33 (1987) 203225. [10] V. O. Manturov, Bifurcations, atoms, and knots, Moscow Univ. Math. Bul l. 1 (2000) 38. [11] V. O. Manturov, Teoriya Uzlov (Knot Theory) (Moscow-Izhevsk, RCD, 2005). [12] M. Khovanov, A categorification of the Jones p olynomial, Duke Math. J. 101 (3) (1997) 359426. [13] M. Khovanov and L. Rozansky, Matrix factorizations and link homology, preprint, arxiv.math: GT/0401268. [14] M. Khovanov and L. Rozansky, Matrix factorizations and link homology I I, preprint, arxiv.math: GT/050506. [15] M. Goussarov, M. Polyak and O. Viro, Finite typ e invariants of classcial and virtual knots, Topology. 39 (2000) 10451068. [16] N. Kamada and S. Kamada, Abstract link diagrams and virtual knots, J. Knot Theory Ramifications 9 (2000) 93106 [17] S. V. Chmutov, S. V. Duzhin and S. K. Lando, Vassiliev Knot Invariants. I, I I, I I I, Adv. Sov. Math. 21 (1994) 117147. [18] G. Kup erb erg, What is a virtual link? Algebr. Geom. Topol. 3(5) (2003) 87591; arxiv.math: GT/0208039. [19] T. Ohtsuki, Quantum Invariants, A Study of Knots, 3-Manifolds, and Their Sets (World Scientific, Singap ore, 2002). [20] E. Sob oleva, Vassiliev knot invariants coming from Lie algebras and 4-invariants, J. Knot Theory Ramifications 10(1) (2001) 161169. [21] D. BarNatan and S. Garoufalidis, On the Melvin-Morton-Rozansky conjecture , Inv. Math. 125 (1996) 103133.

Introduction to Graph-Link Theory

823

[22] L. H. Kauffman, State models and the Jones p olynomial, Topology 26 (1987) 395407. [23] V. F. R. Jones, A p olynomial invariant for links via Neumann algebras, Bul l. Amer. Math. Soc. 129 (1985) 103112. [24] S. K. Lando, J -invariants of ornaments and framed chord diagrams, Funct. Anal. Appl. 40(1) (2006) 113. [25] A. Bouchet, Circle graph obstructions, J. Combin. Theory B 60 (1994) 107144. [26] P. G. Tait, On knots, Scientific Paper I (Cambridge University Press, London, 1898), pp. 273317. [27] K. Murasugi, The Jones p olynomial and classical conjectures in knot theory, Topology 26 (1987) 187194. [28] M. B. Thistlethwaite, Kauffman p olynomial and alternating links, Topology 27 (1988) 311-318 [29] M. B. Thistlethwaite, On the Kauffman p olynomial of an adequate link, Invent. Math. 93(2) (1988) 285296. [30] O. Dasbach, D. Futer, E. Kalfagianni, X.-S. Lin and N. Stoltzfus, The Jones p olynomial and graphs on surfaces, J. Combin. Theory B 98(2) (2008) 384399.