Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.

share|improve this question

2 Answers 2

up vote 7 down vote accepted

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.

share|improve this answer
1  
I posed a question on MO for the request of literatures in generalized EHC on cyclic groups. –  Hsien-Chih Chang 張顯之 Dec 15 '10 at 7:38
    
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 Dec 15 '10 at 13:28
    
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. 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 Dec 15 '10 at 13:44
    
@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 張顯之 Dec 15 '10 at 18:19
    
@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 張顯之 Dec 22 '10 at 14:25

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.

share|improve this answer
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. –  Hsien-Chih Chang 張顯之 Dec 24 '10 at 7:54

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.