Matpic
mathematics, in pictures
Concept

Eulerian path

A walk through a graph using every edge exactly once. One exists precisely when the graph is connected and at most two of its vertices have an odd number of edges — the first theorem of graph theory, and the reason de Bruijn sequences exist.

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

6 necklaces, concatenated into a de Bruijn sequence. The Lyndon words of length dividing 4 over 2 letters, listed in lexicographic order and written end to end; the result is the lexicographically least de Bruijn sequence of order 4.

Every necklace, in order

The graph construction needs the whole graph in memory and finds one sequence among hundreds of millions. Listing the necklaces in alphabetical order and writing them end to end needs no graph at all, and produces the smallest of them.

computation · de bruijn A four-by-four array holding every two-by-two block. A binary array, cyclic in both directions, drawn with its wrapped row and column, in which each of the sixteen two-by-two blocks appears exactly once.

A page that knows where it is

A four-by-four array of bits, cyclic in both directions, in which every two-by-two block appears exactly once. Print it repeatedly across a sheet and any four marks on that sheet are an address.

computation · de bruijn 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

Named alongside it

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

Counting argumentDe bruijn sequenceGraphConstructionDe bruijn torusEquivalence classError correcting codeGreedy algorithmLexicographic orderLyndon wordNecklaceParity

All concepts