Chord diagrams and Euler tours
Back to chord diagrams.
One application of these diagrams is in knot theory: if one has a plane drawing of a knot, one can form a chord diagram for the knot drawing by mapping the knot itself to a circle and connecting pairs of points on the circle that correspond to the two points of a crossing in the drawing.
This application is an example of a more general construction, in which a chord diagram describes an Euler tour of a 4-regular graph, by listing the vertices in the order they are visited by the tour and connecting the two copies of each vertex in the list. The graph itself (and the associated Euler tour) may be recovered from the diagram, by forming a vertex for each chord and an edge for each pair of chords that have endpoints one position apart.
In the knot theoretic application, the 4-regular graph has a vertex for each crossing and an edge for each uncrossed segment of curve, and the Euler tour is the one that goes straight through each crossing. Note that in this case, though, the knot diagram itself may not be determined by the chord diagram, even ignoring the information about which strand is on top and which on the bottom at each crossing, because one may independently invert any two-edge-connected component of the graph.
If one uses an arbitrarily chosen oriented edge ωα of the graph as the starting point of a chord diagram, one can represent each chord diagram, and therefore each Euler tour, by a double permutation that starts with α and ends with ω. Any Euler tour may be converted to a different tour by cutting it at an arbitrarily chosen vertex v and reconnecting the two cut pieces; there are two different ways of doing this reconnection but only one of them forms another tour. In the double permutation, this reconnection may be represented by reversing the subsequence between the two occurrences of v: e.g., cutting at B in the tour represented by the diagram above, which has the double permutation A(BCDGHEB)GFCHADEF, produces the new double permutation A(BEHGDCB)GFCHADEF. Call such a transformation a “flip.”
Choose some particular tour T0, let T be any other tour, and let v be the last vertex on the longest common prefix of T0 and T. Then that prefix must end at the first occurrence of v within both tours. If flipping T at v does not produce another tour that shares a longer common prefix with T0, then there must be some other chord w that crosses the chord of v such that flipping w then v increases the length of the common prefix. Thus, any tour may be reached from any other tour by a sequence of at most 2n flips. Additionally, this structure may be used to define a reverse-search based procedure for listing all tours of a given graph efficiently.
Because the operation of flipping at a vertex permutes the Euler tours of the given graph, we may consider the permutation group generated by all n such involutions. Unfortunately, these generators behave somewhat schizophrenically in terms of how they commute with each other: if the chords for v and w do not cross in some diagram D, then D(vw)2 = D, but if they do cross, then D(vw)3 = D. For most graphs there will be some tours where two chords cross and some other tours where the same two chords do not cross, so the group action is not free.
Comments:
2008-02-16T04:30:48Z
"If the chords for v and w do not cross in some diagram D, then D(vw)^2 = D, but if they do cross, then D(vw)^3 = D"
You've stumbled on (the abelianization of) the Birman-Ko-Lee presentation of the standard n-strand braid group. There are n-choose-2 generators, each corresponding to an edge or chord of a regular n-gon. Specifically, if you imagine that the strands of the braid are threaded through the plane at the n-gon vertices, a chord represents giving the corresponding pair of braids a clockwise half-twist. If two chords do not cross, the corresponding twists commute. If they do cross, the twists define a "Reidemeister" relation xyx = yxy.
Thus, if you think of the chords as generators of the symmetric group, you recover exactly the behavior you observe: xyxy=1 if chords x and y do not cross, and xyxyxy=1 if chords x and y do cross.
Chords diagrams and non-crossing partitions turn out to be quite useful in combinatorial group theory. See Jon McCammond's survey: http://www.math.ucsb.edu/~jon.mccammond/papers/intro-garside.pdf
Yay, braids!
2008-02-16T04:40:48Z
Cool! Though this doesn't seem to mean that the braid group acts on Euler tours, as the flips for a vertex v will correspond to different chords in different diagrams. Alternatively, if you try to define the action of a braid generator in terms of whatever happens to be in the diagram at that position, you run into a problem with the braid generators that don't correspond to chords: giving them a trivial action breaks the Reidemeister relation.
Thanks for the reference, I'll take a look at it.
2008-02-20T08:58:43Z
So I'm trying to understand this, but I must admit I know next to nothing about knot theory. Here's the question I can't seem to figure out. Lets say you have a chord diagram with a double permutation ABAB, it has a euler tour, so it should have an associated knot. The problem is, when I try to draw the knot it either ends up looking like a venn diagram(two separate loops), or it's a knot made with a single loop, but it crosses at one point and then just sort of kisses at the other point(but doesn't actually cross)...Is this acceptable? Is it still considered a knot? Or am I just making some sort of mistake that's preventing me from drawing a normal knot that crosses in two points(as my intuition tells me it should).
Thanks for the help!
2008-02-20T16:28:48Z
Not every chord diagram comes from a knot. As you say, that one doesn't. If you take a curve that crosses itself twice, you should get either AABB or ABBA.
2008-02-20T22:29:04Z
Thanks for the response!
So the mapping from chords to knots is not one-to-one...is it onto?
2008-02-20T22:34:51Z
It doesn't encode the over-under relations. You can turn any knot diagram inside out and make any of its faces the exterior one without changing the corresponding chord diagram. And, if a knot is not prime (can be decomposed into two pieces that don't cross each other by cutting the curve in two places), you can get the same chord diagram but a different knot diagram by flipping one of the two pieces. But otherwise, the chord diagram describes a 3-edge-connected planar graph, which has a unique embedding.