Problems in Pattern Avoidance

This area is rich in wonderful problems. To understand these problems, I recommend that you read my introduction to words avoiding patterns.

  1. Dejean's Conjecture: Show that RT(n) = n/(n-1), n > 11.
  2. Is there a pattern p which is 5-avoidable but not 4-avoidable? See Baker, McNulty & Taylor.
  3. The antichain problem: Fix an alphabet S, and let p be S-avoidable. Let L be the set of finite words over S avoiding p. Must there be an infinite set M in L such that s avoids t whenever s and t are in M?
  4. Prove or disprove: If p is k-avoidable, then p is k-HD0L-avoidable.
  5. Is c(n), the number of non-repetitive words of length n over {1, 2, 3}, asymptotic to an, some constant a?
  6. Prove or disprove: Let an alphabet S be given and let p be S-avoidable. There is a word w over S avoiding p, but such that every extension of w encounters p.
  7. Prove or disprove: Let an alphabet S be given and let p be S-avoidable. Let a word u over S avoiding p be given. There is an extension w of u in S* avoiding p but such that every extension of w encounters p.
  8. Determine ART(n), n > 3.
  9. What is the complexity of deciding whether a given pattern is avoidable?
  10. Identify the undecidable (exponential, NP-hard) problems in this area.