Polymath.tex: Difference between revisions
No edit summary |
No edit summary |
||
| Line 52: | Line 52: | ||
\author{D.H.J. Polymath} | \author{D.H.J. Polymath} | ||
\address{http://michaelnielsen.org/polymath1/index.php} | \address{http://michaelnielsen.org/polymath1/index.php} | ||
\email{ | %\email{} | ||
\subjclass{ | \subjclass{05D05, 05D10} | ||
\begin{abstract} | \begin{abstract} | ||
For any $n \geq 0$ and $k \geq 1$, the density Hales-Jewett number $c_{n,k}$ is defined as the size of the largest subset of the cube $[k]^n$ := $\{1,\ldots,k\}^n$ which contains no combinatorial line; similarly, the Moser number $c'_{n,k}$ is the largest subset of the cube $[k]^n$ which contains no geometric line. A deep theorem of Furstenberg and Katznelson \cite{fk1}, \cite{fk2}, \cite{mcc} shows that $c_{n,k}$ = $o(k^n)$ as $n \to \infty$ (which implies a similar claim for $c'_{n,k}$; this is already non-trivial for $k = 3$. Several new proofs of this result have also been recently established \cite{poly}, \cite{austin}. | For any $n \geq 0$ and $k \geq 1$, the \emph{density Hales-Jewett number} $c_{n,k}$ is defined as the size of the largest subset of the cube $[k]^n$ := $\{1,\ldots,k\}^n$ which contains no combinatorial line; similarly, the Moser number $c'_{n,k}$ is the largest subset of the cube $[k]^n$ which contains no geometric line. A deep theorem of Furstenberg and Katznelson \cite{fk1}, \cite{fk2}, \cite{mcc} shows that $c_{n,k}$ = $o(k^n)$ as $n \to \infty$ (which implies a similar claim for $c'_{n,k}$); this is already non-trivial for $k = 3$. Several new proofs of this result have also been recently established \cite{poly}, \cite{austin}. | ||
Using both human and computer-assisted arguments, we compute several values of $c_{n,k}$ and $c'_{n,k}$ for small $n,k$. For instance the sequence $c_{n,3}$ for $n=0,\ldots,6$ is $1,2,6,18,52,150,450$, while the sequence $c'_{n,3}$ for $n=0,\ldots,6$ is $1,2,6,16,43,124,353$. We also establish some results for higher $k$, showing for instance that an analogue of the LYM inequality (which relates to the $k = 2$ case) does not hold for higher $k$. | Using both human and computer-assisted arguments, we compute several values of $c_{n,k}$ and $c'_{n,k}$ for small $n,k$. For instance the sequence $c_{n,3}$ for $n=0,\ldots,6$ is $1,2,6,18,52,150,450$, while the sequence $c'_{n,3}$ for $n=0,\ldots,6$ is $1,2,6,16,43,124,353$. We also establish some results for higher $k$, showing for instance that an analogue of the LYM inequality (which relates to the $k = 2$ case) does not hold for higher $k$. | ||
| Line 65: | Line 65: | ||
%\today | %\today | ||
\setcounter{tocdepth}{1} | %\setcounter{tocdepth}{1} | ||
\tableofcontents | %\tableofcontents | ||
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | ||
| Line 75: | Line 74: | ||
\include{moser-lower} | \include{moser-lower} | ||
\include{moser} | \include{moser} | ||
\include{fujimura} | %\include{fujimura} | ||
\include{higherk} | %\include{higherk} | ||
\include{coloring} | % \include{coloring} | ||
\appendix | %\appendix | ||
\include{genetic} | %\include{genetic} | ||
\include{integer} | %\include{integer} | ||
\begin{thebibliography}{10} | \begin{thebibliography}{10} | ||
\bibitem{ajtai} Ajtai | \bibitem{ajtai} M. Ajtai, E. Szemer\'edi, \emph{Sets of lattice points that form no squares}, Studia Scientiarum Mathematicarum Hungarica, 9, 9-11 (1974), (1975) | ||
\bibitem{austin} T. Austin, \emph{Deducing the density Hales-Jewett theorem from an infinitary removal lemma}, preprint. | \bibitem{austin} T. Austin, \emph{Deducing the density Hales-Jewett theorem from an infinitary removal lemma}, preprint. | ||
| Line 94: | Line 93: | ||
\bibitem{behrend} | \bibitem{behrend} | ||
F. Behrend, \emph{On the sets of integers which contain no three in arithmetic progression}, Proceedings of the National Academy of Sciences \textbf{23} (1946), 331–-332. | F. Behrend, \emph{On the sets of integers which contain no three in arithmetic progression}, Proceedings of the National Academy of Sciences \textbf{23} (1946), 331–-332. | ||
\bibitem{Brower} | |||
A. Brower, {\tt www.win.tue.nl/$\sim$aeb/codes/binary-1.html}. | |||
\bibitem{chandra} | \bibitem{chandra} | ||
| Line 104: | Line 106: | ||
\bibitem{elkin} | \bibitem{elkin} | ||
M. Elkin, \emph{An Improved Construction of Progression-Free Sets}, preprint. | M. Elkin, \emph{An Improved Construction of Progression-Free Sets}, preprint. | ||
\bibitem{fuji} | |||
K. Fujimura, {\tt www.puzzles.com/PuzzlePlayground/CoinsAndTriangles/CoinsAndTriangles.htm} | |||
\bibitem{fk1} H. Furstenberg, Y. Katznelson, \emph{A density version of the Hales-Jewett theorem for $k = 3$}, Graph Theory and Combinatorics (Cambridge, 1988). Discrete Math. 75 (1989), no. 1-3, 227–-241. | \bibitem{fk1} H. Furstenberg, Y. Katznelson, \emph{A density version of the Hales-Jewett theorem for $k = 3$}, Graph Theory and Combinatorics (Cambridge, 1988). Discrete Math. 75 (1989), no. 1-3, 227–-241. | ||
| Line 119: | Line 124: | ||
\bibitem{Krisha} K. Krishna, M. Narasimha Murty, "Genetic K-means algorithm," Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on , vol.29, no.3, pp.433-439, Jun 1999 | \bibitem{Krisha} K. Krishna, M. Narasimha Murty, "Genetic K-means algorithm," Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on , vol.29, no.3, pp.433-439, Jun 1999 | ||
\bibitem{markstrom} {{\tt http://abel.math.umu.se/~klasm/Data/HJ/}} | \bibitem{markstrom} K. Markstrom, {{\tt http://abel.math.umu.se/~klasm/Data/HJ/}} | ||
\bibitem{moser} L. Moser, Problem P.170 in Canad. Math. Bull. 13 (1970), 268. | \bibitem{moser} L. Moser, Problem P.170 in Canad. Math. Bull. 13 (1970), 268. | ||
\bibitem{mcc} R. McCutcheon, \emph{The conclusion of the proof of the density Hales-Jewett theorem for k=3}, unpublished. | \bibitem{mcc} R. McCutcheon, \emph{The conclusion of the proof of the density Hales-Jewett theorem for $k=3$}, unpublished. | ||
\bibitem{obryant} | \bibitem{obryant} | ||
| Line 129: | Line 134: | ||
\bibitem{oeis} | \bibitem{oeis} | ||
N. J. A. Sloane, Ed. (2008), The On-Line Encyclopedia of Integer Sequences, {\tt www.research.att.com/ | N. J. A. Sloane, Ed. (2008), The On-Line Encyclopedia of Integer Sequences, {\tt www.research.att.com/$\sim$njas/sequences/} | ||
\bibitem{potenchin} | \bibitem{potenchin} | ||
A. Potechin, \emph{Maximal caps in $AG(6, 3)$}, Journal Designs, Codes and Cryptography, Volume 46, Number 3 / March, 2008. | A. Potechin, \emph{Maximal caps in $AG(6, 3)$}, Journal Designs, Codes and Cryptography, Volume 46, Number 3 / March, 2008. | ||
\bibitem{poly} D.H.J. Polymath, | \bibitem{poly} D.H.J. Polymath, \emph{A new proof of the density Hales-Jewett theorem}, preprint, available at {\tt http://arxiv.org/abs/0910.3926}. | ||
\bibitem{polywiki} D.H.J. Polymath, {\tt michaelnielsen.org/polymath1/index.php?title=Polymath1} | |||
\bibitem{rankin} | \bibitem{rankin} | ||
| Line 151: | Line 158: | ||
\bibitem{szem} | \bibitem{szem} | ||
E. Szemer\'edi, \emph{On sets of integers containing no $k$ elements in arithmetic progression}, Acta Arithmetica \textbf{27} (1975), 199-–245. | E. Szemer\'edi, \emph{On sets of integers containing no $k$ elements in arithmetic progression}, Acta Arithmetica \textbf{27} (1975), 199-–245. | ||
\end{thebibliography} | \end{thebibliography} | ||
Revision as of 22:39, 15 January 2010
\documentclass[12pt,a4paper,reqno]{amsart} \usepackage{amssymb} \usepackage{amscd} %\usepackage{psfig} \usepackage{graphicx} %\usepackage{showkeys} % uncomment this when editing cross-references \numberwithin{equation}{section}
\addtolength{\textwidth}{3 truecm} \addtolength{\textheight}{1 truecm} \setlength{\voffset}{-.6 truecm} \setlength{\hoffset}{-1.3 truecm}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section] %\newtheorem{theorem}[theorem]{Theorem} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{principle}[theorem]{Principle} \newtheorem{claim}[theorem]{Claim}
\theoremstyle{definition}
%\newtheorem{roughdef}[subsection]{Rough Definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{remark}[theorem]{Remark} \newtheorem{remarks}[theorem]{Remarks} \newtheorem{example}[theorem]{Example} \newtheorem{examples}[theorem]{Examples} %\newtheorem{problem}[subsection]{Problem} %\newtheorem{question}[subsection]{Question}
\newcommand\E{\mathbb{E}} \newcommand\R{\mathbb{R}} \newcommand\Z{\mathbb{Z}} \newcommand\N{\mathbb{N}} \renewcommand\P{\mathbb{P}}
\parindent 0mm \parskip 5mm
\begin{document}
\title{Density Hales-Jewett and Moser numbers}
\author{D.H.J. Polymath} \address{http://michaelnielsen.org/polymath1/index.php} %\email{}
\subjclass{05D05, 05D10}
\begin{abstract} For any $n \geq 0$ and $k \geq 1$, the \emph{density Hales-Jewett number} $c_{n,k}$ is defined as the size of the largest subset of the cube $[k]^n$ := $\{1,\ldots,k\}^n$ which contains no combinatorial line; similarly, the Moser number $c'_{n,k}$ is the largest subset of the cube $[k]^n$ which contains no geometric line. A deep theorem of Furstenberg and Katznelson \cite{fk1}, \cite{fk2}, \cite{mcc} shows that $c_{n,k}$ = $o(k^n)$ as $n \to \infty$ (which implies a similar claim for $c'_{n,k}$); this is already non-trivial for $k = 3$. Several new proofs of this result have also been recently established \cite{poly}, \cite{austin}.
Using both human and computer-assisted arguments, we compute several values of $c_{n,k}$ and $c'_{n,k}$ for small $n,k$. For instance the sequence $c_{n,3}$ for $n=0,\ldots,6$ is $1,2,6,18,52,150,450$, while the sequence $c'_{n,3}$ for $n=0,\ldots,6$ is $1,2,6,16,43,124,353$. We also establish some results for higher $k$, showing for instance that an analogue of the LYM inequality (which relates to the $k = 2$ case) does not hold for higher $k$. \end{abstract}
\maketitle %\today
%\setcounter{tocdepth}{1} %\tableofcontents
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \include{introduction} \include{dhj-lown-lower} \include{dhj-lown} \include{moser-lower} \include{moser} %\include{fujimura} %\include{higherk} % \include{coloring}
%\appendix
%\include{genetic} %\include{integer}
\begin{thebibliography}{10}
\bibitem{ajtai} M. Ajtai, E. Szemer\'edi, \emph{Sets of lattice points that form no squares}, Studia Scientiarum Mathematicarum Hungarica, 9, 9-11 (1974), (1975)
\bibitem{austin} T. Austin, \emph{Deducing the density Hales-Jewett theorem from an infinitary removal lemma}, preprint.
\bibitem{beck} J. Beck, Combinatorial Games: Tic-Tac-Toe Theory. Cambridge University Press, 2008.
\bibitem{behrend} F. Behrend, \emph{On the sets of integers which contain no three in arithmetic progression}, Proceedings of the National Academy of Sciences \textbf{23} (1946), 331–-332.
\bibitem{Brower} A. Brower, {\tt www.win.tue.nl/$\sim$aeb/codes/binary-1.html}.
\bibitem{chandra} A. Chandra, \emph{On the solution of Moser's problem in four dimensions}, Canad. Math. Bull. \textbf{16} (1973), 507--511.
\bibitem{chvatal1} V. Chv\'{a}tal, \emph{Remarks on a problem of Moser}, Canadian Math Bulletin, Vol 15, 1972, 19--21.
\bibitem{chvatal2} V. Chv\'{a}tal, \emph{Edmonds polytopes and a hierarchy of combinatorial problems}, Discrete Math. 4 (1973) 305-337.
\bibitem{elkin} M. Elkin, \emph{An Improved Construction of Progression-Free Sets}, preprint.
\bibitem{fuji} K. Fujimura, {\tt www.puzzles.com/PuzzlePlayground/CoinsAndTriangles/CoinsAndTriangles.htm}
\bibitem{fk1} H. Furstenberg, Y. Katznelson, \emph{A density version of the Hales-Jewett theorem for $k = 3$}, Graph Theory and Combinatorics (Cambridge, 1988). Discrete Math. 75 (1989), no. 1-3, 227–-241.
\bibitem{fk2} H. Furstenberg, Y. Katznelson, \emph{A density version of the Hales-Jewett theorem}, J. Anal. Math. 57 (1991), 64–-119. MR1191743
\bibitem{greenwolf} B. Green, J. Wolf, \emph{A note on Elkin's improvement of Behrend's construction}, preprint.
\bibitem{heule} Marijn Heule, presentation at {\tt http://www.st.ewi.tudelft.nl/sat/slides/waerden.pdf}
\bibitem{komlos} J. Koml\'{o}s, solution to problem P.170 by Leo Moser, Canad. Math.. Bull. vol {\bf (??check)} (1972), 312--313, 1970.
\bibitem{Krisha} K. Krishna, M. Narasimha Murty, "Genetic K-means algorithm," Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on , vol.29, no.3, pp.433-439, Jun 1999
\bibitem{markstrom} K. Markstrom, Template:\tt http://abel.math.umu.se/~klasm/Data/HJ/
\bibitem{moser} L. Moser, Problem P.170 in Canad. Math. Bull. 13 (1970), 268.
\bibitem{mcc} R. McCutcheon, \emph{The conclusion of the proof of the density Hales-Jewett theorem for $k=3$}, unpublished.
\bibitem{obryant} K. O'Bryant, \emph{Sets of integers that do not contain long arithmetic progressions}, preprint.
\bibitem{oeis} N. J. A. Sloane, Ed. (2008), The On-Line Encyclopedia of Integer Sequences, {\tt www.research.att.com/$\sim$njas/sequences/}
\bibitem{potenchin} A. Potechin, \emph{Maximal caps in $AG(6, 3)$}, Journal Designs, Codes and Cryptography, Volume 46, Number 3 / March, 2008.
\bibitem{poly} D.H.J. Polymath, \emph{A new proof of the density Hales-Jewett theorem}, preprint, available at {\tt http://arxiv.org/abs/0910.3926}.
\bibitem{polywiki} D.H.J. Polymath, {\tt michaelnielsen.org/polymath1/index.php?title=Polymath1}
\bibitem{rankin} R. A. Rankin, Sets of integers containing not more than a given number of terms in arithmetical progression, Proc. Roy. Soc. Edinburgh Sect. A 65 (1960/1961), 332–344 (1960/61). MR 0142526 (26 \#95)
\bibitem{roth} K. Roth, \emph{On certain sets of integers, I}, Journal of the London Mathematical Society \textbf{28} (1953), 104-–109.
\bibitem{Rothlauf} F. Rothlauf, D. E. Goldberg, Representations for Genetic and Evolutionary Algorithms. Physica-Verlag, 2002.
\bibitem{shelah} S. Shelah, \emph{Primitive recursive bounds for van der Warden numbers}, Journal of the American Mathematical Society \textbf{28} 1988, 683-–697.
\bibitem{sperner} E. Sperner, \emph{Ein Satz \"uber Untermengen einer endlichen Menge}, Mathematische Zeitschrift \textbf{27} (1928), 544-–548.
\bibitem{szem} E. Szemer\'edi, \emph{On sets of integers containing no $k$ elements in arithmetic progression}, Acta Arithmetica \textbf{27} (1975), 199-–245.
\end{thebibliography}
\end{document}
