Matpic
mathematics, in pictures
Concept

Eulerian circuit

A closed walk through a graph that uses every edge exactly once. It exists in a connected graph exactly when every vertex has even degree, or, for arrows, as many arrows in as out at every vertex.

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

The de Bruijn graph on 2 letters and words of 3, and the cycle through it. A graph whose vertices are short words and whose arrows are words one letter longer, with a closed walk using every arrow exactly once marked, and the cyclic sequence it spells.

Every word once, around a cycle

A cyclic string of eight bits holds all eight three-bit words, each exactly once — and the reason such a thing exists is that the constraint linking overlapping windows is itself the construction.

computation · De bruijn Two arrows in and two out at every point. 9×9 patch from a random height function, seed 3; heights range 1..6.

Two arrows in and two out

An Eulerian circuit enters every point as often as it leaves, so it hands every edge an arrow with the arrows balanced at each point. Count those balanced orientations instead of the circuits and the question turns into the ice in a freezer: on the square grid, where every point has two arrows in and two out, there are about 1.5396 of them per point — Lieb's (4/3)^(3/2), against Pauling's guess of 1.5. Fix the walls of a square of ice and the count becomes 1, 2, 7, 42, 429, 7436: the alternating-sign matrices.

discrete · Eulerian paths

Named alongside it

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

Exhaustive searchCountingCyclic wordDe bruijn sequenceDeterminantEncodingGraphGraph colouringHierholzer's algorithmOrientationSpanning treeTransfer matrix

All concepts