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 11 essays across 3 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
Ten points, thirteen halving lines. points 0.253,1.518 0.242,0.216 0.717,0.119 -0.427,0.222 0.554,0.409 0.299,0.346 0.806,0.006 -1.101,0.118 1.209,-0.414 0.445,0.714; halving pairs 0-9 1-2 1-3 1-5 2-4 2-6 3-5 3-7 4-5 4-9 5-6 5-9 6-8; degrees 1,3,3,3,3,5,3,1,1,3.

Lines that leave half on each side

Scatter ten points on a page and draw every line through two of them that leaves four on each side. There are at least five such halving lines and at most thirteen, and every point lies on an odd number of them. Both facts come from turning a line through half a revolution, the argument that halves two shapes with one cut. How many halving lines n points can have is the k-set problem, and its answer lies somewhere between a little more than n and n to the four-thirds.

topology · Borsuk ulam
Two random loops and the crossings between them. 56 crossings, 25 positive, 31 negative, linking number -3.

Many crossings and a small linking number

Two random loops of a thousand steps, tangled round a common centre, cross each other about a thousand times in any picture of them. The linking number is half the signed count of those crossings — and it is typically about three. The signs cancel in nearby pairs, wherever one loop dips under the other and comes back, and what survives grows roughly as the fourth root of the length. Shut the same loops in a box and the cancellation stops: the crossings grow as n², and the linking number as n.

topology · Linking number
Every two edges meet. Star polygons with 3, 5, 7 and 9 points: odd star polygons are straight thrackles with exactly as many edges as points; every pair of edges meets once, at a shared point or by a crossing.

Every two edges must meet

A planar drawing has edges that avoid each other. Turn the rule round and insist that every two edges meet exactly once, at a shared end or a single crossing, and the drawing is what John Conway called a thrackle. In the 1960s he conjectured that a thrackle can never have more edges than points, and put up a prize. With straight edges a short argument settles it, and the argument also bounds the longest distances in a set of points. With curved edges it is still open.

discrete · Planarity
Many points on many lines. Grid of 192 points and 128 lines with 512 incidences, against (n m)^(2/3) = 845.

How often points can sit on lines

A million points and a million lines: how many times can a point lie on a line? Counting pairs says about a billion, and over a finite field that is exactly right. In the real plane the true limit is about a hundred million, because a line has an order along it. The proof takes four lines and uses nothing but a crossing count, and from it follows the fact that no set of numbers can have both few sums and few products.

geometry · Ordinary lines

Named alongside it

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

KnotInvariantPlanar graphProjectionTopological invariantComplete graphConjectureCounting argumentEuler formulaExhaustive searchExtremal problemKnot determinant

All concepts