Timeline for A word with maximal number of subwords
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 16, 2012 at 12:14 | comment | added | user6976 | Here is a nice paper on subword complexity that gives the same answer: csd.uwo.ca/faculty/ilie/IJFCS04.pdf . | |
| Sep 15, 2012 at 20:41 | comment | added | Steve Huntsman | You can go the other way too. If you have a prescribed multiplicity for each word, you can form a corresponding directed (Eulerian) multigraph in an obvious generalization of the de Bruijn construction. Then you can use the matrix-tree and BEST theorems to enumerate the sequences with these multiplicities. If you google "generalized de Bruijn" and restrict to site:mathoverflow.net you'll find one or two posts of mine on this topic. | |
| Sep 15, 2012 at 17:48 | vote | accept | CommunityBot | moved from User.Id=6976 by developer User.Id=69903 | |
| Sep 15, 2012 at 17:20 | comment | added | Gerhard Paseman | A similar analysis applies for general n. If m is the smallest integer such that every subword of n of length m is unique, then the number of unique subwords total is at least n(n-m+1). Thus m will always be at least floor(log n). But it should be possible to find a length n fragment of a Debruijn word which will achieve minimal m, as well as attain the largest number of distinct subwords of smaller length. Gerhard "Ask Me About System Design" Paseman, 2012.09.15 | |
| Sep 15, 2012 at 16:41 | history | answered | Ian Agol | CC BY-SA 3.0 |