EUDML

Let $𝒫$ be a hereditary property of words, i.e., an infinite class of finite words such that every subword (block) of a word belonging to $𝒫$ is also in $𝒫$ . Extending the classical Morse-Hedlund theorem, we show that either $𝒫$ contains at least $n + 1$ words of length $n$ for every $n$ or, for some $N$ , it contains at most $N$ words of length $n$ for every $n$ . More importantly, we prove the following quantitative extension of this result: if $𝒫$ has $m \leq n$ words of length $n$ then, for every $k \geq n + m$ , it contains at most $⌈ (m + 1) / 2 ⌉ ⌊ (m + 1) / 2 ⌋$ words of length...

Hereditary properties of words

József Balogh; Béla Bollobás — 2010

RAIRO - Theoretical Informatics and Applications

Let be a hereditary property of words, , an infinite class of finite words such that every subword (block) of a word belonging to is also in . Extending the classical Morse-Hedlund theorem, we show that either contains at least words of length for every or, for some , it contains at most words of length for every . More importantly, we prove the following quantitative extension of this result: if has words of length then, for every , it contains at most ⌈( + 1)/2⌉⌈( + 1)/2⌈ words of...

Page 1

Download Results (CSV)

Advanced Search

Formula preview

Currently displaying 1 – 13 of 13

k-Tuples of the First n Natural Numbers.

Functionals Close to Each Other.

An extension of the isoperimetric inequality on the sphere.

Best possible bounds of the norms of inverses adjoined to normed algebras

Normally subregular systems in normed algebras

Hereditary properties of words

Hereditary properties of words

Continuous restrictions of linear functionals

Ramsey problems in additive number theory

Hereditary properties of graphs: Asymptotic enumeration, global structure, and colouring.

Degree powers in graphs with forbidden subgraphs.

The sum of degrees in cliques.

Hereditary properties of tournaments.