Skip to main content
2 of 4
added 132 characters in body; deleted 55 characters in body; edited body
Steve Huntsman
  • 15.4k
  • 7
  • 75
  • 130

Enumerating (generalized) de Bruijn tori

Given a cyclic word $w$ of length $N$ over a $q$-ary alphabet and $k \in \mathbb{Z}_+$, consider the directed multigraph $G_k(w) = (V,E)$ with $V \subset$ {$1,\dots,q$}$^k$ given by the $k$-lets (i.e., subwords of $k$ symbols) that appear in $w$ (without multiplicity) and $E$ given by the $(k+1)$-lets in $w$ that appear with multiplicity. If $w$ is a de Bruijn sequence, $G_k(w)$ is a de Bruijn graph. So call $G_k(w)$ the generalized de Bruijn graph corresponding to $w$ and $k$. It is not hard to compute the number of words $w'$ having $G_k(w)$ as their generalized de Bruijn graph, using the matrix-tree and BEST theorems.

In two dimensions, the picture is much less clear. De Bruijn tori are basically periodic rectangular arrays of symbols in which all possible subarrays of a certain size occur with multiplicity 1. There is a structure (a hypergraph?)--the "generalized de Bruijn structure"--corresponding to a generic rectangular array of symbols in a generalization of the sketch above, so by analogy call a rectangular array of symbols over a finite alphabet a generalized de Bruijn torus in this context.

Given one generalized de Bruijn torus, how many others share its multiplicities of rectangular subarrays (equivalently, its generalized de Bruijn structure)?

(Note that even the existence of de Bruijn tori for nonsquare subarrays is uncertain, which is why I'm working in the "generalized" context.)

Steve Huntsman
  • 15.4k
  • 7
  • 75
  • 130