Scholarlink

The so-called MP-ratio is a kind of measure of how “packed with palindromes” a given word is. The lower bound on the MP-ratio for the set of all n-ary words is (trivially) 1, while the best possible upper bound is an open problem in the general case. It is solved for \(n=2\) (where the optimal upper bound is 4) and for \(n=3\) (where the optimal upper bound is 6). Also, it is known that in the n-ary case the optimal bound is between 2n and the order of the growth \(n2^{\frac{n}{2}}\) . In this article we solve this problem for quaternary words, for which we show that the best possible upper bound on the MP-ratio equals 8. We believe that this is the last case in which the result is 2n, that is, we believe that for \(n\geqslant 5\) there are words whose MP-ratio is strictly larger than 2n.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

And Now There Are Four: Another Brick in the Wall of the Optimal Upper Bound on the MP-Ratio

  • 会议论文

  • 发表日期：

    2025年

查看全文
  • Kristina Ago,
  • Bojan Bašić

摘要

The so-called MP-ratio is a kind of measure of how “packed with palindromes” a given word is. The lower bound on the MP-ratio for the set of all n-ary words is (trivially) 1, while the best possible upper bound is an open problem in the general case. It is solved for \(n=2\) (where the optimal upper bound is 4) and for \(n=3\) (where the optimal upper bound is 6). Also, it is known that in the n-ary case the optimal bound is between 2n and the order of the growth \(n2^{\frac{n}{2}}\) . In this article we solve this problem for quaternary words, for which we show that the best possible upper bound on the MP-ratio equals 8. We believe that this is the last case in which the result is 2n, that is, we believe that for \(n\geqslant 5\) there are words whose MP-ratio is strictly larger than 2n.