Thue and Post systems, etc. (03D03) Combinatorial aspects of tessellation and tiling problems (05B45) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Combinatorics on words (68R15) 2-person games (91A05) Games involving topology, set theory, or logic (91A44)
Abstract: 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 there exists a nonrepetitive sequence with . Applying the probabilistic method one can prove that this is true for sufficiently large sets . 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.
Recommendations
Cites work
- A constructive proof of the general Lovász local lemma
- Automatic Sequences
- Avoidable patterns in strings of symbols
- Every planar graph is 5-choosable
- Highly nonrepetitive sequences: winning strategies from the local Lemma
- Nonrepetitive colorings of graphs
- Nonrepetitive colorings of graphs -- a survey
- Nonrepetitive colorings of graphs of bounded tree-width
- Nonrepetitive list colourings of paths
- On square-free vertex colorings of graphs
- Pattern avoidance: themes and variations
- Thue choosability of trees
- Thue type problems for graphs, points, and numbers
Cited in
(49)- The list chromatic number of graphs with small clique number
- Generalized arboricity of graphs with large girth
- Every plane graph is facially-non-repetitively \(C\)-choosable
- Anagram-free graph colouring
- Online version of the theorem of Thue
- Entropy compression versus Lovász local lemma
- Nonrepetitive list colorings of the integers
- Fractional meanings of nonrepetitiveness
- Another approach to non-repetitive colorings of graphs of bounded degree
- Acyclic coloring of graphs and entropy compression method
- Total Thue colourings of graphs
- How to play Thue games
- The local cut lemma
- Facially-constrained colorings of plane graphs: a survey
- New bounds for facial nonrepetitive colouring
- Acyclic edge-coloring using entropy compression
- Pattern avoidance in partial words over a ternary alphabet
- A new application of non-increasing sequences
- Moser-Tardos resampling algorithm, entropy compression method and the subset gas
- On the facial Thue choice index via entropy compression
- On the facial Thue choice number of plane graphs via entropy compression method
- Highly nonrepetitive sequences: winning strategies from the local Lemma
- A short proof that shuffle squares are 7-avoidable
- A note on Thue games
- Anagram-Free Colorings of Graph Subdivisions
- Pathwidth and nonrepetitive list coloring
- Avoiding squares over words with lists of size three amongst four symbols
- How far away must forced letters be so that squares are still avoidable?
- Progress on the adjacent vertex distinguishing edge coloring conjecture
- Improved bounds for centered colorings
- Non-repetitive strings over alphabet lists
- Nonrepetitive colouring via entropy compression
- A local lemma for focused stochastic algorithms
- A Novel Riccati Sequence
- Approaching repetition thresholds via local resampling and entropy compression
- Extensions and reductions of squarefree words
- Edge colorings avoiding patterns
- On triangle-free list assignments
- Ann wins the nonrepetitive game over four letters and the erase-repetition game over six letters
- Nonrepetitive sequences on arithmetic progressions
- On harmonious coloring of hypergraphs
- Edge colorings avoiding patterns
- Non-constructive upper bounds for repetition thresholds
- Words avoiding tangrams
- The nonrepetitive coloring of grids
- Fast algorithms for Vizing's theorem on bounded degree graphs
- A linear-time algorithm for (1+)-edge-coloring
- Witness trees in the Moser-Tardos algorithmic Lovász local lemma and Penrose trees in the hard-core lattice gas
- Novel structures in Stanley sequences
This page was built for publication: New approach to nonrepetitive sequences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4909201)
