Matpic
mathematics, in pictures
Concept

Universal cycle

A cyclic sequence in which every object of some family, such as every word of a given length, appears exactly once as a window of consecutive symbols. De Bruijn sequences are the case of words; subsets and permutations are harder.

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

A cycle showing every pair from 5 things exactly once. The complete graph on 5 points with an Eulerian circuit drawn, and the cyclic sequence of symbols it spells; every window of two consecutive symbols is a different pair.

A cycle for every pair

A cyclic sequence in which every window of two consecutive symbols is a different pair of things. For five things it exists and for four it does not, and in both cases there are exactly as many pairs as there are places to put them.

computation · De bruijn Six permutations as six arrows between three symbols. A directed graph with 3 vertices and 6 arrows, one per permutation of 3 symbols in shorthand, every vertex with two arrows in and two out, numbered in the order of an Euler circuit spelling 213231.

Every ordering once, around a cycle

No cycle can show every ordering of three symbols as a window of three: a window holding each symbol once forces the next symbol to repeat the one just dropped, so the sequence has period three and shows three orderings of six. Two repairs work. Write each ordering by its first two entries and the transitions form a balanced graph, so Euler's theorem hands over the cycle at once. Or add a fourth symbol and ask only that each window keep a different relative order — which works too, but no graph explains why.

computation · De bruijn

Named alongside it

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

Counting argumentDe bruijn sequenceEulerian pathGraphPermutationOrder isomorphismParitySubset

All concepts