On unavoidable sets of word patterns

Alexander Burstein, Sergey Kitaev

Research output: Contribution to journalArticle

3 Citations (Scopus)

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.
Original languageEnglish
Pages (from-to)371-381
Number of pages11
JournalSIAM Journal on Discrete Mathematics
Volume19
Issue number2
DOIs
Publication statusPublished - 2005

Fingerprint

De Bruijn Graph
Cycle
Overlap
Numerical Study
Subgraph
Refinement
Graph in graph theory

Keywords

  • word pattern
  • universal cycles
  • de Bruijn graph
  • (un)avoidability

Cite this

Burstein, Alexander ; Kitaev, Sergey. / On unavoidable sets of word patterns. In: SIAM Journal on Discrete Mathematics. 2005 ; Vol. 19, No. 2. pp. 371-381.
@article{c909e8a95f654f36b173b8c9f4b31eba,
title = "On unavoidable sets of word patterns",
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 = "word pattern, universal cycles, de Bruijn graph, (un)avoidability",
author = "Alexander Burstein and Sergey Kitaev",
year = "2005",
doi = "10.1137/S0895480104445678",
language = "English",
volume = "19",
pages = "371--381",
journal = "SIAM Journal on Discrete Mathematics",
issn = "0895-4801",
number = "2",

}

On unavoidable sets of word patterns. / Burstein, Alexander; Kitaev, Sergey.

In: SIAM Journal on Discrete Mathematics, Vol. 19, No. 2, 2005, p. 371-381.

Research output: Contribution to journalArticle

TY - JOUR

T1 - On unavoidable sets of word patterns

AU - Burstein, Alexander

AU - Kitaev, Sergey

PY - 2005

Y1 - 2005

N2 - 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.

AB - 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.

KW - word pattern

KW - universal cycles

KW - de Bruijn graph

KW - (un)avoidability

UR - http://arxiv.org/abs/math/0311399

U2 - 10.1137/S0895480104445678

DO - 10.1137/S0895480104445678

M3 - Article

VL - 19

SP - 371

EP - 381

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

SN - 0895-4801

IS - 2

ER -