Mathematics – Combinatorics
Scientific paper
2011-03-19
Mathematics
Combinatorics
5 pages, no figures.arXiv admin note: substantial text overlap with arXiv:1103.3810
Scientific paper
A sequence is nonrepetitive if it does not contain two adjacent identical blocks. The remarkable construction of Thue asserts that 3 symbols are enough to build an arbitrarily long nonrepetitive sequence. It is still not settled whether the following extension holds: for every sequence of 3-element sets $L_1,..., L_n$ there exists a nonrepetitive sequence $s_1, ..., s_n$ with $s_i\in L_i$. Applying the probabilistic method one can prove that this is true for sufficiently large sets $L_i$. We present an elementary proof that sets of size 4 suffice (confirming the best known bound). The argument is a simple counting with Catalan numbers involved. Our approach is inspired by a new algorithmic proof of the Lov\'{a}sz Local Lemma due to Moser and Tardos and its interpretations by Fortnow and Tao. The presented method has further applications to nonrepetitive games and nonrepetitive colorings of graphs.
Grytczuk Jarosław
Kozik Jakub
Micek Piotr
No associations
LandOfFree
A new approach to nonrepetitive sequences does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A new approach to nonrepetitive sequences, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A new approach to nonrepetitive sequences will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-695106