Skip to main content
1 of 3
JRN
  • 1.3k
  • 4
  • 22
  • 45

Subwords of cube-free binary words

I'm currently working on subwords of cube-free binary words.

A binary word is one composed of letters from a two-letter alphabet such as $\{0,1\}$. A word $y$ is a subword of $w$ if there exist words $x$ and $z$ (possibly empty) such that $w=xyz$. Thus, $01$ is a subword of $0110$, but $00$ is not a subword of $0110$. A word is cube-free if it does not contain subwords of the form $xxx$, where $x$ is a word of one or more letters.

I suspect that all sufficiently long cube-free binary words (those whose length is greater than a certain $n$) contain all the subwords $001$, $010$, $011$, $100$, $101$, and $110$. I know that $n\ge 21$ because the cube-free binary word $110011001101100110011$ has a length of 21 and does not contain the subword $010$.

Does anyone know the length of the longest cube-free binary word that does not contain all the three-letter subwords I mentioned above?

JRN
  • 1.3k
  • 4
  • 22
  • 45