When is a notation drawable?

Let a set consist of N pairs of natural numbers (i,j), where both i and j belong to {1,2,...,2N}, and where each number between 1 and 2N appears exactly once. One would like to know under what conditions there is some knot projection denoted by that set.

First we would like to remark that changing the order inside some pairs, that means replacing some (i,j) by (j,i), does not affect the notation's "drawability", and thus the problem will be discussed for knot shadows and not for the full projections. In other words, one does not need to distinguish between overcrossings and undercrossings while checking a notation's drawability.

Let us take an example of an undrawable notation: { {1,3} , {2,4} }. To see why such a notation is undrawable, click here . The notation "obviously" looks undrawable, but to rigorously prove it one needs the Jordan Curve Theorem. According to the theorem,

A loop in the two-sphere or the plane divides such a surface into two disjoint segments.

This is not as obvious as it may seem; in fact the theorem does not hold in manifolds of dimensionality higher than 2, in non-oriented 2-dimensional manifolds or in 2-dimensional manifolds of non-zero genus. It does hold however for the two-sphere, the plane, the cylindrical surface and so on.

Let now an unordered pair {i,j}, where i < j, belonging to the shadow notation. The curve i,i+1,...,j-1,j is obviously a loop, and so is the curve j,j+1,...,2N,1,...,i-1,i. Each of them will split the projective surface in disjoint pieces, and thus the other must "enter" as many times as it "exits". Therefore, between i and j there must be an even number of crossing points, and thus i-j must be odd. This is not the case however with { {1,3} , {2,4} }, and thus such a notation is undrawable.

Pairing odd numbers to even is a necessary condition, but not sufficient. Take for instance the notation { {1,4}, {3,6}, {5,8}, {7,10}, {9,2} }. To see why it is undrawable, click here, you will find it just below the previous one.

Were the notation above drawable, the segments 1-2-3-4 and 5-6-7-8 would form loops, and their intersection would consist of just one crossing point, namely {3,6}. This would have violated the Jordan Curve Theorem, since one loop would have "entered" the other without being able to "exit". The general rule may be stated as follows.

A shadow notation is drawable if and only if for any two loops that would be formed, the following holds. These two loops either share one or more common segments, or they intersect at an even number of points, vertices not counting.

A loop in general may not look as simple as i,i+1,i+2,...,j-1,j. It may have a form i,i+1,...,k-1,k<=>l,l-1,l-2,..,j+1,j ,where {k,l} is another pair of the notation, or it may have an even more complicated form. The number of possible loops is 3^N and thus the number of pairs one would have to check is 1/2 3^{2N}. While this number is finite and thus this problem can be solved in principle, it increases so rapidly that soon almost all of the computer time is spent just checking the shadow's drawability.

To learn a time-saving method to find whether a notation is drawable, click here.

Charilaos Aneziris, charilaos_aneziris@standardandpoors.com

Copyright 1995


Educational institutions are encouraged to reproduce and distribute these materials for educational use free of charge as long as credit and notification are provided. For any other purpose except educational, such as commercial etc, use of these materials is prohibited without prior written permission.