Patterns in colored circular permutations

NEW

Problem: Reconstructed conjecture: for every colored circular pattern $\rho$ and every $n\ge |\rho|$, there is a length-$n$ circular $\rho$-optimal permutation of the same colored-block form as $\rho$. Here $f_c(\pi,\rho)$ counts circular occurrences, equivalently the sum of ordinary subsequence occurrences over cyclic shifts of $\rho$, and $g_c(n,\rho)=\max_{|\pi|=n} f_c(\pi,\rho)$. “Same form” means the same cyclic sequence of nonempty colored blocks, with the same block-order relations. This is the natural reading of Remark 4.5 following the paper’s results for patterns with few colored blocks.

Result: The conjecture is false.

Take the two-colored circular pattern

It has block form $R_1B_1R_2B_2$. We show that for $n=6$, the optimum is $5$, but every same-form permutation has at most $4$ occurrences.

For any length-$6$ colored circular permutation $\sigma$, every occurrence of any cyclic shift of $\rho$ uses four entries whose colors, when the entries are listed by increasing value, are

Thus $f_c(\sigma,\rho)$ is at most the number of $rbrb$-subsequences in the value-color word of $\sigma$.

A binary word of length $6$ has at most $5$ $rbrb$-subsequences. Indeed, if it has $2$ red letters, both reds must be used, giving at most $xy\le4$, where $x,y$ are the numbers of blues between and after them. The $4$-red case is dual. If it has $3$ reds and $3$ blues, let $a_0,a_1,a_2,a_3$ be the red counts in the gaps around the three blues. The number is

with equality at $(a_0,a_1,a_2)=(1,1,1)$.

The bound is attained by

whose five occurrences are on value sets

Hence $g_c(6,\rho)=5$.

Now suppose $\sigma$ has the same form as $\rho$. Its four nonempty circular blocks have sizes $a,b,c,d$, with $a+b+c+d=6$. Since every cyclic shift of $\rho$ alternates colors, an occurrence cannot choose two entries from the same colored block; hence it chooses one entry from each block. Therefore

Thus no same-form length-$6$ permutation is $\rho$-optimal, while an optimum has value $5$. This refutes the reconstructed conjecture.

Citation: Problem source and terminology: Daniel Gray, Charles Lanning, Hua Wang, “Patterns in colored circular permutations,” Involve 12 (2019), 157–169, Remark 4.5, DOI: 10.2140/involve.2019.12.157. The counterexample above is given here.