We obtain the following results about the avoidance of ternary formulas. 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\mapsto 012$, $1\mapsto 02$, $2\mapsto 1$. The formula $ABAC.BACA.ABCA$ is avoided by polynomially many binary words and there exists arbitrarily many infinite binary words with different sets of recurrent factors that avoid it. If every variable of a ternary formula appears at least twice in the same fragment, then the formula is $3$-avoidable. The pattern $ABACADABCA$ is unavoidable for the class of $C_4$-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$.
@article{10_37236_7901,
author = {Pascal Ochem and Matthieu Rosenfeld},
title = {On some interesting ternary formulas},
journal = {The electronic journal of combinatorics},
year = {2019},
volume = {26},
number = {1},
doi = {10.37236/7901},
zbl = {1419.68070},
url = {http://geodesic.mathdoc.fr/articles/10.37236/7901/}
}
TY - JOUR
AU - Pascal Ochem
AU - Matthieu Rosenfeld
TI - On some interesting ternary formulas
JO - The electronic journal of combinatorics
PY - 2019
VL - 26
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/7901/
DO - 10.37236/7901
ID - 10_37236_7901
ER -
%0 Journal Article
%A Pascal Ochem
%A Matthieu Rosenfeld
%T On some interesting ternary formulas
%J The electronic journal of combinatorics
%D 2019
%V 26
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/7901/
%R 10.37236/7901
%F 10_37236_7901
Pascal Ochem; Matthieu Rosenfeld. On some interesting ternary formulas. The electronic journal of combinatorics, Tome 26 (2019) no. 1. doi: 10.37236/7901
