Return to Answer

I have some unpublished notes that I think are relevant to this problem, and I am cherry-picking from them. (See also here for a related question.) Because the notes are unpublished I hope it will not be considered poor form to provide a rather lengthy response.

I have some unpublished notes that I think are relevant to this problem, and I am cherry-picking from them. (See also here for a related question.) Because the notes are unpublished I hope it will not be considered poor form to provide a rather lengthy response.

alt text http://eqnets.files.wordpress.com/2010/01/mathoverflow0001.png

alt text http://eqnets.files.wordpress.com/2010/01/mathoverflow0002.png

alt text http://eqnets.files.wordpress.com/2010/01/mathoverflow0003.png

As Gerald suggests, the problem can be recast in terms of necklaces and their subwords of length $k$. We introduce the appellation dimgraph for “directed multigraph”. Let $[w]_k$ denote the generalized order $(k – 1)$ de Bruijn dimgraph of the $q$-ary word $w$: i.e., vertices correspond to the $(k – 1)$-tuples, and directed edges correspond to the $k$-tuples in $w$ in the usual way. If $[w′]_k = [w]_k$, we say that $w$ and $w′$ belong to the same order $k$ de Bruijn homology class. It is easy to see that this really is an equivalence relation, which we denote $\sim_k$ (suppressing subscripts when there is no risk of confusion). If the size of an equivalence class is greater than unity, it will be necessary to take into account the additional data associated to $p$, but I will not touch on that (or on the formula to determine the multiplicity of a nontrivial equivalence class, though if anyone wants this please leave a comment and I will try to reply with a PDF) here.

As Gerhard suggests, the problem can be recast in terms of necklaces and their subwords of length $k$. We introduce the appellation dimgraph for “directed multigraph”. Let $[w]_k$ denote the generalized order $(k – 1)$ de Bruijn dimgraph of the $q$-ary word $w$: i.e., vertices correspond to the $(k – 1)$-tuples, and directed edges correspond to the $k$-tuples in $w$ in the usual way. If $[w′]_k = [w]_k$, we say that $w$ and $w′$ belong to the same order $k$ de Bruijn homology class. It is easy to see that this really is an equivalence relation, which we denote $\sim_k$ (suppressing subscripts when there is no risk of confusion). If the size of an equivalence class is greater than unity, it will be necessary to take into account the additional data associated to $p$, but I will not touch on that (or on the formula to determine the multiplicity of a nontrivial equivalence class, though if anyone wants this please leave a comment and I will try to reply with a PDF) here.