pith. sign in

arxiv: 1706.03233 · v2 · pith:LKDO2LENnew · submitted 2017-06-10 · 💻 cs.DM

On some interesting ternary formulas

classification 💻 cs.DM
keywords textttformulaternaryabcamapstowordsbinaryfactors
0
0 comments X
read the original abstract

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 $\texttt{0}\mapsto\texttt{012}$, $\texttt{1}\mapsto\texttt{02}$, $\texttt{2}\mapsto\texttt{1}$. The formula $ABAC.BACA.ABCA$ is avoided by polynomially many binary words and there exist 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$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.