New approach to nonrepetitive sequences
From MaRDI portal
Publication:4909201
DOI10.1002/RSA.20411zbMATH Open1349.68131arXiv1103.3809OpenAlexW3123973497MaRDI QIDQ4909201FDOQ4909201
Jakub Kozik, Piotr Micek, Jarosław Grytczuk
Publication date: 12 March 2013
Published in: Random Structures \& Algorithms (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1103.3809
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)
Cites Work
- Avoidable patterns in strings of symbols
- Automatic Sequences
- Every planar graph is 5-choosable
- Nonrepetitive list colourings of paths
- A constructive proof of the general lovász local lemma
- Thue choosability of trees
- Nonrepetitive colorings of graphs
- Nonrepetitive colorings of graphs -- a survey
- Thue type problems for graphs, points, and numbers
- Highly nonrepetitive sequences: Winning strategies from the local lemma
- Pattern avoidance: themes and variations
- Nonrepetitive colorings of graphs of bounded tree-width
- On square-free vertex colorings of graphs
Cited In (41)
- 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
- 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
- How far away must forced letters be so that squares are still avoidable?
- Fractional meanings of nonrepetitiveness
- A Local Lemma for Focused Stochastic Algorithms
- On the facial Thue choice number of plane graphs via entropy compression method
- On harmonious coloring of hypergraphs
- Anagram-Free Colorings of Graph Subdivisions
- Nonrepetitive colouring via entropy compression
- Extensions and reductions of squarefree words
- Facially-constrained colorings of plane graphs: a survey
- Edge colorings avoiding patterns
- Edge colorings avoiding patterns
- On triangle-free list assignments
- Nonrepetitive list colorings of the integers
- Another approach to non-repetitive colorings of graphs of bounded degree
- Novel structures in Stanley sequences
- 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
- 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
- A short proof that shuffle squares are 7-avoidable
- Acyclic coloring of graphs and entropy compression method
- Progress on the Adjacent Vertex Distinguishing Edge Coloring Conjecture
- Pattern avoidance in partial words over a ternary alphabet
- Anagram-free graph colouring
- The local cut lemma
- Pathwidth and nonrepetitive list coloring
- Improved Bounds for Centered Colorings
- Non-constructive upper bounds for repetition thresholds
- Acyclic edge-coloring using entropy compression
- Moser-Tardos resampling algorithm, entropy compression method and the subset gas
- On the Facial Thue Choice Index via Entropy Compression
- Total Thue colourings of graphs
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)
