Van der Waerden's Theorem and Avoidability in Words

DOI10.1515/INTEG.2011.007zbMATH Open1209.68392arXiv0812.2466MaRDI QIDQ3081580FDOQ3081580

Authors: Aaron Robertson, Yu Hin Au, Jeffrey Shallit 

Publication date: 9 March 2011

Published in: Integers (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/0812.2466

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

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

zbMATH Keywords

Van der Waerden's theoremabelian squarepattern avoidability

Mathematics Subject Classification ID

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

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)