A New Family Satisfying the Intersection Graph Conjecture

Year: 2018 Authors: Ally K. Stacey

Core claim

A generalized four-term relation shows a family of chord diagrams, including necklaces of triangles, satisfies the Intersection Graph Conjecture.

Topics

intersection graphs, chord diagrams, four-term relation, Vassiliev knot invariants

Domains

graph theory, knot theory, combinatorics, invariant theory, mathematical art, visualization, drawing, artistic exploration

Methods

generalized four-term relation, inductive proof, diagrammatic analysis, visual experimentation

Media

hand-drawn artwork, chord diagrams, intersection graph diagrams, color-coded illustrations

Paper text

The text below is the locally extracted OCR/Markdown version of the paper. Raw PDF files remain local and are not published here.

Bridges 2018 Conference Proceedings

A New Family Satisfying the Intersection Graph Conjecture

Ally K. Stacey

Department of Mathematics, Oregon State University; staceyal@oregonstate.edu

Abstract

A chord diagram is a degree three graph with a designated outer circle. It looks like a circle with lines going across it. The intersection graph of a chord diagram is a graph that shows how the lines inside the circle cross each other. Many chord diagrams can share an intersection graph. The intersection graph conjecture asks, “If two chord diagrams share an intersection graph are they equal for a sense of equality of chord diagrams?” I found a new family of intersection graphs for which the answer to this question is “yes.” I have included some artwork that I produced while discovering this result.

Background

In this paper, I share a result that was aided by artistic exploration I engaged in while working on the problem. As I will explain, a drawing I made while exploring properties of chord diagrams helped me to articulate and prove a theorem involving intersection graphs. Figure 1 depicts such artwork I made in pursuit of the theorem I will present in this paper. In order to share the result I first present some initial definitions and ideas. To read more about the background information, Introduction to Vassiliev Knot Invariants by Chumtov, Duzhin, and Mostovoy [3] is a solid book on the topic.

(a) “2 Loops 1”.

(b) “2 Loops 2”. Figure 1: Two art pieces I created to study the theorem presented in this paper.

In the study of Vassiliev knot invariants, chord diagrams are of key interest. The invariants are properties that do not change for “equal” knots. I focus especially on singular knots, which are knots with finitely many arbitrarily fused crossings. These fused crossings are a single point rather than two separate points in three-space. Figure 2 (a) depicts a fused crossing and Figure 2 (b) depicts a non-fused crossing, where the knot outside the dotted lines can be any knot. Only the order in which the double points occur is important for these invariants, not the non-fused crossings. Chord diagrams are useful representations for thinking about singular knots. Figure 2 (c) and (d) show a singular knot with its chord diagram. A chord diagram is a degree

Stacey

Figure 2: Fused and non fused crossings and a singular knot with its chord diagram.

three graph, (a graph where all the vertices have three edges), with a designated outer circle that represents the order in which the double points occur on a singular knot. It is created by starting at a double point and placing a vertex on the circle. Label this point 1. Travel clockwise along the knot, place a vertex on the circle every time you encounter a double point, and label it. If you encounter a double point for the second time keep the label the same. Once you get back to your starting point, place edges inside the circle connecting the two occurrences of each double point. The edges inside the circle are called chords, hence the name “chord diagram.”

Next, I will discuss the four-term relation, which is the fundamental notion of equivalence that was important in my work. Essentially, the four-term relation allows me to express one chord diagram as a combination (sum and difference) of three other chord diagrams. It is called the four-term relation since it involves four chord diagrams. Consider the formal vector space of all chord diagrams with $n$ chords over the field of rational numbers. The four-term relation is an equivalence relation on this space, defined schematically in Figure 3.

In the example in Figure 3 (b), the chords involved in the relation are depicted as gray and the other chords are depicted in black. In the example in Figure 3 (b), the moving lighter gray chord is in a different position with respect the stationary darker gray chord in all four chord diagrams.

The general statement of the four-term relation shows equivalence between two different differences of particular chord diagrams (Figure 3 (a)). For my purposes I tend to use the relation to express one chord diagram in terms of three other diagrams (Figure 3 (b)), so that they satisfy the relation. I have labeled the chord diagrams involved in the example A,B,C,and D for reference. In the example some of the chord diagrams can be combined but I have declined to combine them for the sake of illustration. In particular, in Figure 3 (c), we see that I can express chord diagram B as A - C + D. In this way, I can leverage this relation in order to simplify work with chord diagrams. This relation is invariant under rotating the chord diagram.

Figure 3: The four-term relation.

A New Family Satisfying the Intersection Graph Conjecture

(a)

(b)

(c) Figure 4: A share and the generalized four-term relation.

Our next important concept is that of a share. A share is a set of chords and a division of the circle into four arcs so that no chord ends on adjacent arcs. That is, the endpoints of the demarcation of circle into arcs is part of the share. The two sets of arcs opposite each other partition the chords into two sets, the share and its complement. The complement of a share is also a share. Figure 4 (a) and 4 (b) show an example of a share with a non-example. In Figure 4 (a), the light gray chords form a share since all of the gray chord endpoints are in the top and bottom highlighted arcs. In the non-example in Figure 4 (b), the set of chords highlighted in light gray does not form a share since the bolded chord intersects the light gray chords. I marked and highlighted the four arcs involved with the top and bottom arcs containing the light gray chords, but the bolded chord touches with its left endpoint a black arc and a highlighted arc with its right endpoint, making the light gray chords not a share. For the chord diagram in Figure 4 (b), the bolded chord needs to be included with the light gray chords in the non-example to form a share.

Chumtov, Dunzhin, and Lando [1] proved that for any share we can generalize the four-term relation as shown in Figure 4 (b). The proof relies on there being only a single chord and a share and so we can have any single chord participate with a share. This will be referred to as the generalized four term relation.

The intersection graph of a chord diagram is a graph whose vertices represent the chords and an edge between vertices whenever the corresponding chords intersect. Every chord diagram has a unique intersection graph, but different chord diagrams can have the same intersection graph. Figure 5 depicts a chord diagram (a) with its intersection graph (b). For example, chords 2, 3, and 5 in the figure form a triangle because they all mutually intersect.

(a) Figure 5: A chord diagram with its intersection graph.

(b)

The Intersection Graph Conjecture

The big concept I am interested in regarding intersection graphs is a statement called the Intersection Graph Conjecture. Trying to solve this conjecture has been a major inspiration for many art pieces I have made.

Stacey

Given that these intersection graphs with their chord diagrams are interesting to draw and look at, it is perhaps not surprising I started making artwork involving them.

The Intersection Graph Conjecture: [3] If $D_1$ and $D_2$ are two chord diagrams with the same intersection graph, they are equal in the sense of the four-term relation.

This conjecture is false in general but is true in any of the following situations:

a) For all diagrams with up to 10 chords [2], [5], b) When the intersection graph is a tree [1], c) When the intersection graph contains a single loop (in other words a single cycle in the graph) [4].

This conjecture will be shown to be true in one more case discussed in this paper.

For the purposes of this paper I will use the word “tree” in the context of a chord diagram to mean a set of chords whose intersection graph restricted to this set of chords is a tree. Similarly a “loop” inside a chord diagram will be a set of chords such that the intersection graph restricted to these chords forms a cycle.

An Artistic Approach to a New Case

The Intersection Graph Conjecture is known to be true in the case of one loop, so I wanted to explore the case of two loops. I learn best by making artistic examples and then looking for patterns. The two art pieces in Figures 1 (a) and 1 (b) depict what I thought of as the first two cases of two loops. The graph depicted in Figure 1 (a) has the two loops separated by a single vertex and the graph depicted in Figure 1 (b) has the two loops separated by a more complicated set of vertices forming a tree.

In each figure there are eleven unique chord diagrams, having a common intersection graph, which are drawn as the vertices of that graph. The two sets, each with eleven chord diagrams realizing the intersection graph, were the ones I happened to use and are not necessarily the only eleven chord diagrams with these graphs. I have used color to highlight relationships. For example, the border for each circle representing a vertex in the intersection graph is drawn with the same color used to draw the corresponding chord in each of the chord diagrams. Edges in the intersection diagram are colored with a combination of all vertex colors in the cycle.

(a) “Mirror Image Proof”.

(b) “Necklace of Triangles”. Figure 6: Two art pieces depicting my mirror image proof and an example of a necklace of triangles

A New Family Satisfying the Intersection Graph Conjecture

To approach the Intersection Graph Conjecture, I decided to see if I could make the center chord diagram in “2 Loops 1” equal its mirror image. The art piece in Figure 6 (a) shows a proof that this diagram is equal to its mirror image. This exploration of mirror equality inspired me to propose Theorem 1. The share and chord involved in the generalized four term relation are depicted in red and green respectively. Going from a shade of purple to a shade of yellow indicates a change to the mirror image of the chord diagram above it. The chord diagram on the left has an intersection graph with two loops, but the three on the right only have one loop. The four term relation says that the diagram on the left equals a sum and difference of the diagrams on the right, so if the Intersection Graph Conjecture applies to the diagrams on the right, it must do so for the diagram on the left. I then concluded that this proves the diagram on the left equals its mirror image, but I had actually proven something stronger.

The Theorem

The properties I used in my mirror image proof are generalized in the following theorem.

Theorem 1: The intersection graph conjecture holds for two diagrams sharing an intersection graph with two loops such that a) one of the two loops is a triangle and b) the two loops are separated by a tree.

Proof: Consider the generalized four-term relation depicted in Figure 7. The corresponding intersection graphs for each chord diagram in the relation are depicted below each chord diagram. The share interacting with the moving chord is the dashed group labeled “tree” and the arcs corresponding to this share have been highlighted. In the diagram on the left of the equality, the loop forming a triangle is the colored moving chord intersecting the two trees on the left. The other loop is labeled “1 loop” and intersects the bolded chord once. As a result, the tree attached to the bolded chord along with the bolded chord forms a tree that separates the loops. The three diagrams on the right hand side of the equation are diagrams with a single loop, the section marked “1 loop”, to which the intersection graph conjecture applies, as proven by [4]. Therefore, it must also apply to the diagram on the left hand side. $\square$

Figure 7: The four-term relation in Theorem 1.

I developed the term a necklace of triangles to denote a chord diagram with an intersection graph that has finitely many loops in a chain separated by trees such that only the loop at the end of the chain is not a triangle. Figure 8 depicts the general idea of the intersection graph of a necklace of triangles.

Corollary: The intersection graph conjecture is true for a necklace of triangles.

Proof: The proof is by induction on the number of triangles in the graph.

Base case: There is only 1 triangle and 1 other loop. This is exactly the case in Theorem 1.

Stacey

Figure 8: The general form of the intersection graph of a necklace of triangles.

Now suppose the intersection graph conjecture is true whenever we have $n$ triangles in the necklace. Consider a necklace of $n+1$ triangles. Then apply the four term relation in Theorem 1. Instead of a single loop in the portion on the right, there is a necklace of $n$ triangles. So, all three diagrams on the right satisfy the intersection graph conjecture as in the inductive hypothesis, showing it is true for the diagram on the left.

Thus, by induction I can extend Theorem 1 to a whole necklace of triangles. $\square$

The art piece in Figure 6 (b) depicts an example of a necklace of triangles with both the intersection graph and a chord diagram. The colors of the chord correspond to the colors of its vertex on the intersection graph. I drew this piece to visualize a larger necklace of triangles from a simple example intersection graph.

Summary and Conclusions

Through the exploration of my artwork on the subject I was able to discover a new family of chord diagrams for which the Intersection Graph Conjecture is true. Working with an example in an art piece, I found a single generalized four term relation that made a very specific type of chord diagram satisfy the Intersection Graph Conjecture. I then extended the properties to an infinite family that also satisfy the conjecture.

Acknowledgements

Thanks to my advisor, Ren Guo, for supporting my art long enough to enable me to make this discovery, and thanks to Elise Lockwood for her help in revising this paper.

References

[1] S. Chumtov, S. Duzhin, and S. Lando. “Vassiliev Knot Invariants II.” Advances in Soviet Mathematics, 21, 1994, pp. 127-134. [2] S. Chumtov, S. Duzhin, and S. Lando. “Vassiliev Knot Invariants I.” Advances in Soviet Mathematics, 21, 1994, pp. 117-126. [3] S. Chmutov, S. Duzhin, J. Mostovoy. Introduction to Vassiliev Knot Invariants. Cambridge University Press, 2012. [4] B. Mellor. “The Intersection Graph Conjecture for Loop Diagrams.” J. Knot Theory Ramifications, 9, 2000, pp. 187-211. [5] J. Murikami. “Finite Type Invariants Detecting the Mutant Knots.” Knot Theory, 2000, Osaka University.