Szemerédi’s theorem holds almost surely inside sparse random sets

You need to know: A (nontrivial) k-term arithmetic progression, notation $|I|$ for the number of elements in finite set I, notation P for probability, independence.

Background: Let $[n]=\{1,2,\dots,n\}$ , and let $[n]_p$ be a random subset of $[n]$ in which each element of $[n]$ is chosen independently with probability $p\in[0,1]$ . A finite set I of integers is called $(\delta; k)$ -Szemerédi if every subset of I of cardinality at least $\delta|I|$ contains a nontrivial k-term arithmetic progression.

The Theorem: On 18th November 2010, Daniel Conlon and Timothy Gowers submitted to arxiv and the Annals of Mathematics a paper in which they proved, among other results, that for any $\delta>0$ and any integer $k\geq 3$ , there exists a constant $C=C(k,\delta)$ such that $\lim\limits_{n\to\infty} P([n]_p \text{ is } (\delta; k) \text{-Szemeredi})=1$ if $p \geq \min\{1, Cn^{-1/(k-1)}\}$ .

Short context: Famous Szemerédi’s theorem, proved in 1975, states, in our terminology, that set $[n]$ itself is $(\delta; k)$ -Szemerédi for all $n\geq N(\delta,k)$ . Later, Green and Tao, on the way of proving this theorem, proved the existence of function $p=p(n)$ with $\lim\limits_{n\to\infty} p(n)=0$ such that $\lim\limits_{n\to\infty} P([n]_p \text{ is } (\delta; k) \text{-Szemeredi})=1$ . The Theorem proves that the same conclusion holds for every function $p=p(n)$ such that $p \geq Cn^{-1/(k-1)}$ . This result is optimal up to constant factor because it is known that, for some constant $c=c(k,\delta)>0$ , $\lim\limits_{n\to\infty} P([n]_p \text{ is } (\delta; k) \text{-Szemeredi})=0$ whenever $p \leq cn^{-1/(k-1)}$ . Before 2010, the Theorem was known to hold only for $k=3$ . See here for further generalisation in a later work.