Concept

Crossing number

The fewest pairs of edges that must cross in any drawing of a graph in the plane. It is zero exactly for planar graphs, and the first two graphs with crossing number one are the obstructions Kuratowski named.

Named by 7 essays across 2 fields — each of them below, with the objects they name alongside it.

the trefoil. the trefoil, drawn as a closed curve with 3 crossings. At each crossing the strand passing underneath is broken, which is the only information the flat picture carries that the curve alone does not.

Three moves, and what they cannot undo

A knot is a closed loop of string, and two knots are the same if one can be wiggled into the other. Reidemeister reduced all possible wiggling to three local pictures — which is what makes it possible to prove that a knot is knotted.

topology · Knots
Two graphs that will not lie flat, and one that will. K4, K5 and K3,3 in the best straight-line drawings a search could find. K4 has no crossings; the other two have one each, and Euler's formula shows that none can have none.

Two graphs that will not lie flat

Five points, every pair joined: no matter how the points are placed or how the lines are drawn, two of the lines cross. The proof is not about drawing at all — it counts edges against faces and finds one edge too many.

discrete · Planarity
the Hopf link, with every crossing signed. A diagram of the Hopf link with the under-strand broken at each crossing and each crossing between two components marked with its sign, which add to twice the linking number.

Two loops and one number

Give each crossing between two closed curves a sign, add them up, halve — and the answer does not depend on how the curves were drawn, how they are pushed about, or which way the picture was projected.

topology · Linking number
The two extreme states of the figure-eight knot. The figure-eight knot, then the state with every crossing smoothed the A way (3 circles) and the state with every crossing smoothed the B way (3 circles). The bracket spans 16 powers of A against 16 for four times the crossings.

The crossings an alternating knot cannot lose

Peter Guthrie Tait drew knots for years and believed, without proof, that a diagram whose crossings alternate over and under, and which has no twist that can be undone, is already drawn with the fewest crossings the knot allows. The proof took a century, and when it came it needed only the two most extreme ways of smoothing the diagram and Euler's count of the regions of a map.

topology · Knots
The complete graph on 7 points, drawn straight with 9 crossings. A straight-line drawing of the complete graph on 7 vertices with 9 crossings, the minimum for straight drawings; each crossing comes from four vertices in convex position.

The crossings a graph cannot avoid

Five points all joined need one crossing, six need three, seven need nine. Euler's formula gives a lower bound that grows like the square of the number of points and is badly wrong; a sampling trick turns the same formula into a bound that grows like the fourth power and is right to within a constant. And for drawings with straight edges the count turns out to be something else entirely: the number of quadrilaterals the points make.

discrete · Planarity
A trefoil knot made of six straight sticks. Hexagon with corners (6, 2, 3), (7, 7, 10), (1, 6, 4), (2, 1, 7), (8, 10, 5), (0, 9, 9); three crossings from above, determinant 3, Alexander polynomial t² − t + 1.

Six sticks tie a trefoil, and five cannot

Build a knot from straight sticks joined end to end and ask for the fewest. A trefoil takes six, and the six corners can be whole-number points in a box ten units wide. Five sticks can cross one another five times in a picture, as often as a cinquefoil needs, and still tie nothing — the five crossings always twist three one way and two the other. The fewest sticks is a measure of how knotted a knot is that no diagram shows directly.

topology · Knots
How often a closed random polygon is certainly knotted, by length. 10: 0.8% (mean crossings 2.8); 20: 1.5% (mean crossings 7.9); 40: 6.3% (mean crossings 21.2); 60: 10.5% (mean crossings 35.1); 80: 20.8% (mean crossings 51.3); 100: 22.0% (mean crossings 66.9); 130: 32.3% (mean crossings 94.9); 160: 45.7% (mean crossings 122.6); 200: 47.0% (mean crossings 154.5); 250: 51.7% (mean crossings 205.5).

Almost every long loop is knotted

Close a random walk into a loop and ask whether it is knotted. With ten steps almost never; with a hundred, more than one time in five it can be proved knotted by a single number; with two hundred and fifty, more than half. The chance of staying unknotted falls exponentially with length — Frisch, Wasserman and Delbrück guessed it for polymer rings around 1961, and it was proved in 1988 — because a knot needs only one small tangle somewhere, and a long loop has room for many.

topology · Knots

Named alongside it

The objects these essays reach for when they reach for this one.

KnotInvariantProjectionTopological invariantComplete graphEuler formulaKnot determinantOrientationPlanar graphReidemeister movesWritheAlternating knot

All concepts