|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'504'585
Articles rated: 2609
25 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
A new proof of the density Hales-Jewett theorem | | D. H. J. Polymath
; | | Date: |
20 Oct 2009 | | Abstract: | The Hales-Jewett theorem asserts that for every r and every k there exists n
such that every r-colouring of the n-dimensional grid {1,...,k}^n contains a
combinatorial line. This result is a generalization of van der Waerden’s
theorem, and it is one of the fundamental results of Ramsey theory. The theorem
of van der Waerden has a famous density version, conjectured by Erdos and Turan
in 1936, proved by Szemeredi in 1975, and given a different proof by
Furstenberg in 1977. The Hales-Jewett theorem has a density version as well,
proved by Furstenberg and Katznelson in 1991 by means of a significant
extension of the ergodic techniques that had been pioneered by Furstenberg in
his proof of Szemeredi’s theorem. In this paper, we give the first elementary
proof of the theorem of Furstenberg and Katznelson, and the first to provide a
quantitative bound on how large n needs to be. In particular, we show that a
subset of {1,2,3}^n of density delta contains a combinatorial line if n is at
least a tower of 2’s of height O(1/delta^3). Our proof is reasonably simple:
indeed, it gives what is arguably the simplest known proof of Szemeredi’s
theorem. | | Source: | arXiv, 0910.3926 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER