New approach to nonrepetitive sequences
From MaRDI portal
Publication:4909201
2-person games (91A05) Combinatorial aspects of tessellation and tiling problems (05B45) Combinatorics on words (68R15) Games involving topology, set theory, or logic (91A44) Thue and Post systems, etc. (03D03) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)
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
(45)- A Novel Riccati Sequence
- A new application of non-increasing sequences
- Avoiding squares over words with lists of size three amongst four symbols
- Generalized arboricity of graphs with large girth
- How to play Thue games
- Progress on the adjacent vertex distinguishing edge coloring conjecture
- The list chromatic number of graphs with small clique number
- Every plane graph is facially-non-repetitively \(C\)-choosable
- New bounds for facial nonrepetitive colouring
- Entropy compression versus Lovász local lemma
- Fractional meanings of nonrepetitiveness
- How far away must forced letters be so that squares are still avoidable?
- On the facial Thue choice number of plane graphs via entropy compression method
- Anagram-Free Colorings of Graph Subdivisions
- On harmonious coloring of hypergraphs
- Nonrepetitive colouring via entropy compression
- Extensions and reductions of squarefree words
- Facially-constrained colorings of plane graphs: a survey
- Nonrepetitive list colorings of the integers
- Edge colorings avoiding patterns
- Edge colorings avoiding patterns
- On triangle-free list assignments
- Another approach to non-repetitive colorings of graphs of bounded degree
- On the facial Thue choice index via entropy compression
- Novel structures in Stanley sequences
- Witness trees in the Moser-Tardos algorithmic Lovász local lemma and Penrose trees in the hard-core lattice gas
- A note on Thue games
- Ann wins the nonrepetitive game over four letters and the erase-repetition game over six letters
- Approaching repetition thresholds via local resampling and entropy compression
- A local lemma for focused stochastic algorithms
- Acyclic coloring of graphs and entropy compression method
- A short proof that shuffle squares are 7-avoidable
- Online version of the theorem of Thue
- Pattern avoidance in partial words over a ternary alphabet
- Non-repetitive strings over alphabet lists
- Anagram-free graph colouring
- Nonrepetitive sequences on arithmetic progressions
- Pathwidth and nonrepetitive list coloring
- The local cut lemma
- Acyclic edge-coloring using entropy compression
- Improved bounds for centered colorings
- Non-constructive upper bounds for repetition thresholds
- Moser-Tardos resampling algorithm, entropy compression method and the subset gas
- Total Thue colourings of graphs
- Highly nonrepetitive sequences: winning strategies from the local Lemma
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)
