Skip to main content
Post Made Community Wiki by Ben Webster
Source Link
Pablo Shmerkin
  • 4.7k
  • 2
  • 25
  • 33

Szemerédi's Theorem (possibly in its dynamical version established by Furstenberg) is used to derive many generalizations and variants of Szemerédi's Theorem itself. I'm not an expert so I give just two examples, but I know there are many more:

  • In "Markov processes and Ramsey Theory for trees" (available here), Furstenberg and Weiss prove the following variant of Szemerédi's Theorem for trees: given an integer $h>0$ and $\delta>0$ there is $H(h,\delta)$ such that any subtree of the full binary tree of height $>H(h,\delta)$ and density $>\delta$ contains a full arithmetic subtree of height $h$ (see the paper for the precise definitions).

  • The following version of Szemerédi's Theorem relativized to random sets was obtained independently by Conlon and Gowers and by Balogh, Morris and Samotij. Say that a set $E\subset\mathbb{Z}$ is $(k,\delta)$-szemerédi if every subset of $E$ of relative density $\ge \delta$ contains an arithmetic progression of length $k$. Then, given $\delta>0$ and $k\in\mathbb{N}$ there is $C>0$ such that if $p_n\ge C n^{-1/(k-1)}$, then the probability that a random subset of $\{1,\ldots,n\}$ with each element chosen independently with probability $p_n$ is $(k,\delta)$-szemerédi is $1-o_{n\to\infty}(1)$. (The exponent $1/(k-1)$ is easily seen to be sharp.)

The proofs of these results use Szemerédi's Theorem as a black box (rather than adapting its proof), together with substantial new ideas.