On some interesting ternary formulas - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Article Dans Une Revue The Electronic Journal of Combinatorics Année : 2019

On some interesting ternary formulas

Pascal Ochem
Matthieu Rosenfeld

Résumé

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
Loading...

Dates et versions

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

Licence

Paternité - Pas de modifications

Identifiants

Citer

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 Consultations
100 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More