Advanced Search

Blanched-Sadri and Woodhouse in 2013 have proven the conjecture of Cassaigne, stating that any pattern with m distinct variables and of length at least 2m is avoidable over a ternary alphabet and if the length is at least 3 2m−1 it is avoidable over a binary alphabet. They conjectured that similar theorems are true for partial words - sequences, in which some characters are left “blank”. Using method of entropy compression, we obtain the partial words version of the theorem for ternary words

Blanched-Sadri and Woodhouse in 2013 have proven the conjecture of Cassaigne, stating that any pattern with $m$ distinct variables and of length at least $2^m$ is avoidable over a ternary alphabet and if the length is at least $3·2^{m-1}$ it is avoidable over a binary alphabet. They conjectured that similar theorems are true for partial words – sequences, in which some characters are left “blank”. Using method of entropy compression, we obtain the partial words version of the theorem for ternary words.