What is known about the Thrackle Problem

Stephan Wehner

First up: May 7, 1996.
Major update: March 23, 2000
Adding sequence types for 11-cycle: March 7, 2010
Last update: March 7, 2010

thrackle.org home

In the late sixties, John Conway posed the following problem:

A thrackle embedding of a graph is a function which maps each vertex to a point and each edge to a closed continuous lines in the plane such that

Is there a graph which has more edges than vertices and has a thrackle embedding?

Conway's thrackle conjecture asserts that this is not the case. (In fact, he has promised a prize of $1000 for a solution) This webpage gives a compilation of what is known about this question; some of it can be found in Woodall's paper

Contents

  1. Examples of embeddings
  2. What would a counterexample look like?
  3. All cycles but the 4-cycle have embeddings.
  4. Known bounds on the number of edges vs. the number of vertices.
  5. On sequences of embeddings of the 4-path.
  6. Related output of a computerized search plus an
  7. Interpretation
  8. References.
  9. Additional Resources.

(Collaboration with Luis Goddyn)

1. Two examples

Here are perhaps the most simple thrackle embeddings of graphs with the same number of edges and vertices:

[Pictures of a triangle and the n-ray]

The graph embedded on the left is the 3-cycle. On the right is shown an embedding of the graph with (n-2) edges meeting at one vertex of a 3-cycle. Note that only straight lines occur. Below is an example which is necessarily drawn with curved lines.
Back to top

2. What would a counterexample look like?

It is rather easy to see that a counterexample (if it exists) to the conjecture has to contain two cycles, and that a counterexample with the minimal number of vertices would either be Mike Rubinstein (unpublished) showed that if there is a counterexample of any one of these three kinds, then there are counterexamples of all three kinds.
Back to top

3. All cycles but the 4-cycle have embeddings

That the 4-cycle has no thrackle embedding is a straightforward application of Jordan's Theorem. The existence of thrackle embeddings of the cycles of order > 4 follows from the following statement and the existence of thrackle embeddings of the 3-cycle and the 6-cycle.

If a cycle of order N has a thrackle embedding, then so does the cycle of order N+2. We replace a 3-path by a 5-path and change the embedding in the following way:

[Picture showing how to replace a 3-path by a 5-path]

The new lines are drawn sufficiently close to the original (dotted) line so that they intersect lines in the same order and orientation as the original line. Of course, the lines involved will be curved in general.

From the triangle we obtain embeddings of the odd cycles of order > 2. Here for example is the embedding of the 5-cycle:

[Picture of a 5-star]

Note that this embedding was obtained from a straight line embedding of the triangle and that it was possible to carry out the replacement procedure with straight lines. Applying it one more time will give a straight line embedding of the 7-cycle. There is no difficulty in seeing that just the odd cycles have straight-line embeddings.

Note also that, when one is just interested in the order and the direction in which lines cross, there is essentially only one embedding of the 5-cycle. If the lines are numbered in order of occurence along a traversal, then line x meets lines x+2, x-2 (mod 5) in this order and they hit line x in opposite directions. For cycles of order > 5, there are many different kinds of embeddings. (see further down)

To obtain embeddings of all even cycles of order > 4, we need to show an embedding of the 6-cycle. This can also be obtained from the triangle, but with a different method. Replace every line of an embedding by two lines in the following way:

[Illustration of replacement]

When applied to an embedding of an odd cycle, this replacement yields an embedding of a cycle of doubled order. When applied to an embedding of an even cycle, this replacement yields an embedding of two copies of the cycle. For the triangle the result is an embedding of the 6-cycle:

[Picture of result]

Back to top

4. Known bounds on the number of edges vs. number of vertices

Lovasz, Pach and Szegedy have shown that a bipartite graph can have a thrackle embedding only if it is planar. From Euler's polyhedral formula one readily obtains a bound on the number of edges with respect to the number of vertices for bipartite graphs with thrackle embeddings (roughly E < 3V). They sharpened this bound and proved that if a (possibly non-bipartite) graph with V vertices has a thrackle embedding then it has at most 2V - 3 edges.

Recently Cairns and Nikolayevsky have improved this bound: if a graph with V vertices has a thrackle embedding, then it has at most 1.5(V-1) edges.

5. Sequences of embeddings of the 4-path

In their paper, Lovasz, Pach and Szegedy also show that the theta T(3,3,3) formed by paths of length three has no thrackle embedding. The proof relies on analyzing embeddings of the directed 4-path 1->2->3->4->5. These are shown in the following diagram (upto the operation of inverting of faces)

[Illustrations of the six configurations]

According to the order and the orientation with which the fourth line crosses the first and second line, the embeddings are classified (by us) as zero, plus or minus. Note that if the spots 1,2,3,4,5 are relabeled with 5,4,3,2,1, respectively, the minus configurations become plus-configurations and vice versa; the zero configurations stay zero-configurations. In other words, a plus-configuration walked backwards is a minus-configuration, and vice-versa, and a zero-configuration walked backwards is a zero-configuration.

The graph T(3,3,3) consists of three 6-cycles each pair of which shares a 3-path. The directed 6-cycle (1->2->3->4-5->6->1) consists of six overlapping directed 4-paths: (1->2->3->4->5, 2->3->4->5->6, ..., 6->1->2->3->4). In an embedding of a 6-cycle, which configurations occur? Which sequences of configurations occur?

In proving that T(3,3,3) has no thrackle embedding Lovasz et.al. used the fact thata there is no zero-configuration in any embedding of the 6-cycle, and either there are only plus-configurations or only minus-configurations.

Back to top

6. Output of a computerized search

A C-program generated all thrackle embeddings of cycles of order 6 - 11 and analyzed which sequences of configurations occur. The results are shown below. Inspection of the embedding of the 5-cycle from above reveals that only zero-configurations occur. For the triangle the notion is not applicable and the 4-cycle has no embedding.

Realised sequences

For the 6-cycle Type 1 + + + + + +
For the 7-cycle Type 1 0 0 0 0 0 0 0
Type 2 0 0 0 - 0 0 +
For the 8-cycle Type 1 0 0 0 0 + + + +
Type 2 0 0 + + + + + -
For the 9-cycle Type 1 0 0 0 0 0 0 0 0 0
Type 2 0 0 0 0 0 0 0 + +
Type 3 0 0 0 0 0 0 - 0 +
Type 4 0 0 0 0 0 0 - 0 -
Type 5 0 0 0 0 0 - 0 0 +
Type 6 0 0 0 0 0 + 0 0 +
Type 7 0 0 0 0 0 + 0 0 -
Type 8 0 0 0 0 + 0 0 0 -
Type 9 0 0 0 + - 0 0 + +
Type 10 0 0 0 - - 0 0 + +
Type 11 0 0 + - 0 0 + 0 -

The program found


Back to top

7. Interpretation

The table above tells us that the zero configuration cannot be found in an embedding of the 6-cycle, but it can be found for example in an embedding of the 8-cycle. Look at one of the zero configurations. From the table we read of the following two facts: In this manner, the table provides us with many more examples of embeddings of paths which can only be completed to an embedding of a cycle with a certain minimal number of lines.

The thrackle conjecture is a similar problem. For example: draw an embedding of a 6-cycle and add two lines at an endpoint of a line so that they intersect all other lines exactly once. The conjecture asserts that it is not possible to connect the endpoints of these two lines obeying the rules of thrackle embeddings.


Back to top

8. References

9. Additional Resources