Return to 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.

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.

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 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?

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.

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(n)$ 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(n)$ 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".

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 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?