Cubefree binary words avoiding long squares

Simple item page
dc.creatorRampersad, Narad
dc.creatorShallit, Jeffrey
dc.creatorWang, Ming-wei
dc.date2003-02-25
dc.date2003-04-07
dc.date.accessioned2026-07-07T04:55:34Z
dc.date.available2026-07-07T04:55:34Z
dc.descriptionEntringer, Jackson, and Schatz conjectured in 1974 that every infinite cubefree binary word contains arbitrarily long squares. In this paper we show this conjecture is false: there exist infinite cubefree binary words avoiding all squares xx with |x| >= 4, and the number 4 is best possible. However, the Entringer-Jackson-Schatz conjecture is true if "cubefree" is replaced with "overlap-free".
dc.descriptionPLEASE NOTE: After this paper was prepared, we learned that all our results appeared (albeit with different proofs) in a paper of F. M. Dekking, On repetitions of blocks in binary sequences, J. Combin. Theory Ser. A 20 (1976), 292--299
dc.identifierhttps://arxiv.org/abs/math/0302303
dc.identifierhttp://arxiv.org/abs/math/0302303
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/66619
dc.subjectCombinatorics
dc.subjectDiscrete Mathematics
dc.subject68R15
dc.titleCubefree binary words avoiding long squares
dc.typetext

Files

Collections

arXiv