2
$\begingroup$

Say you take the integers $(1,\cdots,N)$ and color them with $c$ different colors, where $c < N$ and there is no constraint to use all colors. For a given $m < N$, is it possible to determine a lower bound on the longest coloring appearing in $(1, \cdots, m)$ that re-appears at least once more in $(1,\cdots, N)$?

E.g. if we have c = R,G,B and N = 10, and m = 4, then the sequence RRRGGGBBBR repeats "R", while RGRGRGBBBB repeats "RGRG". So a definite lower bound in this case would be 1 (due to a trivial application of the pigeonhole principle). I was thinking maybe this is covered by Ramsey theory, but could not find results that would cover this question.

Thanks

Edit: As Peter has pointed out, the lower bound for $m < c$ is $0$. So I'll add the additional constraint that $m > c$. Thank you for the answers so far.

$\endgroup$
5
  • 1
    $\begingroup$ Well, an obvious lower bound is something like $\log_cN$. $\endgroup$ Oct 10, 2017 at 11:28
  • $\begingroup$ Thanks; I don't quite follow though. Wouldn't that imply that a length 9 string using 3 colors must have a length 3 repetition? However, it seems that, for instance, RGBGRBBRG only has length 2 repetitions. EDIT: sorry I haven't consumed sufficient coffee. I somehow thought log3(9) is 3.... Could I ask how you derived this formula? Thanks $\endgroup$
    – Niklas
    Oct 10, 2017 at 11:36
  • 2
    $\begingroup$ See, we have only $c^k$ different substrings of length $k$, hence if $c^k<N-k+1$, there are got to be repetitions. $\endgroup$ Oct 10, 2017 at 11:40
  • 2
    $\begingroup$ @IvanNeretin, depends on $m$. If $m < c$ then a lower bound of $0$ is tight (by example: $A_1 A_2 \ldots A_m A_{m+1} A_{m+1} \ldots A_{m+1}$). $\endgroup$ Oct 10, 2017 at 19:39
  • $\begingroup$ @IvanNeretin I think your lower bound should be corrected to something like $\log_c m$, because we look for a matching coloring sequence appearing in $(1,\dots,m)$, so its length is already at most $m$. If $c>1$ then we can prevent reappearance of all long coloring sequences appearing in $(1,\dots,m)$. For instance, if we use only the first $c-1$ colors to color $(1,\dots,m)$ and the remaining color to color $(m+1,\dots,N)$. Thus the role of $N$ is secondary for the asked bound. Moreover, it turned out that the bound does not depend on $N$, see my answer. $\endgroup$ Dec 16, 2017 at 10:14

1 Answer 1

1
$\begingroup$

We claim that the required minimax length of the reappearing colored sequence equals the largest $l$ such that $c^l<m-l+2$. Indeed, if $c^l<m-l+2$ then by the pigeonholes principle among the first $m-l+2$ sequences of length $l$ we find two matching. The first of them appears in $(1,\dots,m)$. On the other hand, if $c^l\ge m-l+2$ then we can first color the discrete segment $(1,\dots, m+1)$ according to a de Brujin sequence of order $l$ on a size-$c$ alphabet ending with $1^l$ and then continue to color $11\dots$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .