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 metadatas

Cited literature [16 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-02083616
Contributor : Pascal Ochem <>
Submitted on : Friday, March 29, 2019 - 10:30:36 AM
Last modification on : Thursday, April 2, 2020 - 11:59:27 AM
Document(s) archivé(s) le : Sunday, June 30, 2019 - 1:28:16 PM

Licence


Distributed under a Creative Commons Attribution - NoDerivatives 4.0 International License

Identifiers

Citation

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⟩

Share

Metrics

Record views

131

Files downloads

182