An upper bound of the number of distinct powers in binary words

DOI10.1016/J.DISC.2024.113902MaRDI QIDQ6197757zbMATH OpenWikidataFDO

Authors Shuo Li

Publication date 19 February 2024

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

binary wordscombinatorics on wordssquare factors

Mathematics Subject Classification ID

Enumerative combinatorics (05Axx) Graph theory (05Cxx) Discrete mathematics in relation to computer science (68Rxx)

Abstract: A power is a word of the form $underbrace{uu\mathrm{...}u}_{k;exttimes}$, where $u$ is a word and $k$ is a positive integer and a square is a word of the form $uu$. Fraenkel and Simpson conjectured in 1998 that the number of distinct squares in a word is bounded by the length of the word. This conjecture was proven recently by Brlek and Li. Besides, there exists a stronger upper bound for binary words conjectured by Jonoska, Manea and Seki stating that for a word of length $n$ over the alphabet $lefta,bight$, if we let $k$ be the least of the number of a's and the number of b's and $kgeq2$, then the number of distinct squares is upper bounded by $frac2k-12k+2n$. In this article, we prove this conjecture by giving a stronger statement on the number of distinct powers in a binary word.

Cites work

• A note on the number of squares in a word
• A stronger square conjecture on binary words
• How many double squares can a string contain?
• How many squares can a string contain?
• scientific article; zbMATH DE number 3871492 (Why is no real title available?)
• k-optimal partitions of a directed graph
• On the maximum number of cubic subwords in a word
• On the number of \(k\)-powers in a finite word
• Square-density increasing mappings

This page was built for publication: An upper bound of the number of distinct powers in binary words

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