Take the 2-minute tour ×

I wonder what interesting and non-trivial examples of density Ramsey theorems with explicit asymptotics are there?

I'm aware of two examples: Szemerédi's theorem and density Hales-Jewett theorem.

Let me try to formalize what I mean by "density Ramsey theorems". I'm interested in statements of the following type: for every $k \in \mathbb{N}, \alpha > 0$ there exists $n_0 = n_0(k, \alpha)$ such that if we have a collection of $n \geq n_0$ objects, then whatever $\alpha n$ objects we take there are $k$ among them that form a "nice" structure. Collections and niceness are problem-specific of course: in case of Szemerédi's theorem they are $\lbrace 1, 2, \ldots, n\rbrace$ and arithmetic progressions, for Hales-Jewett — $[k]^d$ and combinatorial lines, respectively. I'm particularly interested in theorems where the dependence $n_0 = n_0(k, \alpha)$ can be made explicit.

share|improve this question
Since there no definitive answer, shouldn't this be community wiki? –  Benoît Kloeckner Nov 19 '11 at 12:40
@Benoit sure, I just forgot about it –  ilyaraz Nov 19 '11 at 14:09

3 Answers 3

Fix $\epsilon>0$. Every subset $A$ of $\{1,2,\dots,n\}$ with $|A|\geq \epsilon n$ contains a centrally symmetric subset $E$ (in other words, there is a $c$ with $E-c=c-E$) with $|E|> \alpha \epsilon^2 n$. The optimal value for $\alpha$ isn't known, but there are reasonably close upper and lower bounds. Greg Martin's paper, with some coauthor or other, isn't the state of the art, but it's the source that sticks in my mind.

Personally, I prefer the continuous statement: every subset of $[0,1]$ with measure $\epsilon$ contains a centrally symmetric subset with measure $0.6\epsilon^2$. And the the "$0.6$", while not best possible, cannot be replaced with "$0.9$".

share|improve this answer

Kostas Tyros spoke in the Toronto set theory seminar just yesterday about a density version of the Halpern Lauchli Theorem. Actually he spoke about a finite version of the density theorem, and the density version is due to P. Dodos et. al. from 2010 I believe.

share|improve this answer

A nice example is Sárközy's theorem on squares among differences.

share|improve this answer

Your Answer


