11
$\begingroup$

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.

$\endgroup$
0

3 Answers 3

11
$\begingroup$

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$".

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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