Skip to Main content Skip to Navigation
Journal articles

On some interesting ternary formulas

Pascal Ochem 1 Matthieu Rosenfeld 2
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : We obtain the following results about the avoidance of ternary formulas. Upto renaming of the letters, the only infinite ternary words avoiding the formula ABCAB.ABCBA.ACB.BAC(resp.ABCA.BCAB.BCB.CBA) are the ones thathave the same set of recurrent factors as the fixed point of07→012,17→02,27→1. The formula ABAC.BACA.ABCA is avoided by polynomially many binarywords (w.r.t. to their lengths) and there exist arbitrarily many infinite binarywords with different sets of recurrent factors that avoid it. If every variable of aternary formula appears at least twice in the same fragment, then the formula is3-avoidable. The pattern ABACADABCA is unavoidable for the class ofC4-minor-free graphs with maximum degree 3. This disproves a conjecture of Grytczuk. The formula ABCA.ACBA, or equivalently the palindromic pattern ABCADACBA, has avoidability index 4.
Document type :
Journal articles
Complete list of metadata

Cited literature [16 references]  Display  Hide  Download
Contributor : Pascal Ochem <>
Submitted on : Friday, March 29, 2019 - 10:30:36 AM
Last modification on : Wednesday, November 4, 2020 - 6:08:04 PM
Long-term archiving on: : Sunday, June 30, 2019 - 1:28:16 PM


Distributed under a Creative Commons Attribution - NoDerivatives 4.0 International License



Pascal Ochem, Matthieu Rosenfeld. On some interesting ternary formulas. The Electronic Journal of Combinatorics, Open Journal Systems, 2019, 26 (1), pp.P1.12. ⟨10.37236/7901⟩. ⟨lirmm-02083616⟩



Record views


Files downloads