Concept

Gray code

An ordering of the binary words in which each step changes exactly one place. It is a Hamiltonian cycle on the cube of binary words, and it is used wherever two bits changing at once would be read as a third value.

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

((p ∧ q) ∨ (r ∧ s)) ∨ (¬p ∧ ¬r), covered by 3 rectangles. A grid of the assignments arranged so that neighbouring squares differ in one variable.

The map that puts neighbours side by side

Reorder the rows of a truth table so that neighbouring squares differ in one letter, and finding a short formula stops being algebra and becomes the problem of covering a shape with rectangles.

logic · Truth functions

A closed walk on the 3-cube changing one place at a time. The corners of a 3-dimensional cube with a path through every one of them exactly once, each step moving along an edge, and the last corner one step from the first.

A walk that changes one thing at a time

Counting from nothing to fifteen in binary changes four digits at once somewhere in the middle. There is another order through the same sixteen words in which every step changes exactly one — and it is a closed walk on a four-dimensional cube.

discrete · Hamiltonian cycles

The 1,344 tours of the 4-cube, by how often each place changes. A bar for each pattern of change counts among all closed walks through the 4-cube, with the number of tours having it; the reflected code's pattern and the perfectly even one are marked.

Every place changes back

A closed walk through every corner of a cube changes one place at each step, and each place, having changed, must change back before the walk returns home. So every place changes an even number of times — which is why no walk on three places can share the work evenly, why perfect sharing is possible only when the number of places is a power of two, and what sorts the 1,344 walks on the 4-cube into exactly four kinds.

discrete · Hamiltonian cycles

A cycle through the middle two levels of the 5-cube: 20 words. The words of length 5 with 2 or 3 ones placed round a ring in the order of a Hamiltonian cycle, alternating between the two levels, each step changing a single place.

The walk through the middle levels

On seven places, the words with three ones and the words with four number thirty-five each. Is there a closed walk through all seventy, changing one place at a time and never leaving those two levels? On five places the answer is 24 walks, on seven and nine a search finds one in moments — and whether one exists for every odd length was open for thirty years, until Torsten Mütze proved in 2016 that it always does.

discrete · Hamiltonian cycles

Eight corners of a squashed cube, visited in order by the simplex method. Klee and Minty's program in 3 variables drawn as its own deformed cube and as a plain one. The simplex method with the largest-price rule visits all 8 corners, with objective values 0, 4, 6, 10, 15, 19, 21, 25; the optimum is one edge from the start.

The cube that takes every corner

The simplex method is fast on every program anybody meets in practice. In 1972 Victor Klee and George Minty squashed a cube so that the method, choosing the steepest edge each time, visits all of its corners — 2ⁿ − 1 moves in n variables, with the optimum one edge from the start.

applied · Duality

Named alongside it

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

Hypercube Parity Counting argument Binary Hamming distance Karnaugh map Binomial coefficient Bipartite graph Combinations Complete graph Covering Exponential growth

All concepts