Improved bounds on maximum sets of letters in sequences with forbidden alternations

2013/12/31 by Jesse Geneson, Geneson, Jesse
Computer Science · Engineering · #05D99 #Coding theory and cryptography #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #graph theory and CDMA systems #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1401.0063

openalex publication_date 2013/12/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let A_s,k(m) be the maximum number of distinct letters in any sequence which can be partitioned into m contiguous blocks of pairwise distinct letters, has at least k occurrences of every letter, and has no subsequence forming an alternation of length s. Nivasch (2010) proved that A_{5, 2d+1}(m) = θ( m α_d(m)) for all fixed d ≥ 2. We show that A_{s+1, s}(m) = \binomm- \lceil (s)/(2) \rceil\lfloor (s)/(2) \rfloor for all s ≥ 2, A_{5, 6}(m) = θ(m log log m), and A_{5, 2d+2}(m) = θ(m α_d(m)) for all fixed d ≥ 3.

Related

• Sequences of formation width 4 and alternation length 5
• Maximal 2-dimensional binary words of bounded degree
• Palindromic Subsequences in Finite Words
• Frequencies of letters in infinite k-balanced sequences
• Improved Upper Bounds on all Maximal α-gapped Repeats and Palindromes