Current browse context:
math.CO
Change to browse by:
References & Citations
Mathematics > Combinatorics
Title: Smallest and Largest Block Palindrome Factorizations
(Submitted on 25 Feb 2023 (v1), last revised 13 Apr 2023 (this version, v2))
Abstract: A \emph{palindrome} is a word that reads the same forwards and backwards. A \emph{block palindrome factorization} (or \emph{BP-factorization}) is a factorization of a word into blocks that becomes palindrome if each identical block is replaced by a distinct symbol. We call the number of blocks in a BP-factorization the \emph{width} of the BP-factorization. The \emph{largest BP-factorization} of a word $w$ is the BP-factorization of $w$ with the maximum width. We study words with certain BP-factorizations. First, we give a recurrence for the number of length-$n$ words with largest BP-factorization of width $t$. Second, we show that the expected width of the largest BP-factorization of a word tends to a constant. Third, we give some results on another extremal variation of BP-factorization, the \emph{smallest BP-factorization}. A \emph{border} of a word $w$ is a non-empty word that is both a proper prefix and suffix of $w$. Finally, we conclude by showing a connection between words with a unique border and words whose smallest and largest BP-factorizations coincide.
Submission history
From: Daniel Gabric [view email][v1] Sat, 25 Feb 2023 20:05:16 GMT (24kb)
[v2] Thu, 13 Apr 2023 18:10:14 GMT (24kb)
Link back to: arXiv, form interface, contact.