On Some Interesting Ternary Formulas

Pascal Ochem (1) , Matthieu Rosenfeld (2)

1 ALGCO - Algorithmes, Graphes et Combinatoire
2 MC2 - Modèles de calcul, Complexité, Combinatoire

We show that, up to renaming of the letters, the only infinite ternary words avoiding the formula ABCAB.ABCBA.ACB.BAC (resp. ABCA.BCAB.BCB.CBA) have the same set of recurrent factors as the fixed point of $0->012,1->02,2->1$ Also, we show that the formula ABAC.BACA.ABCA is 2-avoidable. Finally, we show that the pattern ABACADABCA is unavoidable for the class of $C_4$-minor-free graphs with maximum degree 3. This disproves a conjecture of Grytczuk.

Mots clés: Combinatorics on words; Pattern avoidance

Domaines: Mathématique discrète [cs.DM]; Combinatoire [math.CO]

Pascal Ochem, Matthieu Rosenfeld. On Some Interesting Ternary Formulas. WORDS 2017 - 11th International Conference on Combinatorics on Words, Sep 2017, Montreal, Canada. pp.30-35, ⟨10.1007/978-3-319-66396-8_4⟩. ⟨lirmm-02078252⟩