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
Here are perhaps the most simple thrackle embeddings of graphs with the same number of edges and vertices:
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
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:
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
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:
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:
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:
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:
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.
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)
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
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.
|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
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.