Pattern occurrence statistics and applications to the Ramsey theory of unavoidable patterns

MaRDI QIDQ4626557zbMATH OpenFDO

Authors Jim Tao

Publication date 28 February 2019

Full work available at URL https://arxiv.org/abs/1406.0450, http://web.math.rochester.edu/misc/ojac/vol13/104.pdf

zbMATH Keywords

abelian patternsanalytic combinatoricscombinatorics on wordspartial wordsprobabilistic methodRamsey theoryunavoidable patterns

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Asymptotic enumeration (05A16) Combinatorics on words (68R15)

Abstract: As suggested by Currie, we apply the probabilistic method to problems regarding pattern avoidance. Using techniques from analytic combinatorics, we calculate asymptotic pattern occurrence statistics and use them in conjunction with the probabilistic method to establish new results about the Ramsey theory of unavoidable patterns in the full word case (both nonabelian sense and abelian sense) and in the partial word case. Keywords: Combinatorics on words; Partial words; Unavoidable patterns; Abelian patterns; Probabilistic method; Analytic combinatorics; Ramsey theory.

Recommendations

• Finite automata, probabilistic method, and occurrence enumeration of a pattern in words and permutations
• Pattern avoidance: themes and variations
• On Unavoidable Sets of Word Patterns
• Tower-type bounds for unavoidable patterns in words
• Strict bounds for pattern avoidance

Cites work

• A hybrid of Darboux's method and singularity analysis in combinatorial asymptotics
• Abelian pattern avoidance in partial words
• ALGORITHMIC PROBLEMS IN VARIETIES
• Analytic combinatorics
• Applications of an infinite square-free co-CFL
• Avoiding Abelian squares in partial words
• Characterization of the repetitive commutative semigroups
• Computing the partial word avoidability indices of binary patterns
• Computing the partial word avoidability indices of ternary patterns
• scientific article; zbMATH DE number 53883 (Why is no real title available?)
• scientific article; zbMATH DE number 1503606 (Why is no real title available?)
• scientific article; zbMATH DE number 1737190 (Why is no real title available?)
• scientific article; zbMATH DE number 3324797 (Why is no real title available?)
• Intervals in the lattice of varieties
• Introduction to modern cryptography.
• Mathematics and computer science: coping with finiteness
• Some combinatorial properties of the Thue-Morse sequence and a problem in semigroups
• The complexity of songs

Cited in

(3)

• Critical properties and complexity measures of read-once Boolean functions
• Finite automata, probabilistic method, and occurrence enumeration of a pattern in words and permutations
• Pattern avoidance: themes and variations

This page was built for publication: Pattern occurrence statistics and applications to the Ramsey theory of unavoidable patterns

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4626557)