MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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. An edge $w_\ell \dots w_{\ell+k}$ connects the vertices $w_\ell \dots w_{\ell+k-1}$ and $w_{\ell+1} \dots w_{\ell+k}$. If $w$ is a de Bruijn sequence, $G_k(w)$ is a de Bruijn graph, and vice versa. 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.)

share|cite|improve this question
I just realized that this is likely to be very hard indeed, as it appears related to Levin's universal one-way "tiling expansion" function. See – Steve Huntsman Sep 17 '10 at 18:27
Could you explain what is the exact relation? I tried reading Levin's paper and I could not understands the tiling expansion problem clearly. – Turbo Sep 25 '13 at 13:10

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.