On Unavoidable Sets of Word Patterns

DOI10.1137/S0895480104445678MaRDI QIDQ5470765zbMATH OpenFDO

Authors Alexander Burstein, Sergey Kitaev

Publication date 1 June 2006

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0311399

zbMATH Keywords

(un)avoidabilityde Bruijn graphStirling numbers of the second kinduniversal cycles

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Combinatorics on words (68R15)

Abstract: We introduce the notion of unavoidable (complete) sets of word patterns, which is a refinement for that of words, and study certain numerical characteristics for unavoidable sets of patterns. In some cases we employ the graph of pattern overlaps introduced in this paper, which is a subgraph of the de Bruijn graph and which we prove to be Hamiltonian. In other cases we reduce a problem under consideration to known facts on unavoidable sets of words. We also give a relation between our problem and intensively studied universal cycles, and prove there exists a universal cycle for word patterns of any length over any alphabet. Keywords: pattern, word, (un)avoidability, de Bruijn graph, universal cycles

Recommendations

• scientific article; zbMATH DE number 3980522
• UNAVOIDABLE AND ALMOST UNAVOIDABLE SETS OF WORDS
• Unavoidable sets of partial words
• Long unavoidable patterns
• Unavoidable sets

Cited in

(7)

• On uniquely k-determined permutations
• Unary Pattern Avoidance in Partial Words Dense with Holes
• Unavoidable regularities in long words with bounded number of symbol occurrences
• Pattern occurrence statistics and applications to the Ramsey theory of unavoidable patterns
• Density dichotomy in random words
• On Long Words Avoiding Zimin Patterns
• Introduction to partially ordered patterns

This page was built for publication: On Unavoidable Sets of Word Patterns

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