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.)
No comments:
Post a Comment