http://michaelnielsen.org/polymath1/index.php?title=Abstract.tex&feed=atom&action=historyAbstract.tex - Revision history2019-09-15T19:14:22ZRevision history for this page on the wikiMediaWiki 1.23.5http://michaelnielsen.org/polymath1/index.php?title=Abstract.tex&diff=1889&oldid=prevRyanworldwide at 20:23, 8 July 20092009-07-08T20:23:46Z<p></p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr style='vertical-align: top;'>
<td colspan='2' style="background-color: white; color:black; text-align: center;">← Older revision</td>
<td colspan='2' style="background-color: white; color:black; text-align: center;">Revision as of 20:23, 8 July 2009</td>
</tr><tr><td colspan="2" class="diff-lineno">Line 1:</td>
<td colspan="2" class="diff-lineno">Line 1:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>\begin{abstract}</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>\begin{abstract}</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>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, \dotsc, 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 van der Waerden<del class="diffchange diffchange-inline">'s theorem </del>has a famous density version, conjectured by Erd\H os and Tur\'an in 1936, proved by Szemer\'edi 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 Szemer\'edi'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 $[3]^n$ of density $\delta$ contains a combinatorial line if $n \geq 2 \upuparrows O(1/\delta^3)$. Our proof is surprisingly\noteryan{``reasonably'', maybe} simple: indeed, it gives what is probably the simplest known proof of Szemer\'edi's theorem.  </div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>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, \dotsc, 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 <ins class="diffchange diffchange-inline">theorem of </ins>van der Waerden has a famous density version, conjectured by Erd\H os and Tur\'an in 1936, proved by Szemer\'edi 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 Szemer\'edi'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 $[3]^n$ of density $\delta$ contains a combinatorial line if $n \geq 2 \upuparrows O(1/\delta^3)$. Our proof is surprisingly\noteryan{``reasonably'', maybe} simple: indeed, it gives what is probably the simplest known proof of Szemer\'edi's theorem.  </div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>\end{abstract}</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>\end{abstract}</div></td></tr>
</table>Ryanworldwidehttp://michaelnielsen.org/polymath1/index.php?title=Abstract.tex&diff=1878&oldid=prevRyanworldwide: Undo revision 1762 by 67.186.58.92 (Talk)2009-07-08T20:06:42Z<p>Undo revision 1762 by <a href="/polymath1/index.php?title=Special:Contributions/67.186.58.92" title="Special:Contributions/67.186.58.92">67.186.58.92</a> (<a href="/polymath1/index.php?title=User_talk:67.186.58.92" title="User talk:67.186.58.92">Talk</a>)</p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr style='vertical-align: top;'>
<td colspan='2' style="background-color: white; color:black; text-align: center;">← Older revision</td>
<td colspan='2' style="background-color: white; color:black; text-align: center;">Revision as of 20:06, 8 July 2009</td>
</tr><tr><td colspan="2" class="diff-lineno">Line 1:</td>
<td colspan="2" class="diff-lineno">Line 1:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>\begin{abstract}</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>\begin{abstract}</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>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, \dotsc, 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 <del class="diffchange diffchange-inline">theorem of </del>van der Waerden has a famous density version, conjectured by Erd\H os and Tur\'an in 1936, proved by Szemer\'edi 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 Szemer\'edi'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 $[3]^n$ of density $\delta$ contains a combinatorial line if $n \geq 2 \upuparrows O(1/\delta^3)$. Our proof is surprisingly\noteryan{``reasonably'', maybe} simple: indeed, it gives what is probably the simplest known proof of Szemer\'edi's theorem.  </div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>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, \dotsc, 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 van der Waerden<ins class="diffchange diffchange-inline">'s theorem </ins>has a famous density version, conjectured by Erd\H os and Tur\'an in 1936, proved by Szemer\'edi 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 Szemer\'edi'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 $[3]^n$ of density $\delta$ contains a combinatorial line if $n \geq 2 \upuparrows O(1/\delta^3)$. Our proof is surprisingly\noteryan{``reasonably'', maybe} simple: indeed, it gives what is probably the simplest known proof of Szemer\'edi's theorem.  </div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>\end{abstract}</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>\end{abstract}</div></td></tr>
</table>Ryanworldwidehttp://michaelnielsen.org/polymath1/index.php?title=Abstract.tex&diff=1762&oldid=prev67.186.58.92 at 04:19, 25 June 20092009-06-25T04:19:51Z<p></p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr style='vertical-align: top;'>
<td colspan='2' style="background-color: white; color:black; text-align: center;">← Older revision</td>
<td colspan='2' style="background-color: white; color:black; text-align: center;">Revision as of 04:19, 25 June 2009</td>
</tr><tr><td colspan="2" class="diff-lineno">Line 1:</td>
<td colspan="2" class="diff-lineno">Line 1:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>\begin{abstract}</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>\begin{abstract}</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>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, \dotsc, 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 van der Waerden<del class="diffchange diffchange-inline">'s theorem </del>has a famous density version, conjectured by Erd\H os and Tur\'an in 1936, proved by Szemer\'edi 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 Szemer\'edi'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 $[3]^n$ of density $\delta$ contains a combinatorial line if $n \geq 2 \upuparrows O(1/\delta^3)$. Our proof is surprisingly\noteryan{``reasonably'', maybe} simple: indeed, it gives what is probably the simplest known proof of Szemer\'edi's theorem.  </div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>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, \dotsc, 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 <ins class="diffchange diffchange-inline">theorem of </ins>van der Waerden has a famous density version, conjectured by Erd\H os and Tur\'an in 1936, proved by Szemer\'edi 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 Szemer\'edi'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 $[3]^n$ of density $\delta$ contains a combinatorial line if $n \geq 2 \upuparrows O(1/\delta^3)$. Our proof is surprisingly\noteryan{``reasonably'', maybe} simple: indeed, it gives what is probably the simplest known proof of Szemer\'edi's theorem.  </div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>\end{abstract}</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>\end{abstract}</div></td></tr>
</table>67.186.58.92http://michaelnielsen.org/polymath1/index.php?title=Abstract.tex&diff=1648&oldid=prevRyanworldwide at 00:08, 12 June 20092009-06-12T00:08:50Z<p></p>
<table class='diff diff-contentalign-left'>
<col class='diff-marker' />
<col class='diff-content' />
<col class='diff-marker' />
<col class='diff-content' />
<tr style='vertical-align: top;'>
<td colspan='2' style="background-color: white; color:black; text-align: center;">← Older revision</td>
<td colspan='2' style="background-color: white; color:black; text-align: center;">Revision as of 00:08, 12 June 2009</td>
</tr><tr><td colspan="2" class="diff-lineno">Line 1:</td>
<td colspan="2" class="diff-lineno">Line 1:</td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>\begin{abstract}</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>\begin{abstract}</div></td></tr>
<tr><td class='diff-marker'>−</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #ffe49c; vertical-align: top; white-space: pre-wrap;"><div>The Hales-Jewett theorem asserts that for every $r$ and every $k$ there exists $n$ such that every colouring of the $n$-dimensional grid $<del class="diffchange diffchange-inline">[</del>k<del class="diffchange diffchange-inline">]</del>^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 van der Waerden's theorem has a famous density version, conjectured by Erd\H os and Tur\'an in 1936, proved by Szemer\'edi 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 Szemer\'edi's theorem. In this paper, we give the first <del class="diffchange diffchange-inline">purely combinatorial </del>proof of the theorem of Furstenberg and Katznelson. <del class="diffchange diffchange-inline">The </del>proof is surprisingly simple: indeed, it gives what is probably the simplest known proof of Szemer\'edi's theorem.  </div></td><td class='diff-marker'>+</td><td style="color:black; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #a3d3ff; vertical-align: top; white-space: pre-wrap;"><div>The Hales<ins class="diffchange diffchange-inline">-</ins>-Jewett theorem asserts that for every $r$ and every $k$ there exists $n$ such that every <ins class="diffchange diffchange-inline">$r$-</ins>colouring of the $n$-dimensional grid $<ins class="diffchange diffchange-inline">\{1, \dotsc, </ins>k<ins class="diffchange diffchange-inline">\}</ins>^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 van der Waerden's theorem has a famous density version, conjectured by Erd\H os and Tur\'an in 1936, proved by Szemer\'edi in 1975 and given a different proof by Furstenberg in 1977. The Hales<ins class="diffchange diffchange-inline">-</ins>-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 Szemer\'edi's theorem. In this paper, we give the first <ins class="diffchange diffchange-inline">elementary </ins>proof of the theorem of Furstenberg and Katznelson<ins class="diffchange diffchange-inline">, and the first to provide a quantitative bound on how large $n$ needs to be</ins>. <ins class="diffchange diffchange-inline">In particular, we show that a subset of $[3]^n$ of density $\delta$ contains a combinatorial line if $n \geq 2 \upuparrows O(1/\delta^3)$. Our </ins>proof is surprisingly<ins class="diffchange diffchange-inline">\noteryan{``reasonably'', maybe} </ins>simple: indeed, it gives what is probably the simplest known proof of Szemer\'edi's theorem.  </div></td></tr>
<tr><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>\end{abstract}</div></td><td class='diff-marker'> </td><td style="background-color: #f9f9f9; color: #333333; font-size: 88%; border-style: solid; border-width: 1px 1px 1px 4px; border-radius: 0.33em; border-color: #e6e6e6; vertical-align: top; white-space: pre-wrap;"><div>\end{abstract}</div></td></tr>
</table>Ryanworldwidehttp://michaelnielsen.org/polymath1/index.php?title=Abstract.tex&diff=1378&oldid=prevRyanworldwide: New page: \begin{abstract} The Hales-Jewett theorem asserts that for every $r$ and every $k$ there exists $n$ such that every colouring of the $n$-dimensional grid $[k]^n$ contains a combinatorial l...2009-05-14T04:08:27Z<p>New page: \begin{abstract} The Hales-Jewett theorem asserts that for every $r$ and every $k$ there exists $n$ such that every colouring of the $n$-dimensional grid $[k]^n$ contains a combinatorial l...</p>
<p><b>New page</b></p><div>\begin{abstract}<br />
The Hales-Jewett theorem asserts that for every $r$ and every $k$ there exists $n$ such that every colouring of the $n$-dimensional grid $[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 van der Waerden's theorem has a famous density version, conjectured by Erd\H os and Tur\'an in 1936, proved by Szemer\'edi 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 Szemer\'edi's theorem. In this paper, we give the first purely combinatorial proof of the theorem of Furstenberg and Katznelson. The proof is surprisingly simple: indeed, it gives what is probably the simplest known proof of Szemer\'edi's theorem. <br />
\end{abstract}</div>Ryanworldwide