On some interesting ternary formulas
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.
Domains
Discrete Mathematics [cs.DM]
Loading...