<p>First I have to say: this problem is <em>really</em> interesting!! And here I briefly describe why <a href="https://cstheory.stackexchange.com/posts/3803/revisions">my previous approaches</a> failed, as suggested in <a href="https://cstheory.meta.stackexchange.com/questions/386/policy-on-deleting-incorrect-answers">this meta post</a> about incorrect answers.</p>

<ul>
<li><p>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.</p></li>
<li><p>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}$.</p></li>
<li><p>The third one goes back to the first method, and it shows that for a uber-weak parameter set ($n &gt; k+d-1$ and $d \mid k$), the theorem is false. We used a famous lemma in additive combinatorics: the EGZ-theorem.</p></li>
</ul>

<hr>

<p>The fourth try is due to <a href="https://cstheory.stackexchange.com/questions/3795/extensions-of-ramseys-theorem-monochromatic-but-diverse/3962#3962">the answer</a> 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.</p>

<p>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 <em>switch</em> is defined if $x_i$ and $x_{i+1}$ are in different mod-d classes. We have k-1 switches for $S^*$.</p>

<p>Let a k-subset $S$ be <strong>red</strong> if $S$ has at most k-2 switches; otherwise it is <strong>blue</strong>. By the previous paragraph we already had a blue one, now we prove that for $n &gt; k+d+1$, there is an red $S$ in any n-set $X$. Since $n &gt; d$, there are two numbers $x_i,x_j$ in the same mod-d class and $j-i \leq d-1$; and since $n &gt; k+d+1$, there are at least k-2 elements $x_k$ in $X$ with $k&lt;i$ or $k&gt;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.</p>

CC BY-SA 2.5
2010-12-15T07:38:10.743Z
I posed a [question on MO](http://mathoverflow.net/questions/49494/is-generalized-erdsheilbronn-problem-true-for-finite-cyclic-groups) for the request of literatures in generalized EHC on cyclic groups.
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-12-15T13:28:27.027Z
Thanks, this was enlightening, but I'm not sure if it could be extended to show that the claim is false for a composite $d$. For example, if $d = 4$ and $k$ is odd, then a diverse $X$ might consist of elements that are alternately $1$ or $3$ mod $d$, and no $k$-subset is zero mod $d$?
Jukka Suomela
CC BY-SA 2.5
2010-12-15T13:44:28.260Z
Regarding the real problem: All this is related to proving statements of the form "there is no deterministic distributed algorithm that solves this graph problem in fewer than that many communication rounds". Ramsey theory has been applied successfully in many cases; see e.g. lecture 4 [here](http://www.cs.helsinki.fi/u/josuomel/dda-2010/). But occasionally I need something stronger than "mere" monochromatic subsets. It's a long story, and everything is embarrassingly vague at this point, but if this leads to something concrete, I'll certainly write a detailed explanation here!
Jukka Suomela
CC BY-SA 2.5
2010-12-15T18:19:32.983Z
@Jukka: Thank you for kindly sharing your ideas, I do hope you will come up with something really nice soon! As for the case when d is composite, I got a few ideas to handle them, but it is still a little messy, I'll think for a few more hours before writing them down, in case that the ideas do not fall apart...
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-12-22T14:25:25.190Z
@Jukka: I found a weird mistake in my proof. In Lemma 3, shouldn't $k$ be assumed to be smaller than $|X|$, thus smaller than $d$? Otherwise it is impossible to have all the $x_i$'s distinct. I will try to fix the mistake. But currently the proof is broken...
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-12-23T17:06:13.510Z
I do not think that the chance of non-diversity would tend to zero as N tends to infinity. I also do not understand what you are counting.
domotorp
CC BY-SA 2.5
2010-12-24T01:09:23.023Z
@domotorp: Thanks for the comment, I'll try to provide more explanations.
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-12-24T07:15:11.230Z
Maybe you could give another answer instead of always reediting this one. Just a suggestion.
domotorp
CC BY-SA 2.5
2010-12-24T07:41:33.057Z
@domotorp: But I want to keep all the comments in this answer, which are valuable :) And I'm not sure if multiple answers are suitable if my first answer is in fact wrong, which may not be qualify as an "answer". But thanks for the suggestion, maybe it is time for a discussion on meta?
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-12-24T07:50:21.227Z
Sure, its your choice. Seems you have posted your answer one minute before mine, now let the crowd decide!
domotorp
CC BY-SA 2.5
2010-12-24T08:00:43.470Z
@domotorp: In my opinion, yours wins dominatively. My vote is yours. Any idea on the surviving cases?
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-12-24T10:37:40.913Z
Yeah, this simple modification gives a better lower bound for the n's. Let me think about small n's.
domotorp
CC BY-SA 2.5
2010-12-15T04:24:26.237Z
2010-12-24T11:01:40.153Z
2017-04-13T12:32:28.080Z
Hsien-Chih Chang 張顯之
<p>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.</p>

CC BY-SA 2.5
2010-12-24T07:54:42.520Z
This is clever! And we only need $n > (k-1)d$ in fact. Your answer rules out almost all the cases... Now the only possibilities are $n \leq (k-1)d$, which are not too much.
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2010-12-24T07:35:21.250Z
2010-12-24T07:35:21.250Z
domotorp
<p>As a follow-up of my <a href="https://cstheory.stackexchange.com/questions/3764/ramseys-theorem-for-collections-of-sets">previous question</a>, 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.)</p>

<hr>

<p>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$.</p>

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

<p>Definitions:</p>

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

<p>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.</p>

<p>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$.</p>

<p>Question: is there always a <strong>diverse and monochromatic</strong> $n$-subset $X \subset B$?</p>

<hr>

<p><strong>Edit:</strong> 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.</p>

<reference-request><co.combinatorics><ramsey-theory>
Extensions of Ramsey's theorem: monochromatic but diverse
Jukka Suomela
# Extensions of Ramsey's theorem: monochromatic but diverse

(Asked by: username_0 on 2010-12-14)

As a follow-up of my [previous question](https://cstheory.stackexchange.com/questions/3764/ramseys-theorem-for-collections-of-sets), 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.

**Tags:** reference-request, co.combinatorics, ramsey-theory

---

## 2 answers

### Answer by username_1 on 2010-12-15. Score: 7 | Accepted answer

First I have to say: this problem is *really* interesting!! And here I briefly describe why [my previous approaches](https://cstheory.stackexchange.com/posts/3803/revisions) failed, as suggested in [this meta post](https://cstheory.meta.stackexchange.com/questions/386/policy-on-deleting-incorrect-answers) 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](https://cstheory.stackexchange.com/questions/3795/extensions-of-ramseys-theorem-monochromatic-but-diverse/3962#3962) 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 $kj$. 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.

> **Comments:**
> **username_1**: I posed a [question on MO](http://mathoverflow.net/questions/49494/is-generalized-erdsheilbronn-problem-true-for-finite-cyclic-groups) for the request of literatures in generalized EHC on cyclic groups.  
> **username_0**: Thanks, this was enlightening, but I'm not sure if it could be extended to show that the claim is false for a composite $d$. For example, if $d = 4$ and $k$ is odd, then a diverse $X$ might consist of elements that are alternately $1$ or $3$ mod $d$, and no $k$-subset is zero mod $d$?  
> **username_0**: Regarding the real problem: All this is related to proving statements of the form "there is no deterministic distributed algorithm that solves this graph problem in fewer than that many communication rounds". Ramsey theory has been applied successfully in many cases; see e.g. lecture 4 [here](http://www.cs.helsinki.fi/u/josuomel/dda-2010/). But occasionally I need something stronger than "mere" monochromatic subsets. It's a long story, and everything is embarrassingly vague at this point, but if this leads to something concrete, I'll certainly write a detailed explanation here!  
> **username_1**: @Jukka: Thank you for kindly sharing your ideas, I do hope you will come up with something really nice soon! As for the case when d is composite, I got a few ideas to handle them, but it is still a little messy, I'll think for a few more hours before writing them down, in case that the ideas do not fall apart...  
> **username_1**: @Jukka: I found a weird mistake in my proof. In Lemma 3, shouldn't $k$ be assumed to be smaller than $|X|$, thus smaller than $d$? Otherwise it is impossible to have all the $x_i$'s distinct. I will try to fix the mistake. But currently the proof is broken...  
> **username_2**: I do not think that the chance of non-diversity would tend to zero as N tends to infinity. I also do not understand what you are counting.  
> **username_1**: @domotorp: Thanks for the comment, I'll try to provide more explanations.  
> **username_2**: Maybe you could give another answer instead of always reediting this one. Just a suggestion.  
> **username_1**: @domotorp: But I want to keep all the comments in this answer, which are valuable :) And I'm not sure if multiple answers are suitable if my first answer is in fact wrong, which may not be qualify as an "answer". But thanks for the suggestion, maybe it is time for a discussion on meta?  
> **username_2**: Sure, its your choice. Seems you have posted your answer one minute before mine, now let the crowd decide!  
> **username_1**: @domotorp: In my opinion, yours wins dominatively. My vote is yours. Any idea on the surviving cases?  
> **username_2**: Yeah, this simple modification gives a better lower bound for the n's. Let me think about small n's.  

---

### Answer by username_2 on 2010-12-24. Score: 6

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.

> **Comments:**
> **username_1**: This is clever! And we only need $n > (k-1)d$ in fact. Your answer rules out almost all the cases... Now the only possibilities are $n \leq (k-1)d$, which are not too much.  

---

