Matpic
mathematics, in pictures
Concept

Colour refinement

An algorithm that colours a graph's points by their degree, then by the multiset of their neighbours' colours, and repeats until nothing splits. It is the first thing every practical isomorphism test does, and it is exactly as strong as a two-pebble game — so the pairs it cannot separate are the pairs two variables cannot describe apart.

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

Also named here as graph isomorphism — the same set of essays touches all of them, so they are one junction rather than several.

A 6-cycle and two 3-cycles: refinement cannot tell them apart. Two graphs side by side — one cycle and two smaller cycles — with the same number of points, the same number of edges and every point of the same degree.

The game the algorithm was playing

Change what Duplicator has to offer — a whole bijection instead of one element — and the game stops measuring first-order logic and starts measuring colour refinement, the algorithm every practical graph-isomorphism test begins with. Two subjects that grew apart are one game with the moves relabelled.

logic · Ehrenfeucht–Fraïssé games Two graphs every count agrees on, and one question that does not. Two sixteen-point graphs drawn on a four-by-four grid, with one point marked and its six neighbours highlighted in each, the neighbours forming two triangles in one and a six-cycle in the other.

One gadget defeats every refinement

Colour refinement fails on two triangles against a hexagon; its two-dimensional version fixes that and fails on a pair of strongly regular graphs. For every k there are two graphs the k-dimensional version cannot separate, and they are built from one local piece whose only symmetry is a parity.

logic · Ehrenfeucht–Fraïssé games

Named alongside it

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

Ehrenfeucht fraisse gameGraph isomorphismInvariantCounting argumentExhaustive searchExpressive powerParityQuantifier depth

All concepts