Triangle-free chord diagrams

A chord diagram is formed by choosing some 2n points on a circle (say, at the vertices of a regular polygon) and then connecting them in pairs. It can be represented as a double permutation: a sequence of the 2n values 0,0,1,1,2,2,..., where each value appears twice, and where renumbering the values but keeping the same pairing forms a sequence that is considered to be equivalent. Simply place the values in clockwise order at the chosen points of the circle, and connect pairs of points with equal labels. For instance, the double permutation 0,0,1,2,3,1,3,2, placed clockwise starting at the top vertex of a regular octagon, produces the chord diagram

We may as well choose the permutation of the values so that the first number appearing in a double permutation is 0, the second is 1, etc., as in the above example. If we do so, it is not hard to see that the number of different double permutations is the double factorial (2n − 1)!! = 1 × 3 × 5 × 7 × ... × (2n − 1). For, there are 2n − 1 places in which the second 0 can go, after which the remaining values in the sequence form a double permutation with one less item. However, if one is interested in chord diagrams rather than double permutations, it is natural to consider two diagrams to be equivalent if some rotation or reflection takes one to the other, in which case there are many fewer chord diagrams, counted by OEIS sequence A054499.

A chord diagram is triangle-free if no three chords all cross each other. Triangle-free chord diagrams have a nice geometric property: the partition of the disk made by their chords forms a pattern that doesn't depend on the exact placement of the chord endpoints. For, moving the endpoints of any chord diagram, keeping the same double permutation labeling, produces combinatorial changes in the arrangement of the chords that can be described as Reidemeister moves of type III: inversion of a triangle. But, with no triangles, there can be no Reidemeister moves. Thus, the arrangement, as a plane-embedded graph, is completely determined by the double permutation forming the chord diagram. The planar duals of these graphs are the squaregraphs, planar graphs in which all interior faces are quadrilaterals and all interior vertices have four or more incident edges. Squaregraphs are an important class of partial cubes closely related to the subject of my Manhattan Orbifolds paper.

How can we test whether a double permutation describes a triangle-free chord diagram? Essentially, we wish to know whether it avoids the pattern ...a...b...c...a...b...c... This problem seems closely related to, but not the same as, testing bipartiteness of the intersection graph of the chords; it's not the same because cycles of five or more intersecting chords are ok, only triangles are disallowed. Nevertheless, it can be solved in linear time. The key idea is to process the double permutation representing the diagram in order, maintaining a list L1 of the chords for which only one endpoint has been processed so far, in the order that the endpoints were processed, and a second list L2 of the chords that could have their second endpoint appear next in the sequence without causing a triangle. When processing the second endpoint of a chord, its predecessor in L1 can be added in its place to L2, and all subsequent items in L2 should be removed except for the last one. Using this algorithm, and an algorithm for finding the lexicographically first double permutation representing an isomorphism class of chord diagrams, we may generate all triangle-free permutation diagrams up to a given number of chords in polynomial time per diagram, by forming a tree of diagrams in which the parent of a diagram is formed by removing its first chord, and searching this tree. If my implementation is correct, the numbers of isomorphism classes of triangle-free diagrams with numbers of chords ranging from 1 to 9 are 1, 2, 4, 13, 48, 256, 1619, 12399, and 104732. I tested the code with the triangle-free check disabled against the known values of sequence A054499, and I also checked the triangle-free part against a manual enumeration of the diagrams on up to four chords, so I'm pretty hopeful about the correctness of the results, but some kind of cross-check would probably be a good idea.

If one looks at the diagrams resulting from this enumeration, it turns out that many of them are disconnected: the chords are partitioned into non-intersecting subsets. The more fundamental objects in this enumeration seem to be the connected chord diagrams, dual to the squaregraphs with no articulation point. A biconnected squaregraph is determined up to graph isomorphism by its chord diagram; the connectivity assumption is needed because without it it might be possible to flip part of the graph over at an articulation point, creating two different diagrams for the same graph. I don't know how to generate the connected triangle-free chord diagrams in polynomial time per diagram, but it's easy enough to generate all triangle-free diagrams and test for connectedness afterwards: a diagram is connected if and only if no double permutation representing has a prefix that's also a double permutation. Using this test, I counted the numbers of isomorphism classes of connected triangle-free chord diagrams with numbers of chords ranging from 1 to 9, as 1, 1, 1, 3, 8, 35, 172, 1121, and 8017. Here are the ones on up to five chords, drawn for a lexicographically-smallest double permutation labeling running clockwise from the top:

The connected triangle-free chord diagrams on six chords, as output by my program, are represented by the double permutations

1. 0, 1, 0, 2, 1, 3, 2, 4, 3, 5, 4, 5
2. 0, 1, 2, 0, 3, 2, 4, 3, 5, 4, 1, 5
3. 0, 1, 0, 2, 3, 1, 4, 3, 5, 4, 2, 5
4. 0, 1, 0, 2, 1, 3, 2, 4, 5, 4, 3, 5
5. 0, 1, 0, 2, 1, 3, 4, 5, 3, 5, 2, 4
6. 0, 1, 0, 2, 1, 3, 4, 2, 4, 5, 3, 5
7. 0, 1, 0, 2, 1, 3, 4, 3, 2, 5, 4, 5
8. 0, 1, 0, 2, 1, 3, 4, 3, 5, 2, 5, 4
9. 0, 1, 0, 2, 3, 2, 4, 1, 4, 5, 3, 5
10. 0, 1, 0, 2, 1, 3, 2, 4, 5, 3, 5, 4
11. 0, 1, 0, 2, 3, 1, 4, 5, 3, 5, 4, 2
12. 0, 1, 0, 2, 1, 3, 4, 5, 4, 3, 2, 5
13. 0, 1, 0, 2, 3, 1, 3, 4, 5, 2, 5, 4
14. 0, 1, 0, 2, 1, 3, 4, 5, 4, 2, 5, 3
15. 0, 1, 0, 2, 1, 3, 4, 2, 5, 4, 5, 3
16. 0, 1, 0, 2, 1, 3, 4, 5, 2, 5, 4, 3
17. 0, 1, 0, 2, 3, 4, 5, 1, 5, 4, 3, 2
18. 0, 1, 0, 2, 3, 2, 1, 4, 5, 3, 5, 4
19. 0, 1, 0, 2, 1, 3, 4, 2, 5, 4, 3, 5
20. 0, 1, 0, 2, 3, 4, 1, 5, 4, 3, 5, 2
21. 0, 1, 0, 2, 3, 1, 4, 3, 2, 5, 4, 5
22. 0, 1, 2, 0, 3, 2, 4, 5, 3, 1, 5, 4
23. 0, 1, 0, 2, 1, 3, 4, 5, 3, 2, 5, 4
24. 0, 1, 2, 0, 3, 2, 4, 1, 5, 4, 3, 5
25. 0, 1, 0, 2, 3, 2, 4, 1, 5, 4, 3, 5
26. 0, 1, 0, 2, 3, 1, 4, 3, 5, 2, 5, 4
27. 0, 1, 0, 2, 3, 4, 1, 4, 5, 3, 2, 5
28. 0, 1, 0, 2, 3, 1, 4, 5, 4, 3, 2, 5
29. 0, 1, 0, 2, 3, 1, 4, 5, 3, 5, 2, 4
30. 0, 1, 0, 2, 3, 1, 4, 5, 3, 2, 5, 4
31. 0, 1, 2, 0, 3, 4, 5, 2, 1, 5, 4, 3
32. 0, 1, 2, 0, 3, 4, 2, 1, 5, 4, 3, 5
33. 0, 1, 0, 2, 3, 4, 2, 1, 5, 4, 3, 5
34. 0, 1, 0, 2, 3, 4, 1, 5, 4, 3, 2, 5
35. 0, 1, 2, 3, 0, 4, 5, 3, 2, 1, 5, 4

My code is highly non-optimized, both in its algorithms and its implementation, so it shouldn't be difficult to extend the sequences of counts by at least two terms.

Exercises:

(I don't intend to continue including these regularly, but here there were a few facts I thought better left to the reader.)

1. Find the labelings of the eight four-chord connected triangle-free chord diagrams shown above.
2. Draw the diagrams corresponding to the first four five-chord triangle-free double permutations listed above.
3. Prove that, if a triangle-free chord diagram is not connected, then one of the double permutations representing it has a prefix that is also a double permutation.
4. Prove that, if a double permutation has a prefix that is a double permutation, then the chord diagram it represents is not connected.
5. Find an example of a chord diagram that is not connected, but such that the lexicographically smallest double permutation representing it has no prefix that is also a double permutation. (The two smallest solutions have only six chords.)

Comments: