On some interesting ternary formulas - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Journal Articles The Electronic Journal of Combinatorics Year : 2019

On some interesting ternary formulas

Pascal Ochem
Matthieu Rosenfeld


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.
Fichier principal
Vignette du fichier
7901-PDF file-26937-1-10-20190117.pdf (251.54 Ko) Télécharger le fichier

Dates and versions

lirmm-02083616 , version 1 (29-03-2019)


Attribution - NoDerivatives



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



Gmail Facebook X LinkedIn More