An Introduction To Virtual Spatial Graph Theory

1. Introduction

The mathematical theory of knots studies the many ways a single loop can be tangled up in space. Since many biological molecules, such as DNA, often form loops, knot theory has been applied to biological systems with good effect. However, many biological molecules form far more complicated shapes than simple loops; proteins, for example, often contain extensive crosslinking between cystine residues, and hence from the mathematical viewpoint are far more complicated structures–spatial graphs. The study of graphs embedded in space is known as spatial graph theory, and researchers such as Flapan have obtained good results by applying it to chemical problems. However, in biological systems, proteins are often associated with membranes, meaning that some portions of the molecule are prevented from interacting with others. In the case of a simple loop, the virtual knot theory of Kauffman provides a mathematical framework for studying such systems, as it allows some crossings of strands to be labeled “virtual,” i.e. non-interacting. We hope that a merging of these two theories, called virtual spatial graph theory, will prove equally useful in the biological sciences. Knot theory studies embeddings of circles up to isotopy. There are many ways to extend the ideas of knot theory; two natural choices are the study of spatial graphs and the theory of virtual knots. The theory of spatial graphs generalizes the objects we embed, by studying isotopy classes of arbitrary graphs embedded in S3. The theory of virtual knots is quite different–it generalizes the idea of an embedding. Knots and links can be studied by projecting the embedding into a plane, but retaining information about over- and under-crossings. These knot diagrams are then taken up to an equivalence defined by Reidemeister moves. Virtual knot theory simply allows a third type of crossing, a “virtual” crossing, and introduces new Reidemeister moves which determine how this type of crossing behaves. Virtual knot theory then studies these virtual knot diagrams up to equivalence under the full set of Reidemeister moves. These two generalizations of knot theory move in very different directions.
It is our intention to find a unified approach.

Naturally, spatial graphs may be studied by examining their diagrams, and by introducing virtual crossings and new Reidemeister moves, we may define virtual spatial graphs. A virtual spatial graph is an immersion of a graph G into the plane, with crossings labeled over, under, or virtual. These diagrams are taken up to the equivalence relation generated by the Reidemeister moves of Figures 1 and 2. Many invariants of both virtual knots and spatial graphs may be extended to these new objects.
A knot can be described by the Gauss code of its projection–the sequence that records the order the crossings are met as we traverse the knot diagram. However, there are many more such sequences than there are real knots; those that correspond to classical knots are known as “realizable” codes. One motivation for virtual knots is that they provide realizations for the Gauss codes that do not correspond to classical graphs. A similar motivation for the study of virtual spatial graphs comes from the Gauss code of a diagram for a spatial graph. The Gauss code for a spatial graph simply records the sequence of crossings along each edge of the graph. Again, not every such code corresponds to a classical spatial graph, but any such code corresponds to some virtual spatial graph.
Another motivation for virtual spatial graph theory is that it can give insights into classical problems in topological graph theory. In Section 4 we will use virtual spatial graph theory to produce a filtration on the set of intrinsically linked graphs. Sachs, and Conway and Gordon proved that every embedding of K6 into S3 contains a non-split link [16, 1]. A graph with this property is called intrinsically linked, and these graphs have been extensively studied. Given two such graphs, one might want to compare their “linkedness.” One measure of this property might be the minimum number of links contained in any spatial embedding. For example, there is an embedding of K6 which contains exactly one non-split link, but every embedding of K4,4 contains at least two non-split links. However, both K6 and the Petersen graph have embeddings with exactly one link. Yet, in a certain sense, K6 is more linked than the Petersen graph. That is, we say a graph G is n-intrinsically virtually linked (n-IVL) if every virtual spatial graph diagram of G with n or fewer virtual crossings contains a nonsplit virtual link. This produces a filtration of the set of intrinsically linked graphs, and the deeper in the filtration a graph persists, the more “linked” the graph is.
Virtual spatial graph theory is relatively new, and many aspects of the theory are in early stages of development.
Thus, there are many accessible open problems and questions in this field, and we hope it remains an active area of research for some time.

2 .Virtual Spatial Graphs

We will use a combinatorial definition of virtual spatial graphs. A graph is a set of vertices V and a set of edges E _ V × V . Unless otherwise stated, we will consider vertex-oriented and directed graphs, so that each edge is an ordered pair of vertices. A spatial graph is an embedding of G in S3 that maps the vertices to points and an edge (u, v) to an arc whose endpoints are the images of the vertices u and v, and that is oriented from u to v. We will consider these embedding’s up to ambient isotropy. We can always represent such an embedding by projecting it to a plane so that each vertex neighbourhood is a collection of rays with one end at the vertex and crossings of edges of the graph are transverse double points in the interior of the edges.
Kauffman and Yamada have shown that ambient isotropy of spatial graphs is generated by a set of local moves on these diagrams which generalize the Reidemeister moves for knots and links. These Reidemeister moves for graphs are shown in Figure 1.
A virtual graph diagram is a classical graph diagram, with the addition of virtual crossings. The idea is that the virtual crossings are not really there (hence the name “virtual”). To make sense of this, we extend our set of Reidemeister moves for graphs to include moves with virtual crossings. We need to introduce five more moves, (I*) - (V*), shown in Figure 2. Notice that moves (I*) - (IV*) are just the purely virtual versions of moves (I) - (IV); move (V*) is the only move which combines classical and virtual crossings (in fact, there are two versions of the move, since the classical crossing may be either positive or negative).
There are also three moves which, while they might seem reasonable, are not allowed. These forbidden moves are shown in Figure 3.

2.1. Forbidden Moves

If we allow the forbidden moves in Figure 3, then many more virtual graph diagrams become equivalent. In the case of knots, allowing move (VIII*) trivializes the theory, and all virtual knots become trivial [10, 13]. However, when we look at virtual links or virtual graph diagrams, the effect is not quite so drastic. The following proposition shows that the forbidden moves do not trivialize virtual graph theory, as they do virtual knot theory.

Proposition 1 There are virtual graph diagrams (of a connected graph) which are not equivalent modulo the forbidden moves.
We use the virtual spatial graph invariant T (G), defined in Section 2.2 below. The pairwise linking numbers for all the links in T (G) can be computed by using the Gauss formula ( 12 (number of positive crossings) – 12 (number of negative crossings)). If the links are virtual, these linking numbers may be half-integers, but they are still invariant under all the classical and virtual Reidemeister moves and the forbidden moves (VI*), (VII*) and (VIII*).
The two virtual graph diagrams on the right in Figure 4 have links in T (G) with different linking numbers, and so the diagrams are inequivalent, even allowing the forbidden moves.

2.2. Invariants of Virtual Spatial Graphs

Kauffman introduced a topological invariant of a spatial graph defined as the collection of all knots and links formed by a local replacement at each vertex of the graph. Each local replacement joins two of the edges incident to the vertex and leaves the other edges as free ends (i.e. creates new vertices of degree one at the end of each of the other edges). Choosing a replacement at each vertex of a graph G creates a link L(G) (after erasing all unknotted arcs). T (G) is the collection of all links L(G) for all possible choices of replacements.
For virtual graphs, we can define T (G) in exactly the same way, except that it is now a collection of virtual links. Examples are shown in Figure 4.
The fundamental group of a classical knot or spatial graph is the fundamental group of its complement in S3. Given a diagram for the knot or graph, this group can be calculated using the Wirtinger presentation.

Kauffman defined the fundamental group of a virtual knot by modifying the Wirtinger presentation for classical knots. We define the fundamental group of a virtual spatial graph in the same way, by modifying the Wirtinger presentation for classical spatial graphs. Note that for a classical spatial graph, this modified calculation still produces the usual fundamental group. The quandle is a combinatorial knot invariant introduced by Joyce , that was generalized to virtual knots by Kauffman, and strengthed by Manturov . Modifying Manturov’s approach, we can construct a similar invariant for virtual spatial graphs, though for general graphs this invariant is less potent than in the case of knots. Information about the embedding is encoded by relations generated by the crossings and vertices. Yamada introduced a polynomial invariant R of spatial graphs in . Using skein relations, R(G) can be computed by reducing the graph G to a bouquet of circles, where a (classical) trivial bouquet of n circles has Y (B(n)) = −(−_)n. In the case of virtual spatial graphs we can use exactly the same skein relations to compute R(G), simply by ignoring virtual crossings. The only difference is that we may end up with a virtual bouquet–a bouquet of circles with only virtual crossings. If G is a virtual bouquet of n circles, we simply define R(G) = R(Bn) = −(−_)n. This gives a virtual graph diagram invariant. It is easy to find nontrivial virtual graph diagrams of planar graphs with trivial Yamada polynomial.

3. Gauss Codes

It is easiest to associate a Gauss code to an immersion of a closed curve (or graph) in the plane, so we first study the shadow of our graph diagram, where the over/under information at the crossings is ignored. Figure 5 illustrates the Gauss code for such a shadow. To produce the Gauss code for the original diagram, we augment the Gauss code for its shadow by recording whether each crossing is an over-crossing or an under-crossing. If the graph is directed, we can also label each crossing by its sign.
An important problem in the study of Gauss codes is to find algorithms for determining whether a Gauss code is realizable, that is, the Gauss code of a classical embedding. For closed curves, there are several algorithms [2, 3, 14]; these methods can be generalized to arbitrary graphs.
Given a Gauss code S for an abstract graph G, there is a split code S_ produced in a similar manner as when studying Gauss codes for a knot. However, in this process one must also alter the graph G to produce a chord diagram on a split graph G_. That is, given a Gauss code S on G, we may label each edge of G with a sequence of symbols. When splitting S at symbol b, we cut the edges of G at the labels b and then reconnect them to produce a connected graph. We also add a chord running from one instance of B to the other.
Theorem 1 Let S be a Gauss code for an abstract connected graph G, with split code S_ and split graph G_.
Then S is realizable by a classical spatial graph embedding if and only if G_ is planar, and the embedding of G_ determined by S_ can be extended to an embedding of the corresponding chord diagram.
Perhaps surprisingly, checking the conditions of Theorem 1 is computationally easy.

Proposition 2 Given a Gauss Code S on a connected graph G, there is a polynomial time algorithm to determine whether S is realizable by a classical embedding of G.
This algorithm and a proof of Theorem 1 are discussed in.
Virtual graph diagrams also have Gauss codes, produced in exactly the same way, except that virtual crossings are ignored. As Theorem 2 shows, one motivation for studying virtual graph diagrams is that they allow us to realize the “unrealizable” Gauss codes.
Theorem 2 Every Gauss code can be realized as the code for a virtual graph diagram.
Much as for virtual knots, if a virtual spatial graph diagram has a realizable Gauss code, then that diagram is equivalent to a classical diagram. The proofs of Theorems 2 and 3 are similar to those for the analogous results for virtual knots.
Theorem 3 If two virtual graph diagrams have the same Gauss code, then they are virtually equivalent.
Corollary 1 If a virtual graph diagram has a realizable Gauss code, then it is virtually equivalent to a classical graph diagram.
The inclusion of knot theory into virtual knot theory is known to be injective. It is not yet known if the same is true for the inclusion of spatial graph theory into virtual spatial graph theory.
Conjecture 1 If two classical spatial graphs are virtually equivalent, then they are classically equivalent.

4. Intrinsically Virtually Linked Graphs

A graph G is called intrinsically virtually linked of degree n (n-IVL) if every virtual diagram of G with at most n virtual crossings contains a non-trivial virtual link whose components are disjoint cycles in G. Let IV Ln denote the set of graphs that are intrinsically virtually linked of degree n. We may define intrinsically virtually knotted of degree n and IV Kn in the same way. These definitions give rise to the natural filtrations below. Note that IV L0 (IV K0) is simply the set of classically intrinsically linked (knotted) graphs, so the filtration provides information about this classical problem.

IV L0 = IV L1 ) IV L2 ) IV L3 ) IV L4 ) . . .
IV K0 _ IV K1 ) IV K2 _ IV K3 ) IV K4 _ . . .
It is relatively easy to produce examples that show the filtrations are decreasing in the manner shown, but the equality IV L0 = IV L1 is somewhat surprising.
Theorem 4 If G is intrinsically linked, then G is also intrinsically virtually linked of degree 1, so IV L0 = IV L1.
The proof of Theorem 4 relies on the fact that every embedding of every intrinsically linked graph contains a non-split link with odd linking number, and that the half-integer linking number is an invariant for virtual links.

Every intrinsically linked graph contains one of the Petersen graphs as a minor. That is, the Petersen family, shown in Figure 6, is the minor minimal set for intrinsic linking. We have classified the Petersen family of graphs with respect to the filtration, and clearly all are 1-IVL. Embeddings of G8, G9 and P with two virtual crossings that contain no nontrivial links are shown in Figure 7, and hence are not 2-IVL. The graphs K6, K3,3,1, K4,4 \e and G7 are 2-IVL, but not 3-IVL. These graphs are minor minimal for intrinsic linking, so they are minor minimal with respect to intrinsic virtual linking of degree 2. However, the full set of minor minimal graphs for intrinsic virtual linking of degree 2 is not yet known.
If a knot has non-trivial Jones polynomial, then converting a single classical crossing in any projection of that knot to a virtual crossing gives a non-trivial virtual knot [7]. Since every embedding of every known intrinsically knotted graph contains a knot with non-trivial Jones polynomial, all known 0-IVK graphs are 1-IVK. Indeed, we conjecture that IVK0 = IV K1. To further study this conjecture, as well as understand intrinsic virtual knotting, we introduce the notion of virtual unknotting number.
Given a diagram D of a virtual knot K, define vuD(K) to be the minimum number of classical crossings in D which need to be virtualized in order to unknot K. The virtual unknotting number of K vu(K) is the minimum of {vuD(K)}, taken over all diagrams D for K. We have been able to determine the virtual unknotting number for certain knots.
Theorem 5 The virtual unknotting number of any twist knot is 2.
The virtual unknotting number may be related in some way to the classical unknotting number, but this is not yet understood. In this area, as with all of virtual spatial graph theory, many open problems remain.