Sparse analog of Szemerédi’s theorem is true

Combinatorics 1 Minutes

You need to know: A (nontrivial) k-term arithmetic progression, notation [n] for \{1,2,\dots,n\}.

Background: For integer m>0 and real number x\geq m, denote {{x}\choose{m}}=\frac{1}{m!}\prod\limits_{i=0}^{m-1}(x-i). By convention, we define {{x}\choose{m}}=0 if x<m. Also, by m-subset of [n] we mean a subset which has m elements.

The Theorem: On 29th April 2012, József Balogh, Robert Morris, and Wojciech Samotij submitted to arxiv a paper in which they proved, among other results, that for every real \beta>0 and every integer k\geq 3, there exist constants C and n_0>0 such that for every integers n \geq n_0 and m\geq Cn^{1-1/(k-1)}, there are at most {{\beta n}\choose{m}} m-subsets of [n] that contain no k-term arithmetic progression.

Short context: Famous Szemerédi’s theorem, proved in 1975, states that, for every \beta>0, every subset of [n] of size m\geq \beta n must contain a k-term arithmetic progression, provided that n is sufficiently large. The authors view the Theorem as a sparse analog of this statement. It easily implies the original Szemerédi’s theorem, as well as its sparse random analog described here. In turn, the Theorem itself is just one out of many corollaries of the general powerful theorem in graph theory proved by the authors, see the original paper for details.

Links: Free arxiv version of the original paper is here, journal version is here.

Go to the list of all theorems

Published by Bogdan Grechuk

Published

One thought on “Sparse analog of Szemerédi’s theorem is true”

  1. Pingback: Szemerédi’s theorem holds almost surely inside sparse random sets – Theorems of the 21st century

Leave a comment