Van der Waerden's Theorem and Avoidability in Words

DOI10.1515/INTEG.2011.007MaRDI QIDQ3081580zbMATH OpenFDO

Authors Aaron Robertson, Yu Hin Au, Jeffrey Shallit

Publication date 9 March 2011

Published in Integers (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0812.2466, https://eudml.org/doc/232698, http://www.integers-ejcnt.org/vol11.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

Van der Waerden's theoremabelian squarepattern avoidability

Mathematics Subject Classification ID

Combinatorics on words (68R15) Ramsey theory (05D10) Arithmetic progressions (11B25)

Abstract: Pirillo and Varricchio, and independently, Halbeisen and Hungerbuhler considered the following problem, open since 1994: Does there exist an infinite word w over a finite subset of Z such that w contains no two consecutive blocks of the same length and sum? We consider some variations on this problem in the light of van der Waerden's theorem on arithmetic progressions.

Recommendations

• Binary avoidability and Thue-Morse words
• On the Complexity of Deciding Avoidability of Sets of Partial Words
• On the complexity of deciding avoidability of sets of partial words
• Problems in between words and abelian words: \(k\)-abelian avoidability
• scientific article; zbMATH DE number 3873610
• Testing avoidability on sets of partial words is hard
• Open problems on avoidable patterns in partial words
• Classifying all avoidable sets of partial words of size two
• On weakly self-avoiding words
• scientific article; zbMATH DE number 4168694

Cited in

(3)

• Avoiding three consecutive blocks of the same size and same sum
• Sequences on sets of four numbers
• AVOIDING ABELIAN POWERS IN BINARY WORDS WITH BOUNDED ABELIAN COMPLEXITY

This page was built for publication: Van der Waerden's Theorem and Avoidability in Words

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3081580)