Matpic
mathematics, in pictures
Concept

Hamiltonian cycle

A closed path in a graph that visits every point exactly once. Deciding whether one exists is hard in general; complete graphs have many, and they are the cycles that seating plans, travelling salesman tours and knotted paths through points are made of.

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

A single table for 9 guests over 4 nights. Small circles of 9 guests, one per night, each showing the night's seating as a closed zigzag path; every pair of guests is adjacent in exactly one of them.

Every pair side by side, once

Seat an odd number of guests at round tables for as many nights as it takes, the same table sizes every night, so that every two guests sit side by side on exactly one night. For a single table a zigzag turned a notch each night does it for any number of guests. For other table plans the answer is almost always yes — and for six guests at two tables of three, nine at tables of four and five, and eleven at three, three and five, an exhaustive search proves it is no.

probability · Inclusion exclusion Seven points in space and a knotted path through all of them, seed 12. A projection of K₇ with straight edges, faint, and one Hamiltonian cycle drawn heavy with its crossings broken: a trefoil. 9 of the 360 Hamiltonian cycles are knotted.

Seven points and a knot they cannot avoid

Put seven points anywhere in space and join every pair with a straight segment. There are 360 closed paths that visit all seven points once each, and at least one of them is knotted — however the points are placed. The reason is a parity, as it was for six points and a linked pair: a number read off each path's knot adds up, over all 360, to something odd. Six points are not enough; seven always are.

topology · Linking number

Named alongside it

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

Complete graphAlexander polynomialBipartite graphCounterexampleExhaustive searchGraph decompositionIntrinsic knottingKirkmanKnotParitySeatingStick number

All concepts