Words avoiding repetitions in arithmetic progressions

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

Carpi constructed an infinite word over a 4-letter alphabet that avoids squares in all subsequences indexed by arithmetic progressions of odd difference. We show a connection between Carpi's construction and the paperfolding words. We extend Carpi's result by constructing uncountably many words that avoid squares in arithmetic progressions of odd difference. We also construct infinite words avoiding overlaps and infinite words avoiding arbitrarily large squares in arithmetic progressions of odd difference. We use these words to construct labelings of the 2-dimensional integer lattice such that any line through the lattice encounters a squarefree (resp. overlapfree) sequence of labels.
18 pages; Manuel Silva added as a co-author

Keywords

Combinatorics, 68R15

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/115546

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/math/0608607
 http://arxiv.org/abs/math/0608607

Collections

arXiv