Extensions of Ramsey's theorem: monochromatic but diverse

Question

As a follow-up of my previous question, which was resolved by Hsien-Chih Chang, here is another attempt to find an appropriate generalisation of Ramsey's theorem. (You don't need to read the previous question; this post is self-contained.)

---

Parameters: integers $1 \ll d \ll k \ll n$ are given, and then $N$ is chosen to be sufficiently large. Terminology: an $m$-subset is a subset of size $m$.

Let $B = \{1,2,...,N\}$. For each $k$-subset $S \subset B$, assign a colour $f(S) \in \{0,1\}$.

Definitions:

• $X \subset B$ is monochromatic if $f(S) = f(S')$ for all $k$-subsets $S \subset X$ and $S' \subset X$.
• $X \subset B$ is diverse if $X = \{ x_1, x_2, ..., x_n \}$ such that $x_i < x_{i+1}$ and $x_i\,\not\equiv x_{i+1} \text{ mod } d$ for all $i$.

For example, if $d = 10$, then $\{ 12, 15, 23, 32, 39 \}$ is diverse but $\{ 12, 15, 25, 32, 39 \}$ is not. Note that a subset of a diverse set is not necessarily diverse.

Now Ramsey's theorem says that no matter how we choose $f$, there is a monochromatic $n$-subset $X \subset B$. And obviously it is trivial to find a diverse $n$-subset $X \subset B$.

Question: is there always a diverse and monochromatic $n$-subset $X \subset B$?

---

Edit: Hsien-Chih Chang shows that the claim is false for a prime $d$, but what about composite $d$? In my applications, I will have a lot of freedom in choosing the exact values of $d \ll k \ll n$, as long as I can make them arbitrarily large. They can be powers of primes, products of prime numbers, or whatever is necessary to make the claim true.

Answer 1

First I have to say: this problem is really interesting!! And here I briefly describe why my previous approaches failed, as suggested in this meta post about incorrect answers.

• My first attempt was trying to construct a coloring related to the sumset of the k-subset which makes all n-subset non-monochromatic. Lemma 1 is still available; but Lemma 2 was wrong, by observing that if k and d are related prime, then an n-subset $\{1,3,1,3, \ldots\}$ in module d suggested by @Jukka is a counter-example.

• The second try was a proof to the theorem; by counting the ratio of diverse and monochromatic $n$-subsets, we hope that the number of monochromatic ones will surpasses those of non-diverse ones. But the is an error in my calculations, observed by @domotorp: the ratio of being non-diverse will not approaches zero; it converges to about $n/d$, which is clearly larger than $R(n,n;k)^{-n}$.

• The third one goes back to the first method, and it shows that for a uber-weak parameter set ($n > k+d-1$ and $d \mid k$), the theorem is false. We used a famous lemma in additive combinatorics: the EGZ-theorem.

---

The fourth try is due to the answer by @domotorp; it is both clever and inspiring, and I'll try to modify his proof to deal with all the parameters. But still his method is elegant, and I totally appreciate this simple approach.

A diverse n-set contains at least one k-subset with at least $k-1$ "switches between mod classes"; precisely, let $X = x_1,\ldots,x_n$ be a diverse n-set, and let $S^* = x_1,\ldots,x_k$, a switch is defined if $x_i$ and $x_{i+1}$ are in different mod-d classes. We have k-1 switches for $S^*$.

Let a k-subset $S$ be red if $S$ has at most k-2 switches; otherwise it is blue. By the previous paragraph we already had a blue one, now we prove that for $n > k+d+1$, there is an red $S$ in any n-set $X$. Since $n > d$, there are two numbers $x_i,x_j$ in the same mod-d class and $j-i \leq d-1$; and since $n > k+d+1$, there are at least k-2 elements $x_k$ in $X$ with $k<i$ or $k>j$. And we can construct a k-subset $S$ with $x_i$ next to $x_j$, which only switches at most k-2 times. Thus $S$ is a red k-subset.

Answer 2

I might have misunderstood your question, but if not, I think it is false. Color the k-sets whose members are all congruent modulo d by red, the other k-sets by blue. If n>kd, then any n-set must contain a k-set whose members are all congruent modulo d and is thus red. On the other hand, if a k-set contains two consecutive elements of a diverse n-set, then it is blue.