Concept

Induction

A method of proof in which a statement about every whole number follows from the first case and from each case implying the next. Its strength is that a single argument covers infinitely many claims, and its cost is that the conclusion is only as sharp as the step.

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

One swap frees a colour. A vertex of degree five whose neighbours carry five different colours, before and after a Kempe chain is recoloured. The swap frees one colour for the middle vertex.

Five colours, and a chain that can be followed

The four-colour theorem cannot be checked by a person. The five-colour theorem can, in a page, and the argument that does it is the one Kempe thought had settled four — with the exact step where it fails visible in the picture.

discrete · graph colouring

17 points coloured by whether their difference is a square. 17 points on a circle with every pair joined, coloured by whether the difference of their labels is a square modulo 17; the largest set of points all joined by one colour has 3 members.

Eighteen people, and the seventeen that escape

Among any eighteen people, four are mutual acquaintances or four are mutual strangers. Seventeen can be arranged so that neither happens, and the arrangement is not a lucky find — it is a rule about squares.

discrete · ramsey theory

Named alongside it

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

Chromatic number Complete graph Counterexample Counting argument Euler formula Existence proof Graph Graph colouring Kempe chain Modular arithmetic Paley graph Pigeonhole principle

All concepts