|
|
| (21 intermediate revisions by 6 users not shown) |
| Line 3: |
Line 3: |
| \usepackage{amscd} | | \usepackage{amscd} |
| %\usepackage{psfig} | | %\usepackage{psfig} |
| | \usepackage{graphicx} |
| %\usepackage{showkeys} | | %\usepackage{showkeys} |
| % uncomment this when editing cross-references | | % uncomment this when editing cross-references |
| Line 35: |
Line 36: |
|
| |
|
| \newcommand\E{\mathbb{E}} | | \newcommand\E{\mathbb{E}} |
| | \newcommand\R{\mathbb{R}} |
| | \newcommand\Z{\mathbb{Z}} |
| | \newcommand\N{\mathbb{N}} |
| \renewcommand\P{\mathbb{P}} | | \renewcommand\P{\mathbb{P}} |
|
| |
|
| Line 44: |
Line 48: |
|
| |
|
|
| |
|
| \title{Density Hales-Jewett and Moser numbers in low dimensions} | | \title{Density Hales-Jewett and Moser numbers} |
|
| |
|
| \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,5$ is $1,2,6,16,43,124$. 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 prove 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$, and also establishing the asymptotic lower bound $c_{n,k} \geq k^n \exp\left( - O(\sqrt[\ell]{\log n})\right)$ where $\ell$ is the largest integer such that $2k > 2^\ell$. |
| \end{abstract} | | \end{abstract} |
|
| |
|
| Line 61: |
Line 65: |
| %\today | | %\today |
|
| |
|
| \setcounter{tocdepth}{1} | | %\setcounter{tocdepth}{1} |
| \tableofcontents | | %\tableofcontents |
| | |
|
| |
|
| %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% | | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% |
| \section{Introduction} | | \input{introduction} |
| | \input{dhj-lown-lower} |
| | \input{dhj-lown} |
| | \input{moser-lower} |
| | \input{moser} |
| | %\input{fujimura} |
| | %\input{higherk} |
| | % \input{coloring} |
|
| |
|
| ...
| | %\appendix |
|
| |
|
| | %\input{genetic} |
| | %\input{integer} |
|
| |
|
| In Sections \ref{moser-lower-sec}, \ref{moser-upper-sec} we will show
| | \begin{thebibliography}{10} |
|
| |
|
| \begin{theorem}[Values of $c'_{n,3}$ for small $n$]\label{moser} We have $c'_{0,3} = 1$, $c'_{1,3} = 2$, $c'_{2,3} = 6$, $c'_{3,3} = 16$, $c'_{4,3} = 43$, $c'_{5,3} = 124$, and $353 \leq c'_{6,3} \leq 361$. | | \bibitem{ajtai} M. Ajtai, E. Szemer\'edi, \emph{Sets of lattice points that form no squares}, Studia Scientiarum Mathematicarum Hungarica, \textbf{9} (1974-1975), 9--11. |
| \end{theorem}
| |
|
| |
|
| \begin{remark} The values of $c'_{n,3}$ for $n=0,1,2$ are easily verified. The quantity $c'_{3,3}$ was first computed in \cite{chvatal2}, while the quantity $c'_{4,3}$ was computed in \cite{chandra}; we will give alternate proofs of these results here. The bounds for $c'_{5,3}$ and $c'_{6,3}$ are new. | | \bibitem{austin} T. Austin, \emph{Deducing the density Hales-Jewett theorem from an infinitary removal lemma}, preprint, available at {\tt arxiv.org/abs/0903.1633}. |
| \end{remark}
| |
|
| |
|
| \section{Lower bounds for the Moser problem}\label{moser-lower-sec} | | \bibitem{beck} J. Beck, Combinatorial Games: Tic-Tac-Toe Theory. Cambridge University Press, 2008, Cambridge. |
|
| |
|
| ... | | \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. |
|
| |
|
| (Here we prove the lower bounds in Theorem \ref{moser}.)
| | \bibitem{Brower} |
| | A. Brower, {\tt www.win.tue.nl/$\sim$aeb/codes/binary-1.html}. |
|
| |
|
| \section{Upper bounds for the $k=3$ Moser problem in small dimensions}\label{moser-upper-sec} | | \bibitem{chandra} |
| | A. Chandra, \emph{On the solution of Moser's problem in four dimensions}, Canad. Math. Bull. \textbf{16} (1973), 507--511. |
|
| |
|
| \include{moser} | | \bibitem{chvatal1} V. Chv\'{a}tal, \emph{Remarks on a problem of Moser}, Canad. Math. Bull., \textbf{15} (1972) 19--21. |
|
| |
|
| \section{Upper and lower bounds for $c_n$ for small values of $n$} | | \bibitem{chvatal2} V. Chv\'{a}tal, \emph{Edmonds polytopes and a hierarchy of combinatorial problems}, Discrete Math. \textbf{4} (1973) 305--337. |
| $c_n$ is the size of the largest subset of $[3]{}^n$ that does not contain a combinatorial line. The first few values are 1, 2, 6, 18, 52, 150 and 450. This sequence is in the Online Encyclopaedia of Integer Sequences as sequence A156762. In this section we record the proofs justifying these bounds.
| |
|
| |
|
| \subsection{Basic constructions} | | \bibitem{elkin} |
| For all $n\geq 1$, a basic example of a mostly line-free set is \begin{equation}\label{Dn}
| | M. Elkin, \emph{An Improved Construction of Progression-Free Sets}, preprint. |
| D_n := \{(x_1,\ldots,x_n) \in [3]{}^n : \Sum_{i=1}^n x_i \neq 0 mod 3 \}
| |
| \end{equation}
| |
| This has cardinality $|D_n| = 2\cross 3^{n-1}$ . The only lines in $D_n$ are those with \begin{itemize}
| |
| \item A number of wildcards equal to a multiple of three;
| |
| \item The number of 1s unequal to the number of 2s modulo 3.
| |
| \end{itemize}
| |
| One way to construct line-free sets is to start with $D_n$ and remove some additional points. We also have the variants $D_{n,0} = D_n, D_{n,1}, D_{n,2}$ defined as \begin{equation}\label{Dnj}
| |
| D_{n,j} := \{(x_1,\ldots,x_n) \in [3]{}^n : \Sum_{i=1}^n x_i \neq j mod 3\}
| |
| \end{equation}
| |
| When $n$ is not a multiple of 3, then $D_{n,0}$, $D_{n,1}$ and $D_{n,2}$ are all cyclic permutations of each other; but when $n$ is a multiple of 3, then $D_{n,0}$ plays a special role (though $D_{n,1}$ and $D_{n,2}$ are still interchangeable).
| |
| Another useful construction proceeds by using the slices $\Gamma_{a,b,c} \subset [3]{}^n$ for $(a,b,c)$ in the triangular grid \begin{equation}\label{DeltaN}
| |
| \Delta_n := \{(a,b,c) \in \mathbb{Z}_+^3 : a+b+c = n\},
| |
| \end{equation}
| |
| where $\Gamma_{a,b,c}$ is defined as the strings in $[3]{}^n$ with $a$ 1s, $b$ 2s, and $c$ 3s. Note that \begin{equation}\label{GammaDef}
| |
| |\Gamma_{a,b,c}| = \frac{n!}{a!b!c!}.
| |
| \end{equation}
| |
|
| |
|
| Given any set $B\subset\Delta_n$ that avoids equilateral triangles $(a + r,b,c),(a,b + r,c),(a,b,c + r) $, the set \begin{equation}\label{GammaB}
| | \bibitem{fuji} |
| \Gamma_B := \Cup_{(a,b,c)\in B} \Gamma_{a,b,c}
| | K. Fujimura, {\tt www.puzzles.com/PuzzlePlayground/CoinsAndTriangles/CoinsAndTriangles.htm} |
| \end{equation}
| |
| is line-free and has cardinality \begin{equation}\label{GammaBSize}
| |
| |\Gamma_B| = \Sum_{(a,b,c)\in B} \frac{n!}{a!b!c!},
| |
| \end{equation}
| |
| and thus provides a lower bound for $c_n$: \begin{equation}\label{c_nbound}
| |
| c_n \geq \Sum_{(a,b,c)\in B} \frac{n!}{a!b!c!}.
| |
| \end{equation}
| |
| All lower bounds on $c_n$ have proceeded so far by choosing a good set of B and applying \eqref{c_nbound}. Note that $D_n$ is the same as $\Gamma_{B_n}$, where $B_n$ consists of those triples $(a,b,c) \in \Delta_n$ in which $a \neq b$ mod 3.
| |
| Note that if one takes a line-free set and permutes the alphabet {1,2,3} in any fashion (e.g. replacing all 1s by 2s and vice versa), one also gets a line-free set. This potentially gives six examples from any given starting example of a line-free set, though in practice there is enough symmetry that the total number of examples produced this way is less than six. (These six examples also correspond to the six symmetries of the triangular grid $\Delta_n$ formed by rotation and reflection.)
| |
| Another symmetry comes from permuting the $n$ indices in the strings of $[3]{}^n$ (e.g. replacing every string by its reversal). But the sets $\Gamma_B$ are automatically invariant under such permutations and thus do not produce new line-free sets via this symmetry.
| |
| $[3]{}^{n+1}$ can be expressed as the union of three copies of $[3]{}^n$, so we have the basic upper bound \begin{equation}\label{3cn}
| |
| c_{n+1} \leq 3c_n.
| |
| \end{equation}
| |
| Note that equality only occurs if one can find an $n+1$-dimensional line-free set such that every $n$-dimensional slice has the maximum possible cardinality of $c_n$.
| |
| \subsection{Small values of $c_n$}
| |
| It is clear that $c_0 = 1$ and $c_1 = 2$.
| |
| The three sets $D_1 = \{1,2\}$, $D_{1,1} = \{2,3\}$, and $D_{1,2} = \{1,3\}$ are the only two-element sets which are line-free in $[3]{}^1$, and there are no three-element sets.
| |
| There are four six-element sets in $[3]{}^2$ which are line-free, which we denote \begin{align}
| |
| $x = D_{2,2}$ &=& {12, 13, 21, 22, 31, 33} \\
| |
| $y = D_{2,1}$ &=& {11, 12, 21, 23, 32, 33}, \\
| |
| $z = D_2$ & = & {11, 13, 22, 23, 31, 32} \\
| |
| and $w$ & = & {12, 13, 21, 23, 31, 32}
| |
| \end{align}
| |
|
| |
|
| Combining this with the basic upper bound \eqref{3cn} we see that $c_2 = 6$.
| | \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. \textbf{75} (1989), 227–-241. |
| \subsection{$c_3 = 18$}
| |
| We describe a subset $A$ of $[3]{}^3$ as a string $abc$, where $a,b,c \subset [3]{}^2$ correspond to strings of the form 1 * * , 2 * * , 3 * * in $[3]{}^3$ respectively. Thus for instance $D_3 = xyz$, and so from \eqref{3cn} we have $c_3 = 18$.
| |
| \begin{lemma}\label{Lemma1} The only 18-element line-free subset of [3]3 is D3 = xyz. The only 17-element line-free subsets of [3]3 are formed by removing a point from D3 = xyz, or by removing either 111, 222, or 333 from $D_{3,2}$ = yzx or $D_{3,3}$ = zxy.\end{lemma}
| |
| \begin{proof} We prove the second claim. As 17 = 6 + 6 + 5, and $c_2 = 6$, at least two of the slices of a 17-element line-free set must be from $x$, $y$, $z$, $w$, with the third slice having 5 points. If two of the slices are identical, the last slice can have only 3 points, a contradiction. If one of the slices is a $w$, then the 5-point slice will contain a diagonal, contradiction. By symmetry we may now assume that two of the slices are $x$ and $y$, which force the last slice to be $z$ with one point removed. Now one sees that the slices must be in the order $xyz$, $yzx$, or $zxy$, because any other combination has too many lines that need to be removed. The sets $yzx$, $zxy$ contain the diagonal {111,222,333} and so one additional point needs to be removed.
| |
| The first claim follows by a similar argument to the second. \end{proof}
| |
| \subsection{$c_4 = 52$}
| |
| Indeed, divide a line-free set in $[3]{}^4$ into three blocks 1 * * * ,2 * * * ,3 * * * of $[3]{}^3$. If two of them are of size 18, then they must both be $xyz$, and the third block can have at most 6 elements, leading to an inferior bound of 42. So the best one can do is 18 + 17 + 17 = 52 which can be attained by deleting the diagonal {1111,2222,3333} from $D_{4,1} = xyz yzx xzy$, $D_4 = yzx zxy xyz$, or $D_{4,2} = zxy xyz yzx$. In fact,
| |
| \begin{lemma}\label{Lemma2}
| |
| \begin{itemize}\item The only 52-element line-free sets in [3]4 are formed by removing the diagonal {1111,2222,3333} from $D_{4,j}$ for some j=0,1,2.
| |
| \item The only 51-element line-free sets in [3]4 are formed by removing the diagonal and one further point from $D_{4,j}$ for some j=0,1,2.
| |
| \item The only 50-element line-free sets in [3]4 are formed by removing the diagonal and two further points from $D_{4,j}$ for some j=0,1,2 OR is equal to one of the three permutations of the set $X := \Gamma_{3,1,0} \cup \Gamma_{3,0,1} \cup \Gamma{2,2,0} \cup \Gamma_{2,0,2} \cup \Gamma_{1,1,2} \cup \Gamma_{1,2,1} \cup \Gamma_{0,2,2}$.\end{itemize} \end{lemma}
| |
| \begin{proof} It suffices to prove the third claim. In fact it suffices to show that every 50-point line-free set is either contained in the 54-point set $D_{4,j}$ for some $j=0,1,2$, or is some permutation of the set $X$. Indeed, if a 50-point line-free set is contained in, say, $D_4$, then it cannot contain 2222, since otherwise it must omit one point from each of the four pairs formed from {2333, 2111} by permuting the indices, and must also omit one of {1111, 1222, 1333}, leading to at most 49 points in all; similarly, it cannot contain 1111, and so omits the entire diagonal {1111,2222,3333}, with two more points to be omitted. Similarly when $D_4$ is replaced by one of the other $D_{4,j}$.
| |
| Next, observe that every three-dimensional slice of a line-free set can have at most $c_3 = 18$ points; thus when one partitions a 50-point line-free set into three such slices, it must divide either as 18+16+16, 18+17+15, 17+17+16, or some permutation of these.
| |
| Suppose that we can slice the set into two slices of 17 points and one slice of 16 points. By the various symmetries, we may assume that the 1*** slice and 2*** slices have 17 points, and the 3*** slice has 16 points. By Lemma \ref{Lemma1}, the 1-slice is $\{1\}\cross D_{3,j}$ with one point removed, and the 2-slice is $\{2\}\cross D_{3,k}$ with one point removed, for some $j,k \in \{0,1,2\}$.
| |
| If $j=k$, then the 1-slice and 2-slice have at least 15 points in common, so the 3-slice can have at most 27 − 15 = 12 points, a contradiction. If $jk$ = 01, 12, or 20, then observe that from Lemma \ref{Lemma1} the *1**, *2**, *3** slices cannot equal a 17-point or 18-point line-free set, so each have at most 16 points, leading to only 48 points in all, a contradiction. Thus we must have $jk$ = 10, 21, or 02.
| |
| Let's first suppose that $jk$=02. Then by Lemma \ref{Lemma1}, the 2*** slice contains the nine points formed from {2211, 2322, 2331} and permuting the last three indices, while the 1*** slice contains at least eight of the nine points formed from {1211, 1322, 1311} and permuting the last three indices. Thus the 3*** slice can contain at most one of the nine points formed from {3211, 3322, 3311} and permuting the last three indices. If it does contain one of these points, say 3211, then it must omit one point from each of the four pairs {3222, 3233}, {3212, 3213}, {3221, 3231}, {3111, 3311}, leading to at most 15 points on this slice, a contradiction. So the 3*** slice must omit all nine points, and is therefore contained in $\{3\}\cross D_{4,1}$, and so the 50-point set is contained in $D_{4,1}$, and we are done by the discussion at the beginning of the proof.
| |
| The case $jk$=10 is similar to the $jk$=02 case (indeed one can get from one case to the other by swapping the 1 and 2 indices). Now suppose instead that $jk=12$. Then by Lemma \ref{Lemma1}, the 1*** slice contains the six points from permuting the last three indices of 1123, and similarly the 2*** slice contains the six points from permuting the last three indices of 2123. Thus the 3*** slice must avoid all six points formed by permuting the last three indices of 3123. Similarly, as 1133 lies in the 1*** slice and 2233 lies in the 2*** slice, 3333 must be avoided in the 3*** slice.
| |
| Now we claim that 3111 must be avoided also; for if 3111 was in the set, then one point from each of the six pairs formed from {3311, 3211}, {3331, 3221} and permuting the last three indices must lie outside the 3*** slice, which reduces the size of that slice to at most 27 − 6 − 1 − 6 = 14, which is too small. Similarly, 3222 must be avoided, which puts the 3*** slice inside $\{3\}\cross D_3$ and then places the 50-point set inside $D_4$, and we are done by the discussion at the beginning of the proof.
| |
| We have handled the case in which at least one of the slicings of the 50-point set is of the form 50=17+17+16. The only remaining case is when all slicings of the 50-point set are of the form 18+16+16 or 18+17+15 (or a permutation thereof). By the symmetries of the situation, we may assume that the 1*** slice has 18 points, and thus by Lemma \ref{Lemma1} takes the form $\{1\}\cross D_3$. Inspecting the *1**, *2**, *3** slices, we then see (from Lemma \ref{Lemma1}) that only the *1** slice can have 18 points; since we are assuming that this slicing is some permutation of 50=18+17+16, we conclude that the *1** slice must have exactly 18 points, and is thus described precisely by Lemma \ref{Lemma1}. Similarly for the **1* and ***1 slices. Indeed, by Lemma \ref{Lemma1}, we see that the 50-point set must agree exactly with $D_{4,1}$ on any of these slices. In particular, on the remaining portion $\{2,3$\}^4$ of the cube, there are exactly 6 points of the 50-point set in $\{2,3\}^4$.
| |
| Suppose that 3333 was in the set; then since all permutations of 3311, 3331 are known to lie in the set, then 3322, 3332 must lie outside the set. Also, as 1222 lies in the set, at least one of 2222, 3222 lie outside the set. This leaves only 5 points in $\{2,3\}^4$, a contradiction. Thus 3333 lies outside the set; similarly 2222 lies outside the set.
| |
| Let a be the number of points in the 50-point set which are some permutation of 2233, thus $0\leq a\leq 6$. If $a=0$ then the set lies in $D_{4,1}$ and we are done. If $a=6$ then the set is exactly $X$ and we are done. Now suppose $a=1,2,3$. By symmetry we may assume that 2233 lies in the set. Then (since 2133, 1233 2231, 2213 are known to lie in the set) 2333, 3233, 2223, 2232 lie outside the set, which leaves at most 5 points inside $\{2,3\}^4$, a contradiction.
| |
| The remaining case is when $a=4,5$. Then one of the three pairs {2233, 3322}, {2323, 3232}, {2332, 3223} lie in the set. By symmetry we may assume that {2233, 3322} lie in the set. Then by arguing as before we see that all eight points formed by permuting 2333 or 3222 lie outside the set, leading to at most 5 points inside $\{2,3\}^4$, a contradiction. \end{proof}
| |
| \subsection{$c_5 = 150$, $c_6 = 450$}
| |
| \begin{lemma}. Any line-free subset of $D_{5,j}$ can have at most 150 points.\end{lemma}
| |
| \begin{proof} By rotation we may work with $D_5$. This set has 162 points. By looking at the triplets {10000, 11110, 12220} and cyclic permutations we must lose 5 points; similarly from the triplets {20000,22220, 21110} and cyclic permutations. Finally from {11000,11111,11222} and {22000,22222,22111} we lose two more points. \end{proof}
| |
| Equality can be attained by removing $\Gamma_{0,4,1}, \Gamma_{0,5,0},\Gamma_{4,0,1},\Gamma_{5,0.0} from $D_5$. Thus $c_5 \geq 150$.
| |
| Another pattern of 150 points is this: Take the 450 points in $[3]{}^6$ which are $\Gamma_{1,2,3}$, $\Gamma_{0,2,4}$ and permutations, then select the 150 whose final coordinate is 1.
| |
| \begin{lemma} \label{NoTwo51} A line-free subset of [3]5 with over 150 points cannot have two parallel [3]4 slices, each of which contain at least 51 points.\end{lemma}
| |
| \begin{proof}. Suppose not. By symmetry, we may assume that the 1**** and 2**** slices have at least 51 points, and that the whole set has at least 151 points, which force the third slice to have at least $151 – 2c_4 = 47$ points.
| |
| By Lemma \ref{Lemma2}, the 1**** slice takes the form $\{1\}\cross D_{4,j}$ for some $j = 0,1,2$ with the diagonal {11111,12222,13333} and possibly one more point removed, and similarly the 2**** slice takes the form $\{2\}\cross D_{4,k}$ for some $k = 0,1,2$ with the diagonal {21111,22222,23333} and possibly one more point removed.
| |
| Suppose first that $j=k$. Then the 1-slice and 2-slice have at least 50 points in common, leaving at most 31 points for the 3-slice, a contradiction. Next, suppose that $jk=01$. Then observe that the *i*** slice cannot look like any of the configurations in Lemma \ref{Lemma2} and so must have at most 50 points for $i=1,2,3$, leading to 150 points in all, a contradiction. Similarly if $jk$=12 or 20. Thus we must have $jk$ equal to 10, 21, or 02.
| |
| Let's suppose first that $jk=10$. The first slice then is equal to $\{1\}\cross D_{4,1}$ with the diagonal and possibly one more point removed, while the second slice is equal to $\{2\}\cross D_{4,0}$ with the diagonal and possibly one more point removed. Superimposing these slices, we thus see that the third slice is contained in $\{3\}\cross D_{4,2}$ except possibly for two additional points, together with the one point 32222 of the diagonal that lies outside of $\{3\}\cross D_{4,2}$.
| |
| The lines x12xx, x13xx (plus permutations of the last four digits) must each contain one point outside the set. The first two slices can only absorb two of these, and so at least 14 of the 16 points formed by permuting the last four digits of 31233, 31333 must lie outside the set. These points all lie in $\{3\}\cross D_{4,2}$, and so the 3**** slice can have at most $| D_{4,2}| − 14 + 3 = 43$ points, a contradiction.
| |
| The case $jk=02$ is similar to the case $jk=10$ (indeed one can obtain one from the other by swapping 1 and 2). Now we turn to the case $jk=21$. Arguing as before we see that the third slice is contained in $\{3\}\cross D_4$ except possibly for two points, together with 33333.
| |
| If 33333 was in the set, then each of the lines xx333, xxx33 (and permutations of the last four digits) must have a point missing from the first two slices, which cannot be absorbed by the two points we are permitted to remove; thus 33333 is not in the set. For similar reasons, 33331 is not in the set, as can be seen by looking at xxx31 and permutations of the last four digits. Indeed, any string containing four threes does not lie in the set; this means that at least 8 points are missing from $\{3\}\cross D_{4}$, leaving only at most 46 points inside that set. Furthermore, any point in the 3**** slice outside of $\{3\}\cross D_{4}$ can only be created by removing a point from the first two slices, so the total cardinality is at most 46 + 52 + 52 = 150, a contradiction.\end{proof}
| |
| \begin{Corollary} $c_5 \leq 152$ \end{corollary}
| |
| \begin{proof} By Lemma \ref{NoTwo51} and the bound $c_4 = 52$, any line-free set with over 150 points can have one slice of cardinality 52, but then the other two slices can have at most 50 points. \end{proof}
| |
| \begin{lemma}\label{151-49} Any solution with 151 or more points has a slice with at most 49 points. \end{lemma}
| |
| \begin{proof} Suppose we have 151 points without a line, and each of three slices has at least 50 points.
| |
| Using earlier notation, we split subsets of $[3]{}^4$ into nine subsets of $[3]{}^2$. So we think of x,y,z,a,b and c as subsets of a square. Each slice is one of the following:
| |
| \begin{itemize}\item $D_4$ = y'zx,zx'y,xyz (with one or two points removed) | |
| \item $D_{4,2}$ = z'xy,xyz,yzx' (with one or two points removed)
| |
| \item $D_{4,1}$ = xyz,yz'x,zxy' (with one or two points removed)
| |
| \item X = xyz,ybw,zwc
| |
| \item Y = axw,xyz,wzc
| |
| \item Z = awx,wby,xyz
| |
| \end{itemize}
| |
| where a, b and c have four points each. $a = \{2,3\}^2$, $b = \{1,3\}^2$ and $c = \{1,2\}^2$.
| |
| x', y' and z' are subsets of x, y and z respectively, and have five points each.
| |
| Suppose all three slices are subsets of $D_{4,j}$. We can remove at most five points from the full set of three D_{4,j}. Consider columns 2,3,4,6,7,8. At most two of these columns contain xyz, so one point must be removed from the other four. This uses up all but one of the removals. So the slices must be $D_{4,2}$, $D_{4,1}$, $D_{4,0}$ or a cyclic permutation of that. Then the cube, which contains the first square of slice 1; the fifth square of slice 2; and the ninth square of slice 3, contains three copies of the same square. It takes more than one point removed to remove all lines from that cube. So we can't have all three slices subsets of $D_{4,j}$.
| |
| Suppose one slice is X,Y or Z, and two others are subsets of $D_{4,j}$. We can remove at most three points from the full $D_{4,j}$ By symmetry, suppose one slice is X. Consider columns 2,3,4 and 7. They must be cyclic permutations of x, y, z, and two of them are not xyz, so must lose a point. Columns 6 and 8 must both lose a point, and we only have 150 points left. So if one slice is X, Y or Z, the full set contains a line.
| |
| Suppose two slices are from X, Y and Z, and the other is a subset of $D_{4,j}$. By symmetry, suppose two slices are X and Y. Columns 3,6,7 and 8 all contain w, and therefore at most 16 points each. Columns 1, 5 and 9 contain a, b, or c, and therefore at most 16 points. So the total number of points is at most 7*16+2*18 = 148. This contradicts the assumption of 151 points. \end{proof}
| |
| \begin{corollary} \label{525049} $c_5 \leq 151$ \end{corollary}
| |
| \begin{proof} By Lemmas \ref{NoTwo51} and \ref{151-49}, the maximum number of points is 52+50+49=151. \end{proof}
| |
| \begin{lemma} \label{151NoX} No solution with 151 points contains as a slice the X defined in Lemma \ref{Lemma2} \end{lemma}
| |
| \begin{proof} Suppose one row is $X$. Another row is $D_{4,j}$.
| |
| Suppose $X$ is in the first row. Label the other rows with letters from the alphabet.
| |
| \begin{align*} xyz & ybw & zwc \\ mno & pqr & stu \\def & ghi & jkl \end{align*}
| |
| Reslice the array into a left nine, middle nine and right nine. One of these squares contains 52 points, and it can only be the left nine. One of its three columns contains 18 points, and it can only be its left-hand column, $xmd$. So $m=y$ and $d=z$. But none of the $D_{4,j}$ begins with $y$ or $z$, which is a contradiction. So $X$ is not in the first row.
| |
| So $X$ is in the second or third row. By symmetry, suppose it is in the second row
| |
| \begin{align*}def & ghi & jkl \\xyz & ybw & zwc \\ mno & pqr & stu \end{align*}
| |
| Again, the left-hand nine must contain 52 points, so it is $D_{4,2}$. So either the first row is $D_{4,2}$ or the third row is $D_{4,0}$. If the first row is $D_{4,2}$ then the only way to have 50 points in the middle or right-hand nine is if the middle nine is $X$
| |
| \begin{align*}z'xy & xyz & yzx' \\xyz & ybw & zwc \\ yzx' & zwc & stu \end{align*}
| |
| In the seventh column, $s$ contains 5 points and in the eighth column, $t$ contains 4 points. The final row can now contain at most 48 points, and the whole array contains only 52+50+48 = 150 points.
| |
| If the third row is $D_{4,0}$, then neither the middle nine nor the right-hand nine contains 50 points, by the classification of Lemma \ref{Lemma2} and the formulas at the start of Lemma \ref{151-49}. Again, only 52+49+49 = 150 points are possible.
| |
| A similar argument is possible if $X$ is in the third row; or if $X$ is replaced by $Y$ or $Z$.
| |
| So when a 151-point set is sliced into three, one slice is $D_{4,j}$ and another slice is 50 points contained in $D_{4,k}$. \end{proof}
| |
| \begin{lemma} There is no 151-point solution \end{lemma}
| |
| \begin{proof} Assume by symmetry that the first row contains 52 points and the second row contains 50.
| |
| If $D_{4,1}$ is in the first row, then the second row must be contained in $D_{4,0}$.
| |
| \begin{align*} xyz & yz'x & zxy' \\ y'zx & zx'y & xyz \\ def & ghi & jkl
| |
| \end{align*}
| |
| But then none of the left nine, middle nine or right nine can contain 52 points, which contradicts Corollary \ref{525049}.
| |
| Suppose the first row is $D_{4,0}$. Then the second row is contained in $D_{4,2}$, otherwise the cubes formed from the nine columns of the diagram would need to remove too many points.
| |
| \begin{align*} y'zx & zx'y & xyz \\ z'xy & xyz & yzx' \\ def & ghi & jkl \end{align*}
| |
| But then neither the left nine, middle nine nor right nine contain 52 points.
| |
| So the first row contains $D_{4,2}$, and the second row is contained in $D_{4,1}$. Two points may be removed from the second row of this diagram.
| |
| \begin{align*} z'xy & xyz & yzx' \\ xyz & yz'x & zxy' \\ def & ghi & jkl \end{align*}
| |
| Slice it into the left nine, middle nine and right nine. Two of them are contained in $D_{4,j}$ so at least two of $def$, $ghi$, and $jkl$ are contained in the corresponding slice of $D_{4,0}$. Slice along a different axis, and at least two of $dgj$, $ehk$, $fil$ are contained in the corresponding slice of $D_{4,0}$. So eight of the nine squares in the bottom row are contained in the corresponding square of $D_{4,0}$. Indeed, slice along other axes, and all points except one are contained within $D_{4,0}$. This point is the intersection of all the 49-point slices.
| |
| So, if there is a 151-point solution, then after removal of the specified point, there is a 150-point solution, within $D_{5,j}$, whose slices in each direction are 52+50+48.
| |
| \begin{align*}z'xy & xyz & yzx' \\ xyz & yz'x & zxy' \\ y'zx & zx'y & xyz \end{align*}
| |
| One point must be lost from columns 3, 6, 7 and 8, and four more from the major diagonal $z'z'z$. That leaves 148 points instead of 150.
| |
| So the 150-point solution does not exist with 52+50+48 slices; so the 151 point solution does not exist. \end{proof}
| |
| \begin{corollary} $c_6 = 450$ \end{corollary}
| |
| \begin{proof}The upper bound follows since $c_6 \leq 3c_5$. The lower bound can be formed by gluing together all the slices $\Gamma_{a,b,c}$ where $(a,b,c)$ is a permutation of $(0,2,4)$ or $(1,2,3)$.\end{proof}
| |
|
| |
|
| | \bibitem{fk2} H. Furstenberg, Y. Katznelson, \emph{A density version of the Hales-Jewett theorem}, J. Anal. Math. \textbf{57} (1991), 64–-119. |
|
| |
|
| \appendix | | \bibitem{kra} |
| | D. Geller, I. Kra, S. Popescu, S. Simanca, \emph{On circulant matrices}, {\tt www.math.sunysb.edu/$\sim$sorin/eprints/circulant.pdf} |
|
| |
|
| \section{Genetic algorithms} | | \bibitem{greenwolf} |
| | B. Green, J. Wolf, \emph{A note on Elkin's improvement of Behrend's construction}, preprint, available at {\tt arxiv.org/abs/0810.0732}. |
|
| |
|
| \include{genetic} | | \bibitem{heule} M. Heule, presentation at {\tt www.st.ewi.tudelft.nl/sat/slides/waerden.pdf} |
|
| |
|
| \begin{thebibliography}{10} | | \bibitem{komlos} |
| | J. Koml\'{o}s, solution to problem P.170 by Leo Moser, Canad. Math. Bull. \textbf{15} (1972), 312--313, 1970. |
|
| |
|
| \bibitem{austin} T. Austin, \emph{Deducing the density Hales-Jewett theorem from an infinitary removal lemma}, preprint. | | %\bibitem{Krisha} K. Krishna, M. Narasimha Murty, \emph{Genetic $K$-means algorithm}, Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on , vol.29, no.3, pp.433-439, Jun 1999 |
|
| |
|
| \bibitem{chandra} | | \bibitem{markstrom} K. Markstrom, {{\tt abel.math.umu.se/$\sim$klasm/Data/HJ/}} |
| A. Chandra, \emph{On the solution of Moser's problem in four dimensions}, Canad. Math. Bull. \textbf{16} (1973), 507--511.
| |
|
| |
|
| \bibitem{chvatal1} V. Chvatal, \emph{Remarks on a problem of Moser}, Canadian Math Bulletin, Vol 15, 1972, 19--21. | | \bibitem{moser} L. Moser, Problem P.170 in Canad. Math. Bull. \textbf{13} (1970), 268. |
|
| |
|
| \bibitem{chvatal2} V. Chvatal, \emph{Edmonds polytopes and a hierarchy of combinatorial problems}, Discrete Math. 4 (1973) 305-337. | | \bibitem{mcc} R. McCutcheon, \emph{The conclusion of the proof of the density Hales-Jewett theorem for $k=3$}, unpublished. |
|
| |
|
| \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{obryant} |
| | K. O'Bryant, \emph{Sets of integers that do not contain long arithmetic progressions}, preprint, available at {\tt arxiv.org/abs/0811.3057}. |
|
| |
|
| \bibitem{fk2} H. Furstenberg, Y. Katznelson, \emph{A density version of the Hales-Jewett theorem}, J. Anal. Math. 57 (1991), 64–-119. MR1191743 | | \bibitem{oeis} |
| | N. J. A. Sloane, Ed. (2008), The On-Line Encyclopedia of Integer Sequences, {\tt www.research.att.com/$\sim$njas/sequences/} |
|
| |
|
| \bibitem{komlos} | | \bibitem{potenchin} |
| J. Komlos, solution to problem P.170 by Leo Moser, Canad. Math.. Bull. vol (??check) (1972), 312-313, 1970.
| | A. Potechin, \emph{Maximal caps in $AG(6, 3)$}, Des. Codes Cryptogr., \textbf{46} (2008), 243--259. |
|
| |
|
| \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{poly} D.H.J. Polymath, \emph{A new proof of the density Hales-Jewett theorem}, preprint, available at {\tt arxiv.org/abs/0910.3926}. |
|
| |
|
| \bibitem{moser} L. Moser, Problem P.170 in Canad. Math. Bull. 13 (1970), 268. | | \bibitem{polywiki} D.H.J. Polymath, {\tt michaelnielsen.org/polymath1/index.php?title=Polymath1} |
|
| |
|
| \bibitem{mcc} R. McCutcheon, \emph{The conclusion of the proof of the density Hales-Jewett theorem for k=3}, unpublished. | | \bibitem{rankin} |
| | R. A. Rankin, \emph{Sets of integers containing not more than a given number of terms in arithmetical progression}, Proc. Roy. Soc. Edinburgh Sect. A \textbf{65} (1960/1961), 332–-344. |
|
| |
|
| \bibitem{poly} D.H.J. Polymath, ???, preprint. | | \bibitem{roth} |
| | K. Roth, \emph{On certain sets of integers, I}, J. Lond. Math. Soc. \textbf{28} (1953), 104-–109. |
|
| |
|
| \bibitem{Rothlauf} F. Rothlauf, D. E. Goldberg, Representations for Genetic and Evolutionary Algorithms. Physica-Verlag, 2002. | | %\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}, J. Amer. Math. Soc. \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{thebibliography} |
\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 prove 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$, and also establishing the asymptotic lower bound $c_{n,k} \geq k^n \exp\left( - O(\sqrt[\ell]{\log n})\right)$ where $\ell$ is the largest integer such that $2k > 2^\ell$.
\end{abstract}
\maketitle
%\today
%\setcounter{tocdepth}{1}
%\tableofcontents
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\input{introduction}
\input{dhj-lown-lower}
\input{dhj-lown}
\input{moser-lower}
\input{moser}
%\input{fujimura}
%\input{higherk}
% \input{coloring}
%\appendix
%\input{genetic}
%\input{integer}
\begin{thebibliography}{10}
\bibitem{ajtai} M. Ajtai, E. Szemer\'edi, \emph{Sets of lattice points that form no squares}, Studia Scientiarum Mathematicarum Hungarica, \textbf{9} (1974-1975), 9--11.
\bibitem{austin} T. Austin, \emph{Deducing the density Hales-Jewett theorem from an infinitary removal lemma}, preprint, available at {\tt arxiv.org/abs/0903.1633}.
\bibitem{beck} J. Beck, Combinatorial Games: Tic-Tac-Toe Theory. Cambridge University Press, 2008, Cambridge.
\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}, Canad. Math. Bull., \textbf{15} (1972) 19--21.
\bibitem{chvatal2} V. Chv\'{a}tal, \emph{Edmonds polytopes and a hierarchy of combinatorial problems}, Discrete Math. \textbf{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. \textbf{75} (1989), 227–-241.
\bibitem{fk2} H. Furstenberg, Y. Katznelson, \emph{A density version of the Hales-Jewett theorem}, J. Anal. Math. \textbf{57} (1991), 64–-119.
\bibitem{kra}
D. Geller, I. Kra, S. Popescu, S. Simanca, \emph{On circulant matrices}, {\tt www.math.sunysb.edu/$\sim$sorin/eprints/circulant.pdf}
\bibitem{greenwolf}
B. Green, J. Wolf, \emph{A note on Elkin's improvement of Behrend's construction}, preprint, available at {\tt arxiv.org/abs/0810.0732}.
\bibitem{heule} M. Heule, presentation at {\tt 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. \textbf{15} (1972), 312--313, 1970.
%\bibitem{Krisha} K. Krishna, M. Narasimha Murty, \emph{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 abel.math.umu.se/$\sim$klasm/Data/HJ/
\bibitem{moser} L. Moser, Problem P.170 in Canad. Math. Bull. \textbf{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, available at {\tt arxiv.org/abs/0811.3057}.
\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)$}, Des. Codes Cryptogr., \textbf{46} (2008), 243--259.
\bibitem{poly} D.H.J. Polymath, \emph{A new proof of the density Hales-Jewett theorem}, preprint, available at {\tt arxiv.org/abs/0910.3926}.
\bibitem{polywiki} D.H.J. Polymath, {\tt michaelnielsen.org/polymath1/index.php?title=Polymath1}
\bibitem{rankin}
R. A. Rankin, \emph{Sets of integers containing not more than a given number of terms in arithmetical progression}, Proc. Roy. Soc. Edinburgh Sect. A \textbf{65} (1960/1961), 332–-344.
\bibitem{roth}
K. Roth, \emph{On certain sets of integers, I}, J. Lond. Math. Soc. \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}, J. Amer. Math. Soc. \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}
