a Ramsey-type question

Question

This question is related to this one but feels more Ramsey-type, so perhaps it is easier. Let $S$ be a finite set, $|S|=k$. Suppose we color all subsets of $S$ in $1000$ colors. What is the maximal (in terms of $k$) guaranteed length $l=l(k)$ of a monochromatic sequence of pairwise different subsets $A_1,A_2,..., A_l$ such that $|A_i\setminus A_{i+1}|+|A_{i+1}\setminus A_i|\le 2$ for every $i$? Clearly if $A$ is a subset of $S$ such that all 2-element subsets of $A$ are monochromatic, then $l(n)\ge |A|-1$ (there is a sequence of 2-element subsets of $A$ which satisfies the above property). So $l(k)$ is at least as big as the corresponding number from the Ramsey theory. Is it much bigger? The number 1000 is of course "any fixed number".

Update 1 Fedor and Tony showed below that $l(k)\ge k/1000$. Thus only the first question remains: What is $l(k)$? Is it exponential in $k$, for example?

Update 2 Although the question I asked makes sense (see Update 1), I realized that it is not the question I meant to ask. Here is the correct question. Same assumptions: $|S|=k$, 1000 colors. We consider monochromatic sequences of pairwise different subsets ${\mathcal A}=A_1,A_2,...,A_l$, where $|A_i\setminus A_{i+1}|+|A_{i+1}\setminus A_i|\le 2$. For each of these sequences we compute $\chi({\mathcal A})=|A_1\setminus A_l|+|A_l\setminus A_1|$. Now the question: what is the maximal guaranteed $\chi({\mathcal A})$ in terms of $k$, call it $\chi(k)$? By Ramsey, this number grows with $k$. Indeed if we color just $s$-element subsets, we will be able (if $k\gg s$) to find a subset of size $2s$ where all subsets of size $s$ are colored with the same color; then we can find a monochromatic sequence of subsets of size $s$ with the above property and $\chi=2s$ because the first and the last subsets in that sequence are disjoint. The question is what is the growth rate of $\chi(k)$. The question is motivated by Justin Moore's answer here.

Answer 1

Here is a proof of a very weak upper bound for $l(k)$. Consider the colouring of $2^S$ where each set is coloured by its size (mod 1000). A good monochomatic sequence must consist of sets of the same size. Thus we obtain $l(k) \leq \binom{k}{k/2}$.

However, we can be a bit smarter. Instead of colouring all $i$-subsets of $S$ with the same colour, we can use 333 colours and still guarantee that a good monochromatic sequence must use sets of the same size. Thus, we are lead to the problem of 333-colouring $\binom{S}{i}$ to minimize the length of a good monochromatic sequence inside $\binom{S}{i}$.

Answer 2

It is much bigger for sure, even if we restrict two subsets of cardinality 2 (call them edges). You need monochromatic path of length $\ell$. Take the color with at least $k(k-1)/2000$ edges of this color, consider only them. Consider the maximal path in our graph. It has length at most $l-1$. Hence it endpoint (both of them) has degree at most $l-1$. Remove it and repeat (or use induction). We get that our graph has at most $(l-1)k$ edges. So, $k(k-1)/2000\leq (l-1)k$, $l\geq (k-1)/2000+1$.