On the number of squares in a finite word (Q7006799)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 8017581
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | On the number of squares in a finite word |
scientific article; zbMATH DE number 8017581 |
Statements
On the number of squares in a finite word (English)
0 references
27 March 2025
0 references
The authors prove the 1998 conjecture by \textit{A. S. Fraenkel} and \textit{J. Simpson} [J. Comb. Theory, Ser. A 82, No. 1, 112--120 (1998; Zbl 0910.05001)] and even its stonger 2011 version stated by \textit{A. Deza} et al. [Lect. Notes Comput. Sci. 6661, 77--89 (2011; Zbl 1339.68217)]: For a given finite word \(w\), the number of distinct square factors of \(w\) is bounded by \(|w|-d\), where \(|w|\) denotes the length of \(w\) and \(d\) is the number of distinct letters in \(w\).\N\NThe proof is surprisingly short and beautiful and uses the structure of Rauzy graphs.
0 references
combinatorics on words
0 references
squares
0 references
repetition
0 references
Fraenkel-Simpson conjecture
0 references
