MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This is a stronger version to Szemerédi's theorem.

Let $C : \mathbb{N}\rightarrow 2^{\mathbb{N}}$ be a choice function such that $C(n)$ is a subset of $\{1,...,n\}$ with size at least $\frac{n}{M}$ for some nonzero constant $M$ that only depends on $C$. Can we guarantee an arithmetic progression in $C(n)$ of length at least $\frac{n}{M'}$ where $M'$ only depends on $M$?

If not, what is a counter example? and how big arithmetic progression (order in terms of $n$) we can guarantee in $C(n)$.

share|cite|improve this question
up vote 4 down vote accepted

This is far too ambitious. Recall that the van der Waerden number W(k,c) is the smallest $N$ such that if we color $[N]$ with $c$ colors we are guaranteed to have a $k$ term arithmetic progression. Gasarch and Haeupler have given a lower bound of $W(k,c) \gg \frac{c^{k-1}}{ek}$. Thus we can color $[N]$ with $M$ colors such that there is no monochromatic arithmetic progression of length $ \gg_{M} \log(N)$. Clearly one of these colors will have size $\geq N/M$, which gives a counterexample to your question.

share|cite|improve this answer

Your Answer


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.