A cycle for every pair

A de Bruijn sequence lists every word of a fixed length, once each, in a cycle. The obvious question is what else can be listed that way — every subset of a fixed size, every permutation, every partition — and the obvious answer is that the counting has to work out. The counting works out far more often than the cycles exist.

Fix a ground set of $n$ things and ask for a cyclic sequence of symbols in which every window of $k$ consecutive symbols is a different $k$-element subset. Such a thing is a universal cycle, or ucycle. Its length has to be $\binom{n}{k}$, because that is how many subsets there are and each position gives one.

The case that is a graph #

For $k = 2$ the object is something already familiar in disguise.

A window of two consecutive symbols is a pair, and consecutive windows overlap in one symbol. So the sequence is a walk in which the vertices are the symbols and the edges are the pairs — and requiring every pair exactly once makes it a walk using every edge of the complete graph exactly once and returning to its start.

A universal cycle for the pairs from $n$ things is an Eulerian circuit of the complete graph on $n$ points, and nothing else.

Euler settled when those exist and the criterion is the degrees: a connected graph has a circuit using every edge once exactly when every vertex has even degree. In the complete graph on $n$ points every degree is $n-1$. So the cycle exists precisely when $n$ is odd.

That is a complete answer, it took one reduction to reach, and it is not a counting argument at all.

It also answers a question the reduction makes visible and the original phrasing hides: how many such cycles are there? As many as the complete graph has Eulerian circuits, which the BEST theorem counts in terms of a determinant of the graph’s Laplacian — so the existence question and the counting question are answered by the same reduction, and both are answered by a theorem about graphs rather than about sequences. For five things the number runs to the hundreds; for seven it is astronomical, and the figure builds one of them.

Two counts, and only one of them is a condition #

There is a counting argument here and it is easy to get the wrong one.

The naive count says there are $\binom{n}{k}$ subsets and a cycle of that length has $\binom{n}{k}$ positions, so the sizes match. That is true for every $n$ and every $k$, it is satisfied at $n = 4$ exactly as at $n = 5$, and it decides nothing whatever.

The real count is about the symbols. Each occurrence of a symbol in the cycle sits inside exactly $k$ windows, and every window containing that symbol arises this way, so the number of occurrences of a symbol times $k$ equals the number of subsets containing it. That gives

$$k \;\big|\; \binom{n-1}{k-1},$$

as a necessary condition, because a symbol cannot occupy a fractional number of positions. For pairs it reads $2 \mid n-1$, which is $n$ odd — the same answer the degrees gave, arrived at without a graph.

So for pairs the real count is not merely necessary; it is sufficient, because Euler’s theorem closes the gap. That makes $k = 2$ a happy case and a misleading one, and the rest of this essay is about what happens when the gap does not close.

The figure settles the smallest failing case twice over. The degree argument says no circuit exists; the exhaustive search generates every one of the $4^6$ cyclic sequences of six symbols and reports that none works. The two agree, which is what an exhaustion is for — the argument might have had a gap, and the search has none.

The naive count is the one a reader supplies unprompted, and it is satisfied here. That is the whole warning of this rung: an object whose pieces would fit is not an object that exists, and the arithmetic that says they would fit is available before any of the work has been done.

Bigger windows, and where the answers run out #

For $k = 3$ the reduction to Euler is gone. A window of three consecutive symbols overlaps the next in two, so the natural structure is a graph whose vertices are ordered pairs and whose edges are triples — but a triple can be read in several orders and the correspondence stops being one-to-one. The problem becomes a Hamiltonian question rather than an Eulerian one, and that change of character is the same one the de Bruijn reduction was built to avoid.

What is known is a mixture of constructions and computation. The real counting condition $3 \mid \binom{n-1}{2}$ rules out many $n$; among those it permits, cycles are known to exist, and the corresponding statement for general $k$ — that the divisibility condition is enough once $n$ is large — was conjectured by Chung, Diaconis and Graham in 1992 and stood until 2020. It is now a theorem, proved by an argument about tours in hypergraphs rather than about sequences, and it is a theorem about large $n$: the small cases remain a list rather than a criterion.

That sentence is the honest state of a subject whose one-dimensional word case has a one-line proof.

Permutations are worse and more interesting, and they are the clean example of the warning above. Here the naive count is not merely satisfied but exact — there are $n!$ permutations and a cycle of $n!$ positions — and no such cycle exists for any $n \ge 3$.

The obstruction is two lines. A window of $n$ symbols that is a permutation contains each symbol exactly once. The next window drops the leftmost symbol and adds a new one at the right; for it also to contain every symbol once, the symbol added must be the one just dropped. So $s_{i+n} = s_i$ for every $i$, the sequence has period $n$, and it therefore has $n$ distinct windows rather than $n!$.

Nothing about that argument is deep and nothing about the counting hinted at it. The repair, due to Chung, Diaconis and Graham, is to use $n+1$ symbols and to ask that each window be order-isomorphic to a permutation rather than equal to one; in that form the cycles exist, and finding them is a real problem.

Why the word case is the easy one #

Standing back, the reason words are easy is worth naming, because it explains everything above.

A window of $n$ letters and the next one overlap in $n-1$ letters, and the overlap determines the transition completely: from a given overlap, each letter of the alphabet gives exactly one next window. So the structure of transitions is a graph in which every vertex has out-degree $k$ and in-degree $k$, and equality of those two numbers is precisely Euler’s condition.

Everything that goes wrong for other families goes wrong at that sentence.

For subsets, the overlap does not determine the transition, because a subset has no order and the symbol leaving the window is not determined by the symbols in it. The in- and out-degrees stop matching and the graph stops being Eulerian.

For arrays, the overlap is not a single object at all: a block overlaps its neighbour to the right and its neighbour below, and there is no walk with two directions.

For permutations, the overlap over-determines the transition, which is the obstruction above: the constraint is so tight that only one continuation is possible and the sequence becomes periodic.

So a de Bruijn sequence exists for every alphabet and length not because the counting works — the counting works in a great many cases where nothing exists — but because words are exactly the family whose overlap structure is a graph with balanced degrees. That is a very special property and it looks like no property at all.

What survives of the reduction #

One thing does carry over from words to every family here, and it is the move the first rung of this ladder was built on.

Given any family of objects and a rule saying which may follow which, there are always two graphs available. Put the objects on the vertices and join two when one may follow the other: finding a listing is then a Hamiltonian path problem, which is hard in general. Put the overlaps on the vertices and the objects on the edges: finding a listing is an Eulerian path problem, which is easy.

The first rung’s lesson was to look for the second encoding. What this rung adds is that the second encoding is not always available — it requires that the overlap determine the transition, and that is a property of the family rather than a choice of the person encoding it. For words it holds. For subsets it does not, which is why $k = 3$ becomes a Hamiltonian question, and why the results there are constructions and computations rather than a criterion.

So the reduction is not a technique that sometimes fails to apply. It is a test: a family admits the easy encoding exactly when its overlaps are informative enough to determine what comes next, and asking that question of a new family is the first thing worth doing.

The pattern of the failure #

There is a general lesson here about existence questions, and it is the reason this ladder ends on a negative result.

A counting condition is derived by asking what an object would have to satisfy. It is always necessary and it is evidence of nothing. When it turns out to be sufficient — as it does for words, and as it does for Latin squares of every order but two and six, and as it fails to for the two orders that were ruled out by exhaustion rather than by arithmetic — that is a theorem needing its own proof, usually a construction. The gap can be enormous: for subsets the condition was written down in 1992 and its sufficiency for large $n$ took twenty-eight years, and in the meantime nothing about the arithmetic changed.

The tempting mistake is to treat the counting as the difficult part. It is the easy part, and it is the part that generalises. What does not generalise is the structural accident that made the counting sufficient, and the whole content of a generalisation is finding out whether that accident survives.

Here it does not. The counting survives every one of the generalisations above; the graph survives none of them.

What the pictures cannot show #

The impossibility is exhibited at one size. All 4,096 cyclic sequences of six symbols from four are generated and none works, which settles $n = 4$. That no even $n$ admits a cycle is the degree argument, and no figure covers it.

The six-point case is not searched either, and its caption says so. There are 470 billion candidate sequences and the panel rests on the degree argument, which is the same argument that settles every even case and needed no search in the first place.

The larger cases are not searched. At $n = 7$ there are $7^{21}$ candidate sequences, so the figure builds the circuit and checks its windows rather than searching. Building the object and verifying it is the honest procedure there; exhaustion is available only where it is cheap.

And no figure here is a de Bruijn sequence, which is the family this ladder is named for and the one whose cycle always exists. Its graph is drawn once, for contrast, and everything else on this page is a family that does not have one.

Nothing here shows a ucycle of triples, which is the case where the subject stops having a clean answer, because the smallest interesting instance has 84 windows and no structure a picture can carry.

And the permutation obstruction is stated rather than drawn. It is a two-line argument about what a window’s successor must be, and drawing three windows would illustrate it without establishing anything.

Where the ladder goes next #

This closes the ladder. It began with a cycle of eight bits holding every three-bit word and the observation that the constraint linking overlapping windows is the construction; it ends with the discovery that this was a fact about words rather than about cycles.

What remains open here is genuinely open. The existence of ucycles for $k$-subsets is settled for $k \le 3$ and for large $n$ at fixed $k$; the general question is not, and neither is the existence question for de Bruijn tori of arbitrary shape. Both are cases where the counting is trivial and the structure is missing.

What that leaves is a subject with a shape worth recognising. The condition is arithmetic, the construction is combinatorial, and between them sits a proof that is neither — the four-colour theorem’s is a computer search, and the 2020 proof for large $n$ is an argument about hypergraph tours that no reader of the original question would have anticipated. Existence results in this corner tend to come from a distance.

Sideways: the objects that admit a listing of this kind are close relatives of combinatorial designs, where the question is not how to sequence every pair but how to partition them, — a resolvable design is a schedule and a ucycle is a tour — and the existence questions there have exactly the same flavour — a divisibility condition that is necessary, occasionally sufficient, and never sufficient for the reason it looks like it should be.

What is worth carrying away #

An existence question has two halves, and the arithmetic half is almost never the difficult one.

Every family of objects considered here has a counting condition, all of the conditions are one line, and all of them are necessary. For words the condition is also sufficient, and the reason is not arithmetic — it is that words overlap in a way that makes a balanced graph. When a generalisation fails, the thing that broke is usually the structure that was doing the work invisibly, and the surviving arithmetic goes on looking like a promise long after it has stopped being one.