Szemerédi's theorem

In number theory Szemerédi's theorem refers to the proof of the Erdős–Turán conjecture. In 1936 Erdős and Turan conjecturedcitation|authorlink1=Paul Erdős|first1=Paul|last1=Erdős|authorlink2=Paul Turán|first2=Paul|last2=Turán|title=On some sequences of integers|journal=Journal of the London Mathematical Society|volume=11|year=1936|pages=261–264.] for every value "d" called density 0 < "d" <1 and every integer "k" there is a number "N"("d","k") such that every subset A of {1,...,"N"} of cardinality "dN" contains a length-k arithmetic progression, provided "N" > "N"("d","k").

This generalizes the statement of van der Waerden's theorem.

Let "k" be a positive integer and let 0 < δ ≤ 1/2. A finitary version of the theorem states that there exists a positive integer

:"N" = "N"("k", δ)

such that every subset of {1, 2, ..., "N"} of size at least δ"N" contains an arithmetic progression of length "k".The best-known bounds for "N"("k", δ) are

: $C^{log(1/delta)^{k-1 leq N(k,delta) leq 2^{2^{delta^{-2^{2^{k+9}$

: $N(3,delta) leq C^{delta^{-2}log(1/delta)},$

ee also

*Problems involving arithmetic progressions
*Ergodic Ramsey theory
*Arithmetic combinatorics

References

External links

* [http://planetmath.org/encyclopedia/SzemeredisTheorem.html PlanetMath source for initial version of this page]
* [http://www.math.ucla.edu/~tao/whatsnew.html Announcement by Ben Green and Terence Tao] - the preprint is available at [http://front.math.ucdavis.edu/math.NT/0404188 math.NT/0404188]
* [http://in-theory.blogspot.com/2006/06/szemeredis-theorem.html Discussion of Szemerédi's theorem (part 1 of 5)]
*Ben Green and Terence Tao: [http://www.scholarpedia.org/article/Szemeredi%27s_Theorem Szemerédi's theorem] on Scholarpedia.

Wikimedia Foundation. 2010.

Игры ⚽ Поможем написать реферат

Look at other dictionaries:

Szemerédi–Trotter theorem — In mathematics, the Szemerédi–Trotter theorem is a result in the field of combinatorial geometry. It asserts that given n points and m lines in the plane,the number of incidences (i.e. the number of point line pairs, such that the point lies on… … Wikipedia
Szemerédi regularity lemma — In mathematics, Szemerédi s regularity lemma states that every large enough (finite undirected simple) graph can be approximated by a composition of a structured and a pseudo random part.Formal statement of the regularity lemmaThe formal… … Wikipedia
Endre Szemerédi — (born August 21 1940) is a Hungarian mathematician, working in the field of combinatorics, currently professor of computer science at Rutgers University. He was born in Budapest. His advisers in mathematics were Paul Erdős and András Hajnal.He is … Wikipedia
Van der Waerden's theorem — is a theorem of the branch of mathematics called Ramsey theory. The theorem is about the basic structure of the integers. It is named for Dutch mathematician B. L. van der Waerden. [B.L. van der Waerden, Beweis einer Baudetschen Vermutung , Nieuw … Wikipedia
Beck's theorem (geometry) — In incidence geometry, Beck s theorem is a more quantitative form of the more classical Sylvester–Gallai theorem. It says that finite collections of points in the plane fall into one of two extremes; one where a large fraction of points lie on a… … Wikipedia
Green–Tao theorem — In mathematics, the Green–Tao theorem, proved by Ben Green and Terence Tao in 2004, [Ben Green and Terence Tao, [http://arxiv.org/abs/math.NT/0404188 The primes contain arbitrarily long arithmetic progressions] ,8 Apr 2004.] states that the… … Wikipedia
Hales–Jewett theorem — In mathematics, the Hales–Jewett theorem is a fundamental combinatorial result of Ramsey theory, concerning the degree to which high dimensional objects must necessarily exhibit some combinatorial structure; it is impossible for such objects to… … Wikipedia
Roth's theorem — There are two major results of Klaus Roth in mathematics which go by the name Roth s theorem :* The Thue Siegel Roth theorem in Diophantine approximation, which concerns the rarity to which an irrational algebraic number can be approximated by a… … Wikipedia
Erdős–Stone theorem — In extremal graph theory, the Erdős–Stone theorem is an asymptotic result generalising Turán s theorem to bound the number of edges in an H free graph for a non complete graph H . It is named after Paul Erdős and Arthur Stone, who proved it in… … Wikipedia
Corners theorem — In mathematics, the corners theorem is an important result, proved by Miklós Ajtai and Endre Szemerédi, of a statement in arithmetic combinatorics. It states that for every ε > 0 there exists N such that given at least εN2 points in… … Wikipedia

Academic Dictionaries and Encyclopedias

Szemerédi's theorem

Look at other dictionaries:

Share the article and excerpts

Academic Dictionaries and Encyclopedias

Wikipedia

Szemerédi's theorem

Look at other dictionaries:

Share the article and excerpts

Direct link