Introduction.tex - Revision history

Teorth at 07:52, 23 January 2010

2010-01-23T07:52:56Z

← Older revision		Revision as of 00:52, 23 January 2010
Line 89:		Line 89:
	This motivates a ``hyper-optimistic'' conjecture:		This motivates a ``hyper-optimistic'' conjecture:

	{\bf a ~~picture showing~~ a Fujimura set?}		\begin{figure}[tb]
			\centerline{\includegraphics{FujimuraPicture.pdf}}
			\caption{A Fujimura set in $\Delta_{6,3}$. The point $(a,b,c)$ is represented by a square at $(a,b)$ labeled with $c$. The Fujimura set is shown in red; its complement in $\Delta_{6,3}$ is shown in gray.}
			\label{fig-pic}
			\end{figure}

	\begin{conjecture}\label{hoc} For any $k \geq 1$ and $n \geq 0$, and any line-free subset $A$ of $[k]^n$, one has		\begin{conjecture}\label{hoc} For any $k \geq 1$ and $n \geq 0$, and any line-free subset $A$ of $[k]^n$, one has

Teorth at 02:34, 20 January 2010

2010-01-20T02:34:46Z

Teorth at 06:41, 16 January 2010

2010-01-16T06:41:10Z

← Older revision		Revision as of 23:41, 15 January 2010
Line 25:		Line 25:
	\begin{theorem}[Asymptotic lower bound for $c_{n,k}$]\label{dhj-lower} For each $k\geq 3$, there is an absolute constant $C>0$ such that		\begin{theorem}[Asymptotic lower bound for $c_{n,k}$]\label{dhj-lower} For each $k\geq 3$, there is an absolute constant $C>0$ such that
	\[ c_{n,k} \geq C k^n \left(\frac{r_k(\sqrt{n})}{\sqrt{n}}\right)^{k-1} = k^n \exp\left( - O(\sqrt[\ell]{\log n}) \right), \]		\[ c_{n,k} \geq C k^n \left(\frac{r_k(\sqrt{n})}{\sqrt{n}}\right)^{k-1} = k^n \exp\left( - O(\sqrt[\ell]{\log n}) \right), \]
	where $\ell$ is the largest integer satisfying $2k>2^{\ell}$. ~~Specifically~~,		where $\ell$ is the largest integer satisfying $2k>2^{\ell}$. More specifically,
	\[ c_{n,k} \geq C k^{n-\alpha(k) \sqrt[\ell]{\log n} + \beta(k) \log\log n},\]		\[ c_{n,k} \geq C k^{n-\alpha(k) \sqrt[\ell]{\log n} + \beta(k) \log\log n},\]
	where all logarithms are base-$k$, and $\alpha(k) = (\log 2)^{1-1/\ell} \ell 2^{(\ell-1)/2-1/\ell}$ and $\beta(k)=(k-1)/(2\ell)$.		where all logarithms are base-$k$, and $\alpha(k) = (\log 2)^{1-1/\ell} \ell 2^{(\ell-1)/2-1/\ell}$ and $\beta(k)=(k-1)/(2\ell)$.
Line 35:		Line 35:
	\end{theorem}		\end{theorem}

	This result is established in Sections~\ref{dhj-lower-sec},~\ref{dhj-upper-sec}. Initially these results were established by an integer program ~~(see Appendix~\ref{integer-sec}~~, but we provide completely computer-free proofs here. The constructions used in Section~\ref{dhj-lower-sec} give reasonably efficient constructions for larger values of $n$; for instance, they show that $3^{99} \leq c_{100,3} \leq 2 \times 3^{99}$. See Section~\ref{dhj-lower-sec} for further discussion.		This result is established in Sections~\ref{dhj-lower-sec},~\ref{dhj-upper-sec}. Initially these results were established by an integer program, but we provide completely computer-free proofs here. The constructions used in Section~\ref{dhj-lower-sec} give reasonably efficient constructions for larger values of $n$; for instance, they show that $3^{99} \leq c_{100,3} \leq 2 \times 3^{99}$. See Section~\ref{dhj-lower-sec} for further discussion.

	We also have several partial results for higher values of $k$: see Section~\ref{higherk-sec}. ~~For results on the closely related \emph{Hales-Jewett numbers} $HJ(k,r)$, see Section~\ref{coloring-sec}.~~		We also have several partial results for higher values of $k$: see Section~\ref{higherk-sec}.

	A variant of the density Hales-Jewett theorem has also been studied in the literature. Define a \emph{geometric line} in $[k]^n$ to be any set of the form $\{ a+ir: i=1,\ldots,k\}$ in $[k]^n$, where we identify $[k]^n$ with a subset of $\Z^n$, and $a, r \in \Z^n$ with $r \neq 0$. Equivalently, a geometric line takes the form $\{ w( i, k+1-i ): i =1,\ldots,k \}$, where $w \in ([k] \cup \{x,\overline{x}\})^n \backslash [k]^n$ is a word of length $n$ using the numbers in $[k]$ and two wildcards $x, \overline{x}$ as the alphabet, with at least one wildcard occuring in $w$, and $w(i,j) \in [k]^n$ is the word formed by substituting $i,j$ for $x,\overline{x}$ respectively. Figure~\ref{fig-geomline} shows the eight geometric lines in $[3]^2$. Clearly every combinatorial line is a geometric line, but not conversely. In general, $[k]^n$ has $((k+2)^n-k^n)/2$ geometric lines.		A variant of the density Hales-Jewett theorem has also been studied in the literature. Define a \emph{geometric line} in $[k]^n$ to be any set of the form $\{ a+ir: i=1,\ldots,k\}$ in $[k]^n$, where we identify $[k]^n$ with a subset of $\Z^n$, and $a, r \in \Z^n$ with $r \neq 0$. Equivalently, a geometric line takes the form $\{ w( i, k+1-i ): i =1,\ldots,k \}$, where $w \in ([k] \cup \{x,\overline{x}\})^n \backslash [k]^n$ is a word of length $n$ using the numbers in $[k]$ and two wildcards $x, \overline{x}$ as the alphabet, with at least one wildcard occuring in $w$, and $w(i,j) \in [k]^n$ is the word formed by substituting $i,j$ for $x,\overline{x}$ respectively. Figure~\ref{fig-geomline} shows the eight geometric lines in $[3]^2$. Clearly every combinatorial line is a geometric line, but not conversely. In general, $[k]^n$ has $((k+2)^n-k^n)/2$ geometric lines.
Line 56:		Line 56:
	\end{theorem}		\end{theorem}

	This result is established in Sections \ref{moser-lower-sec}, \ref{moser-upper-sec}. The arguments given here are computer-assisted; however, we have found alternate (but lengthier) computer-free proofs for the above claims with the the exception of the proof of $c'_{6,3}=353$, which requires one non-trivial computation (Lemma \ref{paretop-4}). These alternate proofs are not given in this paper to save space, but can be found ~~on the wiki for this project~~ at		This result is established in Sections \ref{moser-lower-sec}, \ref{moser-upper-sec}. The arguments given here are computer-assisted; however, we have found alternate (but lengthier) computer-free proofs for the above claims with the the exception of the proof of $c'_{6,3}=353$, which requires one non-trivial computation (Lemma \ref{paretop-4}). These alternate proofs are not given in this paper to save space, but can be found at \cite{polywiki}.

	\~~centerline~~{~~{\tt http://michaelnielsen.org/polymath1/index.php?title=Main\_Page~~}.}

	We establish a lower bound for this problem of $(2+o(1))\binom{n}{i}2^i\leq c'_{n,3}$, which is maximized for $i$ near $2n/3$. This bound is around one-third better than the literature. We also give methods to improve on this construction.		We establish a lower bound for this problem of $(2+o(1))\binom{n}{i}2^i\leq c'_{n,3}$, which is maximized for $i$ near $2n/3$. This bound is around one-third better than the literature. We also give methods to improve on this construction.
Line 83:		Line 81:
	\sum_{a_1,a_2 \geq 0; a_1+a_2 = n} \frac{\|A \cap \Gamma_{a_1,a_2}\|}{\|\Gamma_{a_1,a_2}\|} \leq 1		\sum_{a_1,a_2 \geq 0; a_1+a_2 = n} \frac{\|A \cap \Gamma_{a_1,a_2}\|}{\|\Gamma_{a_1,a_2}\|} \leq 1
	$$		$$
	for any line-free subset $A \subset [2]^n$, where the \emph{cell} $\Gamma_{a_1,\ldots,a_k} \subset [k]^n$ is the set of words in $[k]^n$ which contain exactly $a_i$ $i$'s for each $i=1,\ldots,k$. It is natural to ask whether this inequality can be extended to higher $k$. Let $\Delta_{k,n}$ denote the set of all tuples $(a_1,\ldots,a_k)$ of non-negative integers summing to $n$, define a \emph{simplex} to be a set of $k$ points in $\Delta_{k,n}$ of the form		for any line-free subset $A \subset [2]^n$, where the \emph{cell} $\Gamma_{a_1,\ldots,a_k} \subset [k]^n$ is the set of words in $[k]^n$ which contain exactly $a_i$ $i$'s for each $i=1,\ldots,k$. It is natural to ask whether this inequality can be extended to higher $k$. Let $\Delta_{n,k}$ denote the set of all tuples $(a_1,\ldots,a_k)$ of non-negative integers summing to $n$, define a \emph{simplex} to be a set of $k$ points in $\Delta_{n,k}$ of the form
	$(a_1+r,a_2,\ldots,a_k), (a_1,a_2+r,\ldots,a_k),\ldots,(a_1,a_2,\ldots,a_k+r)$ for some $0 < r \leq n$ and $a_1,\ldots,a_k$ summing to $n-r$, and define a \emph{Fujimura set} to be a subset $B \subset \Delta_{k,n}$ which contains no simplices. Observe that if $w$ is a combinatorial line in $[k]^n$, then		$(a_1+r,a_2,\ldots,a_k), (a_1,a_2+r,\ldots,a_k),\ldots,(a_1,a_2,\ldots,a_k+r)$ for some $0 < r \leq n$ and $a_1,\ldots,a_k$ summing to $n-r$, and define a \emph{Fujimura set}\footnote{Fujimura actually proposed the related problem of finding the largest subset of $\Delta_{n,k}$ that contained no all equilateral triangles; see \cite{fuji}. Our results for Fujimura sets can be found at the page {\tt Fujimura's problem} at \cite{polywiki}.} to be a subset $B \subset \Delta_{n,k}$ which contains no simplices. Observe that if $w$ is a combinatorial line in $[k]^n$, then
	$$ w(1) \in \Gamma_{a_1+r,a_2,\ldots,a_k}, w(2) \in \Gamma_{a_1,a_2+r,\ldots,a_k}, \ldots, w(k) = \Gamma_{a_1,a_2,\ldots,a_k+r}$$		$$ w(1) \in \Gamma_{a_1+r,a_2,\ldots,a_k}, w(2) \in \Gamma_{a_1,a_2+r,\ldots,a_k}, \ldots, w(k) = \Gamma_{a_1,a_2,\ldots,a_k+r}$$
	for some simplex $(a_1+r,a_2,\ldots,a_k), (a_1,a_2+r,\ldots,a_k),\ldots,(a_1,a_2,\ldots,a_k+r)$. Thus, if $B$ is a Fujimura set, then $A := \bigcup_{\vec a \in B} \Gamma_{\vec a}$ is line-free. Note also that		for some simplex $(a_1+r,a_2,\ldots,a_k), (a_1,a_2+r,\ldots,a_k),\ldots,(a_1,a_2,\ldots,a_k+r)$. Thus, if $B$ is a Fujimura set, then $A := \bigcup_{\vec a \in B} \Gamma_{\vec a}$ is line-free. Note also that
	$$		$$
	\sum_{\vec a \in \Delta_{k,n}} \frac{\|A \cap \Gamma_{\vec a}\|}{\|\Gamma_{\vec a}\|} = \|B\|.		\sum_{\vec a \in \Delta_{n,k}} \frac{\|A \cap \Gamma_{\vec a}\|}{\|\Gamma_{\vec a}\|} = \|B\|.
	$$		$$
	This motivates a ``hyper-optimistic'' conjecture:		This motivates a ``hyper-optimistic'' conjecture:
Line 96:		Line 94:
	\begin{conjecture}\label{hoc} For any $k \geq 1$ and $n \geq 0$, and any line-free subset $A$ of $[k]^n$, one has		\begin{conjecture}\label{hoc} For any $k \geq 1$ and $n \geq 0$, and any line-free subset $A$ of $[k]^n$, one has
	$$		$$
	\sum_{\vec a \in \Delta_{k,n}} \frac{\|A \cap \Gamma_{\vec a}\|}{\|\Gamma_{\vec a}\|} \leq c^\mu_{k,n},$$		\sum_{\vec a \in \Delta_{n,k}} \frac{\|A \cap \Gamma_{\vec a}\|}{\|\Gamma_{\vec a}\|} \leq c^\mu_{n,k},$$
	where $c^\mu_{k,n}$ is the maximal size of a Fujimura set in $\Delta_{k,n}$.		where $c^\mu_{n,k}$ is the maximal size of a Fujimura set in $\Delta_{n,k}$.
	\end{conjecture}		\end{conjecture}

	One can show that this conjecture for a fixed value of $k$ would imply Theorem \ref{dhj} for the same value of $k$, in much the same way that the LYM inequality is known to imply Sperner's theorem. The LYM inequality asserts that Conjecture \ref{hoc} is true for $k \leq 2$. As far as we know this conjecture could hold in $k=3$. However, we ~~know that it fails~~ for ~~all even~~ $k\ge 4$~~, see Section~~~\~~ref~~{~~higherk-sec~~}.		One can show that this conjecture for a fixed value of $k$ would imply Theorem \ref{dhj} for the same value of $k$, in much the same way that the LYM inequality is known to imply Sperner's theorem. The LYM inequality asserts that Conjecture \ref{hoc} is true for $k \leq 2$. As far as we know, this conjecture could hold in $k=3$. However, we found a simple counterexample for $k=4$ and $n=2$, given by the line-free set
			$$A := \{(1, 1), (1, 2), (1, 3), (2, 1), (2, 3), (2, 4), (3, 2), (3, 3), (3,4), (4, 1), (4, 2), (4, 4)\}$$
			together with the computation that $c^\mu_{4,2}=7$. It is in fact likely that this conjecture fails for all higher $k$ also.

	We are interested in removing all upward-pointing equilateral triangles from a triangular grid. Fujimura actually proposed the similar problem of removing all equilateral triangles at this website: www.puzzles.com/PuzzlePlayground/CoinsAndTriangles/CoinsAndTriangles.htm

	~~In Section \ref{fujimura-sec} we give some bounds on these numbers. Explicit values are given for $\overline{c}^\mu_n$ up to $n=13$, and general upper and lower bounds are given for all $n$.~~

	\subsection{Notation}\label{notation-sec}		\subsection{Notation}\label{notation-sec}
Line 121:		Line 118:

	For the analysis of Moser sets in $[k]^n$, the symmetries are a bit different. One can still permute the $n$ coordinates, but one is no longer free to permute the alphabet $[k]$. Instead, one can \emph{reflect} an individual coordinate, for instance sending each word $x_1 \ldots x_n$ to its reflection $x_1 \ldots x_{i-1} (k+1-x_i) x_{i+1} \ldots x_n$. Together, this gives a symmetry group of order $2^n n!$ on the cube $[k]^n$, which we refer to as the \emph{geometric symmetry group} of the cube $[k]^n$; this group maps geometric lines to geometric lines, and thus maps Moser sets to Moser sets. Two Moser sets which are related by an element of this symmetry group will be called (geometrically) \emph{equivalent}. For instance, a sphere $S_{i,n}$ is equivalent only to itself, and $S_{i,n}^o$, $S_{i,n}^e$ are equivalent only to each other.		For the analysis of Moser sets in $[k]^n$, the symmetries are a bit different. One can still permute the $n$ coordinates, but one is no longer free to permute the alphabet $[k]$. Instead, one can \emph{reflect} an individual coordinate, for instance sending each word $x_1 \ldots x_n$ to its reflection $x_1 \ldots x_{i-1} (k+1-x_i) x_{i+1} \ldots x_n$. Together, this gives a symmetry group of order $2^n n!$ on the cube $[k]^n$, which we refer to as the \emph{geometric symmetry group} of the cube $[k]^n$; this group maps geometric lines to geometric lines, and thus maps Moser sets to Moser sets. Two Moser sets which are related by an element of this symmetry group will be called (geometrically) \emph{equivalent}. For instance, a sphere $S_{i,n}$ is equivalent only to itself, and $S_{i,n}^o$, $S_{i,n}^e$ are equivalent only to each other.

			\subsection{About this project}

			This paper is part of the \emph{Polymath project}, which was launched by Timothy Gowers in February 2009 as an experiment to see if research mathematics could be conducted by a massive online collaboration. The first project in this series, \emph{Polymath1}, was was focused on understanding the density Hales-Jewett numbers $c_{n,k}$, and was split up into two sub-projects, namely an (ultimately successful) attack on the density Hales-Jewett theorem $c_{n,k} = o(k^n)$ (resulting in the paper \cite{poly}), and a collaborative project on computing $c_{n,k}$ and related quantities (such as $c'_{n,k}$) for various small values of $n$ and $k$. This project (which was administered by Terence Tao) resulted in this current paper.

			Being such a collaborative project, many independent aspects of the problem were studied, with varying degrees of success. For reasons of space (and also due to the partial nature of some of the results), this paper does not encompass the entire collection of observations and achievements made during the research phase of the project (which lasted for approximately three months). In particular, alternate proofs of some of the results here have been omitted, as well as some auxiliary results on related numbers, such as coloring Hales-Jewett numbers. However, these results can be accessed from the web site of this project at \cite{polywiki}.

Mpeake at 13:38, 27 July 2009

2009-07-27T13:38:19Z

← Older revision		Revision as of 06:38, 27 July 2009
Line 120:		Line 120:
	In the density Hales-Jewett problem, there are two types of symmetries on $[k]^n$ which map combinatorial lines to combinatorial lines (and hence line-free sets to line-free sets). The first is a permutation of the alphabet $[k]$; the second is a permutation of the $n$ coordinates. Together, this gives a symmetry group of order $k!n!$ on the cube $[k]^n$, which we refer to as the \emph{combinatorial symmetry group} of the cube $[k]^n$. Two sets which are related by an element of this symmetry group will be called (combinatorially) \emph{equivalent}, thus for instance any two slices are combinatorially equivalent.		In the density Hales-Jewett problem, there are two types of symmetries on $[k]^n$ which map combinatorial lines to combinatorial lines (and hence line-free sets to line-free sets). The first is a permutation of the alphabet $[k]$; the second is a permutation of the $n$ coordinates. Together, this gives a symmetry group of order $k!n!$ on the cube $[k]^n$, which we refer to as the \emph{combinatorial symmetry group} of the cube $[k]^n$. Two sets which are related by an element of this symmetry group will be called (combinatorially) \emph{equivalent}, thus for instance any two slices are combinatorially equivalent.

	For the analysis of Moser sets in $[k]^n$, the symmetries are a bit different. One can still permute the $n$ coordinates, but one is no longer free to permute the alphabet $[k]$. Instead, one can \emph{reflect} an individual coordinate, for instance sending each word $x_1 \ldots x_n$ to its reflection $x_1 \ldots x_{i-1} (k+1-x_i) x_{i+1} \ldots x_n$. Together, this gives a symmetry group of order $2^k n!$ on the cube $[k]^n$, which we refer to as the \emph{geometric symmetry group} of the cube $[k]^n$; this group maps geometric lines to geometric lines, and thus maps Moser sets to Moser sets. Two Moser sets which are related by an element of this symmetry group will be called (geometrically) \emph{equivalent}. For instance, a sphere $S_{i,n}$ is equivalent only to itself, and $S_{i,n}^o$, $S_{i,n}^e$ are equivalent only to each other.		For the analysis of Moser sets in $[k]^n$, the symmetries are a bit different. One can still permute the $n$ coordinates, but one is no longer free to permute the alphabet $[k]$. Instead, one can \emph{reflect} an individual coordinate, for instance sending each word $x_1 \ldots x_n$ to its reflection $x_1 \ldots x_{i-1} (k+1-x_i) x_{i+1} \ldots x_n$. Together, this gives a symmetry group of order $2^n n!$ on the cube $[k]^n$, which we refer to as the \emph{geometric symmetry group} of the cube $[k]^n$; this group maps geometric lines to geometric lines, and thus maps Moser sets to Moser sets. Two Moser sets which are related by an element of this symmetry group will be called (geometrically) \emph{equivalent}. For instance, a sphere $S_{i,n}$ is equivalent only to itself, and $S_{i,n}^o$, $S_{i,n}^e$ are equivalent only to each other.

Teorth at 23:14, 25 July 2009

2009-07-25T23:14:38Z

← Older revision		Revision as of 16:14, 25 July 2009
Line 19:		Line 19:
	\end{remark}		\end{remark}

	The Furstenberg-Katznelson proof of Theorem~\ref{dhj} relied on ergodic-theory techniques and did not give an explicit decay rate for $c_{n,k}$. Recently, two further proofs of this theorem have appeared, by Austin~\cite{austin} and by the sister Polymath project to this one~\cite{poly}. The proof of~\cite{austin} also used ergodic theory, but the proof in~\cite{poly} was combinatorial and gave effective bounds for $c_{n,k}$ in the limit $n \to \infty$. For example, if $n$ can be written as an exponential tower 2^2^2~~^...^~~2 with $m$ 2s, then $c_{n,3} \le 3^n m^{-1/3}$. However, these bounds are not believed to be sharp, and in any case are only non-trivial in the asymptotic regime when $n$ is sufficiently large depending on $k$.		The Furstenberg-Katznelson proof of Theorem~\ref{dhj} relied on ergodic-theory techniques and did not give an explicit decay rate for $c_{n,k}$. Recently, two further proofs of this theorem have appeared, by Austin~\cite{austin} and by the sister Polymath project to this one~\cite{poly}. The proof of~\cite{austin} also used ergodic theory, but the proof in~\cite{poly} was combinatorial and gave effective bounds for $c_{n,k}$ in the limit $n \to \infty$. For example, if $n$ can be written as an exponential tower $2 \uparrow 2 \uparrow 2 \uparrow \ldots \uparrow 2$ with $m$ 2s, then $c_{n,3} \le 3^n m^{-1/3}$. However, these bounds are not believed to be sharp, and in any case are only non-trivial in the asymptotic regime when $n$ is sufficiently large depending on $k$.

	Our first result is the following asymptotic lower bound. The construction is based on the recent refinements \cite{elkin,greenwolf,obryant} of a well-known construction of Behrend~\cite{behrend} and Rankin~\cite{rankin}. The proof of Theorem~\ref{dhj-lower} is in Section~\ref{dhj-lower-sec}. Let $r_k(n)$ be the maximum size of a subset of $[n]$ that does not contain a $k$-term arithmetic progression.		Our first result is the following asymptotic lower bound. The construction is based on the recent refinements \cite{elkin,greenwolf,obryant} of a well-known construction of Behrend~\cite{behrend} and Rankin~\cite{rankin}. The proof of Theorem~\ref{dhj-lower} is in Section~\ref{dhj-lower-sec}. Let $r_k(n)$ be the maximum size of a subset of $[n]$ that does not contain a $k$-term arithmetic progression.
Line 74:		Line 74:
	for $n \geq 2$. This bound is not quite optimal; for instance, it gives a lower bound of $c'_{6,3}=344$.		for $n \geq 2$. This bound is not quite optimal; for instance, it gives a lower bound of $c'_{6,3}=344$.

	\begin{remark} Let $c''_{n,3}$ be the size of the largest subset of ${\~~Bbb~~ F}_3^n$ which contains no lines $x, x+r, x+2r$ with $x,r \in {\mathbb F}_3^n$ and $r \neq 0$, where ${\mathbb F}_3$ is the field of three elements. Clearly one has $c''_{n,3} \leq c'_{n,3} \leq c_{n,3}$. It is known that		\begin{remark} Let $c''_{n,3}$ be the size of the largest subset of ${\mathbb F}_3^n$ which contains no lines $x, x+r, x+2r$ with $x,r \in {\mathbb F}_3^n$ and $r \neq 0$, where ${\mathbb F}_3$ is the field of three elements. Clearly one has $c''_{n,3} \leq c'_{n,3} \leq c_{n,3}$. It is known that
	$$ c''_{0,3}=1; c''_{1,3}=2; c''_{2,3}=4; c'_{3,3}=9; c'_{4,3}=20; c''_{5,3}=45; c''_{6,3} = 112;$$		$$ c''_{0,3}=1; c''_{1,3}=2; c''_{2,3}=4; c'_{3,3}=9; c'_{4,3}=20; c''_{5,3}=45; c''_{6,3} = 112;$$
	see \cite{potenchin}.		see \cite{potenchin}.

Mpeake at 10:05, 14 July 2009

2009-07-14T10:05:05Z

← Older revision		Revision as of 03:05, 14 July 2009
Line 19:		Line 19:
	\end{remark}		\end{remark}

	The Furstenberg-Katznelson proof of Theorem~\ref{dhj} relied on ergodic-theory techniques and did not give an explicit decay rate for $c_{n,k}$. Recently, two further proofs of this theorem have appeared, by Austin~\cite{austin} and by the sister Polymath project to this one~\cite{poly}. The proof of~\cite{austin} also used ergodic theory, but the proof in~\cite{poly} was combinatorial and gave effective bounds for $c_{n,k}$ in the limit $n \to \infty$. {\~~bf Note~~ - ~~need to ask what those explicit bounds are!~~} However, these bounds are not believed to be sharp, and in any case are only non-trivial in the asymptotic regime when $n$ is sufficiently large depending on $k$.		The Furstenberg-Katznelson proof of Theorem~\ref{dhj} relied on ergodic-theory techniques and did not give an explicit decay rate for $c_{n,k}$. Recently, two further proofs of this theorem have appeared, by Austin~\cite{austin} and by the sister Polymath project to this one~\cite{poly}. The proof of~\cite{austin} also used ergodic theory, but the proof in~\cite{poly} was combinatorial and gave effective bounds for $c_{n,k}$ in the limit $n \to \infty$. For example, if $n$ can be written as an exponential tower 2^2^2^...^2 with $m$ 2s, then $c_{n,3} \le 3^n m^{-1/3}$. However, these bounds are not believed to be sharp, and in any case are only non-trivial in the asymptotic regime when $n$ is sufficiently large depending on $k$.

	Our first result is the following asymptotic lower bound. The construction is based on the recent refinements \cite{elkin,greenwolf,obryant} of a well-known construction of Behrend~\cite{behrend} and Rankin~\cite{rankin}. The proof of Theorem~\ref{dhj-lower} is in Section~\ref{dhj-lower-sec}. Let $r_k(n)$ be the maximum size of a subset of $[n]$ that does not contain a $k$-term arithmetic progression.		Our first result is the following asymptotic lower bound. The construction is based on the recent refinements \cite{elkin,greenwolf,obryant} of a well-known construction of Behrend~\cite{behrend} and Rankin~\cite{rankin}. The proof of Theorem~\ref{dhj-lower} is in Section~\ref{dhj-lower-sec}. Let $r_k(n)$ be the maximum size of a subset of $[n]$ that does not contain a $k$-term arithmetic progression.

Mpeake at 06:32, 14 July 2009

2009-07-14T06:32:40Z

← Older revision		Revision as of 23:32, 13 July 2009
Line 100:		Line 100:
	\end{conjecture}		\end{conjecture}

	One can show that this conjecture for a fixed value of $k$ would imply Theorem \ref{dhj} for the same value of $k$, in much the same way that the LYM inequality is known to imply Sperner's theorem. The LYM inequality asserts that Conjecture \ref{hoc} is true for $k \leq 2$. As far as we know this conjecture could hold in $k=3$. However, we know that it fails for all even $k\ge 4$, see Section~\ref{~~fujimura~~-sec}.		One can show that this conjecture for a fixed value of $k$ would imply Theorem \ref{dhj} for the same value of $k$, in much the same way that the LYM inequality is known to imply Sperner's theorem. The LYM inequality asserts that Conjecture \ref{hoc} is true for $k \leq 2$. As far as we know this conjecture could hold in $k=3$. However, we know that it fails for all even $k\ge 4$, see Section~\ref{higherk-sec}.

	We are interested in removing all upward-pointing equilateral triangles from a triangular grid. Fujimura actually proposed the similar problem of removing all equilateral triangles at this website: www.puzzles.com/PuzzlePlayground/CoinsAndTriangles/CoinsAndTriangles.htm		We are interested in removing all upward-pointing equilateral triangles from a triangular grid. Fujimura actually proposed the similar problem of removing all equilateral triangles at this website: www.puzzles.com/PuzzlePlayground/CoinsAndTriangles/CoinsAndTriangles.htm

Mpeake at 06:30, 14 July 2009

2009-07-14T06:30:42Z

← Older revision		Revision as of 23:30, 13 July 2009
Line 35:		Line 35:
	\end{theorem}		\end{theorem}

	This result is established in Sections~\ref{dhj-lower-sec},~\ref{dhj-upper-sec}. Initially these results were established by an integer program (see Appendix~\ref{integer-sec}, but we provide completely computer-free proofs here. The constructions used in ~~Theorem~~~\ref{dhj-~~upper~~} give reasonably efficient constructions for larger values of $n$; for instance, they show that $3^{99} \leq c_{100,3} \leq 2 \times 3^{99}$. See Section~\ref{dhj-lower-sec} for further discussion.		This result is established in Sections~\ref{dhj-lower-sec},~\ref{dhj-upper-sec}. Initially these results were established by an integer program (see Appendix~\ref{integer-sec}, but we provide completely computer-free proofs here. The constructions used in Section~\ref{dhj-lower-sec} give reasonably efficient constructions for larger values of $n$; for instance, they show that $3^{99} \leq c_{100,3} \leq 2 \times 3^{99}$. See Section~\ref{dhj-lower-sec} for further discussion.

	We also have several partial results for higher values of $k$: see Section~\ref{higherk-sec}. For results on the closely related \emph{Hales-Jewett numbers} $HJ(k,r)$, see Section~\ref{coloring-sec}.		We also have several partial results for higher values of $k$: see Section~\ref{higherk-sec}. For results on the closely related \emph{Hales-Jewett numbers} $HJ(k,r)$, see Section~\ref{coloring-sec}.

	A variant of the density Hales-Jewett theorem has also been studied in the literature. Define a \emph{geometric line} in $[k]^n$ to be any set of the form $\{ a+ir: i=1,\ldots,k\}$ in $[k]^n$, where we identify $[k]^n$ with a subset of $\Z^n$, and $a, r \in \Z^n$ with $r \neq 0$. Equivalently, a geometric line takes the form $\{ w( i, k+1-i ): i =1,\ldots,k \}$, where $w \in ([k] \cup \{x,\overline{x}\})^n \backslash [k]^n$ is a word of length $n$ using the numbers in $[k]$ and two wildcards $x, \overline{x}$ as the alphabet, with at least one wildcard occuring in $w$, and $w(i,j) \in [k]^n$ is the word formed by substituting $i,j$ for $x,\overline{x}$ respectively. Figure~\ref{fig-geomline} shows the eight geometric lines in $[3]^2$. Clearly every combinatorial line is a geometric line, but not conversely.		A variant of the density Hales-Jewett theorem has also been studied in the literature. Define a \emph{geometric line} in $[k]^n$ to be any set of the form $\{ a+ir: i=1,\ldots,k\}$ in $[k]^n$, where we identify $[k]^n$ with a subset of $\Z^n$, and $a, r \in \Z^n$ with $r \neq 0$. Equivalently, a geometric line takes the form $\{ w( i, k+1-i ): i =1,\ldots,k \}$, where $w \in ([k] \cup \{x,\overline{x}\})^n \backslash [k]^n$ is a word of length $n$ using the numbers in $[k]$ and two wildcards $x, \overline{x}$ as the alphabet, with at least one wildcard occuring in $w$, and $w(i,j) \in [k]^n$ is the word formed by substituting $i,j$ for $x,\overline{x}$ respectively. Figure~\ref{fig-geomline} shows the eight geometric lines in $[3]^2$. Clearly every combinatorial line is a geometric line, but not conversely. In general, $[k]^n$ has $((k+2)^n-k^n)/2$ geometric lines.

	\begin{figure}[tb]		\begin{figure}[tb]
Line 100:		Line 100:
	\end{conjecture}		\end{conjecture}

	One can show that this conjecture for a fixed value of $k$ would imply Theorem \ref{dhj} for the same value of $k$, in much the same way that the LYM inequality is known to imply Sperner's theorem. The LYM inequality asserts that Conjecture \ref{hoc} is true for $k \leq 2$. As far as we know this conjecture could hold in $k=3$. However, we know that it fails for $k=4$; see ~~???.~~ {~~\bf do we know it fails for higher k also?~~}		One can show that this conjecture for a fixed value of $k$ would imply Theorem \ref{dhj} for the same value of $k$, in much the same way that the LYM inequality is known to imply Sperner's theorem. The LYM inequality asserts that Conjecture \ref{hoc} is true for $k \leq 2$. As far as we know this conjecture could hold in $k=3$. However, we know that it fails for all even $k\ge 4$, see Section~\ref{fujimura-sec}.

	~~The~~ problem of ~~computing $c^\mu_{k,n}$ was essentially proposed by Fujimura ({\bf reference?})~~. In Section \ref{fujimura-sec} we give some bounds on these numbers. {\~~bf be more specific here!}~~		We are interested in removing all upward-pointing equilateral triangles from a triangular grid. Fujimura actually proposed the similar problem of removing all equilateral triangles at this website: www.puzzles.com/PuzzlePlayground/CoinsAndTriangles/CoinsAndTriangles.htm

			In Section \ref{fujimura-sec} we give some bounds on these numbers. Explicit values are given for $\overline{c}^\mu_n$ up to $n=13$, and general upper and lower bounds are given for all $n$.

	\subsection{Notation}\label{notation-sec}		\subsection{Notation}\label{notation-sec}

Teorth at 06:49, 10 July 2009

2009-07-10T06:49:03Z

← Older revision		Revision as of 23:49, 9 July 2009
Line 53:		Line 53:
	were known~\cite{chvatal2},~\cite{chandra} (this is Sequence A003142 in the OEIS~\cite{oeis}). We extend this sequence slightly:		were known~\cite{chvatal2},~\cite{chandra} (this is Sequence A003142 in the OEIS~\cite{oeis}). We extend this sequence slightly:

	\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 355~~$.		\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 $c'_{6,3} = 353$.
	\end{theorem}		\end{theorem}

	This result is established in Sections \ref{moser-lower-sec}, \ref{moser-upper-sec}. The ~~bounds~~ here ~~were initially~~ computer-assisted ~~by an integer program~~ (~~see Appendix \ref{integer-sec}~~)~~, but is now mostly~~ computer-free, with the exception the $c'_{6,3}$ ~~bounds~~, ~~as well as~~ one ~~fact concerning Moser sets in $[3]^3$~~ (Lemma \ref{paretop}) ~~which can be easily checked by brute force computer search~~ but ~~which~~ can ~~probably also~~ be ~~derived in a computer-free manner also~~.		This result is established in Sections \ref{moser-lower-sec}, \ref{moser-upper-sec}. The arguments given here are computer-assisted; however, we have found alternate (but lengthier) computer-free proofs for the above claims with the the exception of the proof of $c'_{6,3}=353$, which requires one non-trivial computation (Lemma \ref{paretop-4}). These alternate proofs are not given in this paper to save space, but can be found on the wiki for this project at

			\centerline{{\tt http://michaelnielsen.org/polymath1/index.php?title=Main\_Page}.}

	We establish a lower bound for this problem of $(2+o(1))\binom{n}{i}2^i\leq c'_{n,3}$, which is maximized for $i$ near $2n/3$. This bound is around one-third better than the literature. We also give methods to improve on this construction.		We establish a lower bound for this problem of $(2+o(1))\binom{n}{i}2^i\leq c'_{n,3}$, which is maximized for $i$ near $2n/3$. This bound is around one-third better than the literature. We also give methods to improve on this construction.
Line 72:		Line 74:
	for $n \geq 2$. This bound is not quite optimal; for instance, it gives a lower bound of $c'_{6,3}=344$.		for $n \geq 2$. This bound is not quite optimal; for instance, it gives a lower bound of $c'_{6,3}=344$.

	~~For~~ $n=6$, ~~the best lower bound we have was initially computed by a genetic algorithm~~; see ~~Appendix~~ \~~ref~~{~~genetic-alg~~}.		\begin{remark} Let $c''_{n,3}$ be the size of the largest subset of ${\Bbb F}_3^n$ which contains no lines $x, x+r, x+2r$ with $x,r \in {\mathbb F}_3^n$ and $r \neq 0$, where ${\mathbb F}_3$ is the field of three elements. Clearly one has $c''_{n,3} \leq c'_{n,3} \leq c_{n,3}$. It is known that
			$$ c''_{0,3}=1; c''_{1,3}=2; c''_{2,3}=4; c'_{3,3}=9; c'_{4,3}=20; c''_{5,3}=45; c''_{6,3} = 112;$$
			see \cite{potenchin}.
			\end{remark}

	As mentioned earlier, the sharp bound on $c_{n,2}$ comes from Sperner's theorem. It is known that Sperner's theorem can be refined to the \emph{Lubell-Meshalkin-Yamamoto (LMY) inequality}, which in our language asserts that		As mentioned earlier, the sharp bound on $c_{n,2}$ comes from Sperner's theorem. It is known that Sperner's theorem can be refined to the \emph{Lubell-Meshalkin-Yamamoto (LMY) inequality}, which in our language asserts that

OBryant: Adjusted text to refer to picture of geometric lines

2009-07-02T18:09:33Z

Adjusted text to refer to picture of geometric lines

← Older revision		Revision as of 11:09, 2 July 2009
Line 39:		Line 39:
	We also have several partial results for higher values of $k$: see Section~\ref{higherk-sec}. For results on the closely related \emph{Hales-Jewett numbers} $HJ(k,r)$, see Section~\ref{coloring-sec}.		We also have several partial results for higher values of $k$: see Section~\ref{higherk-sec}. For results on the closely related \emph{Hales-Jewett numbers} $HJ(k,r)$, see Section~\ref{coloring-sec}.

	A variant of the density Hales-Jewett theorem has also been studied in the literature. Define a \emph{geometric line} in $[k]^n$ to be any set of the form $\{ a+ir: i=1,\ldots,k\}$ in $[k]^n$, where we identify $[k]^n$ with a subset of $\Z^n$, and $a, r \in \Z^n$ with $r \neq 0$. Equivalently, a geometric line takes the form $\{ w( i, k+1-i ): i =1,\ldots,k \}$, where $w \in ([k] \cup \{x,\overline{x}\})^n \backslash [k]^n$ is a word of length $n$ using the numbers in $[k]$ and two wildcards $x, \overline{x}$ as the alphabet, with at least one wildcard occuring in $w$, and $w(i,j) \in [k]^n$ is the word formed by substituting $i,j$ for $x,\overline{x}$ respectively. ~~Thus for instance~~ $[3]^2~~$ contains the geometric lines $2x = 2\overline{x} = \{21,22,23\}$, $xx = \overline{x}\overline{x}=\{11,22,33\}$, and $x\overline{x}=\overline{x}x=\{13,22,31\}~~$. Clearly every combinatorial line is a geometric line, but not conversely.		A variant of the density Hales-Jewett theorem has also been studied in the literature. Define a \emph{geometric line} in $[k]^n$ to be any set of the form $\{ a+ir: i=1,\ldots,k\}$ in $[k]^n$, where we identify $[k]^n$ with a subset of $\Z^n$, and $a, r \in \Z^n$ with $r \neq 0$. Equivalently, a geometric line takes the form $\{ w( i, k+1-i ): i =1,\ldots,k \}$, where $w \in ([k] \cup \{x,\overline{x}\})^n \backslash [k]^n$ is a word of length $n$ using the numbers in $[k]$ and two wildcards $x, \overline{x}$ as the alphabet, with at least one wildcard occuring in $w$, and $w(i,j) \in [k]^n$ is the word formed by substituting $i,j$ for $x,\overline{x}$ respectively. Figure~\ref{fig-geomline} shows the eight geometric lines in $[3]^2$. Clearly every combinatorial line is a geometric line, but not conversely.

	\begin{figure}[tb]		\begin{figure}[tb]

← Older revision		Revision as of 19:34, 19 January 2010
Line 30:		Line 30:
	\end{theorem}		\end{theorem}

	In the case of small $n$, we focus primarily on the first non-trivial case $k=3$. We have computed the following explicit values of $c_{n,3}$:		In the case of small $n$, we focus primarily on the first non-trivial case $k=3$. We have computed the following explicit values of $c_{n,3}$ (entered in the OEIS~\cite{oeis} as A156762):

	\begin{theorem}[Explicit values of $c_{n,3}$]\label{dhj-upper} We have $c_{0,3} = 1$, $c_{1,3} = 2$, $c_{2,3} = 6$, $c_{3,3} = 18$, $c_{4,3} = 52$, $c_{5,3}=150$, and $c_{6,3}=450$. ~~(This has been entered in the OEIS~\cite{oeis} as A156762.)~~		\begin{theorem}[Explicit values of $c_{n,3}$]\label{dhj-upper} We have $c_{0,3} = 1$, $c_{1,3} = 2$, $c_{2,3} = 6$, $c_{3,3} = 18$, $c_{4,3} = 52$, $c_{5,3}=150$, and $c_{6,3}=450$.
	\end{theorem}		\end{theorem}

	This result is established in Sections~\ref{dhj-lower-sec},~\ref{dhj-upper-sec}. Initially these results were established by an integer program, but we provide completely computer-free proofs here. The constructions used in Section~\ref{dhj-lower-sec} give reasonably efficient constructions for larger values of $n$; for instance, they show that $3^{99} \leq c_{100,3} \leq 2 \times 3^{99}$. See Section~\ref{dhj-lower-sec} for further discussion.		This result is established in Sections~\ref{dhj-lower-sec},~\ref{dhj-upper-sec}. Initially these results were established by an integer program, but we provide completely computer-free proofs here. The constructions used in Section~\ref{dhj-lower-sec} give reasonably efficient constructions for larger values of $n$; for instance, they show that $3^{99} \leq c_{100,3} \leq 2 \times 3^{99}$. See Section~\ref{dhj-lower-sec} for further discussion.

	We also have several partial results for higher values of $k$: see Section~\ref{higherk-sec}.		%We also have several partial results for higher values of $k$: see Section~\ref{higherk-sec}.

	A variant of the density Hales-Jewett theorem has also been studied in the literature. Define a \emph{geometric line} in $[k]^n$ to be any set of the form $\{ a+ir: i=1,\ldots,k\}$ in $[k]^n$, where we identify $[k]^n$ with a subset of $\Z^n$, and $a, r \in \Z^n$ with $r \neq 0$. Equivalently, a geometric line takes the form $\{ w( i, k+1-i ): i =1,\ldots,k \}$, where $w \in ([k] \cup \{x,\overline{x}\})^n \backslash [k]^n$ is a word of length $n$ using the numbers in $[k]$ and two wildcards $x, \overline{x}$ as the alphabet, with at least one wildcard occuring in $w$, and $w(i,j) \in [k]^n$ is the word formed by substituting $i,j$ for $x,\overline{x}$ respectively. Figure~\ref{fig-geomline} shows the eight geometric lines in $[3]^2$. Clearly every combinatorial line is a geometric line, but not conversely. In general, $[k]^n$ has $((k+2)^n-k^n)/2$ geometric lines.		A variant of the density Hales-Jewett theorem has also been studied in the literature. Define a \emph{geometric line} in $[k]^n$ to be any set of the form $\{ a+ir: i=1,\ldots,k\}$ in $[k]^n$, where we identify $[k]^n$ with a subset of $\Z^n$, and $a, r \in \Z^n$ with $r \neq 0$. Equivalently, a geometric line takes the form $\{ w( i, k+1-i ): i =1,\ldots,k \}$, where $w \in ([k] \cup \{x,\overline{x}\})^n \backslash [k]^n$ is a word of length $n$ using the numbers in $[k]$ and two wildcards $x, \overline{x}$ as the alphabet, with at least one wildcard occuring in $w$, and $w(i,j) \in [k]^n$ is the word formed by substituting $i,j$ for $x,\overline{x}$ respectively. Figure~\ref{fig-geomline} shows the eight geometric lines in $[3]^2$. Clearly every combinatorial line is a geometric line, but not conversely. In general, $[k]^n$ has $((k+2)^n-k^n)/2$ geometric lines.
Line 60:		Line 60:
	We establish a lower bound for this problem of $(2+o(1))\binom{n}{i}2^i\leq c'_{n,3}$, which is maximized for $i$ near $2n/3$. This bound is around one-third better than the literature. We also give methods to improve on this construction.		We establish a lower bound for this problem of $(2+o(1))\binom{n}{i}2^i\leq c'_{n,3}$, which is maximized for $i$ near $2n/3$. This bound is around one-third better than the literature. We also give methods to improve on this construction.

	Earlier lower bounds were known:		Earlier lower bounds were known. Indeed, let $A(n,d)$ denote the size of the largest binary code of length $n$
	let $A(n,d)$ denote the size of the largest binary code of length $n$
	and minimal distance $d$. Then		and minimal distance $d$. Then
	\begin{equation}\label{cnchvatalintro}		\begin{equation}\label{cnchvatalintro}
Line 70:		Line 69:
	c'_{n,3} \geq \binom{n+1}{\lfloor \frac{2n+1}{3} \rfloor} 2^{\lfloor \frac{2n+1}{3} \rfloor - 1}		c'_{n,3} \geq \binom{n+1}{\lfloor \frac{2n+1}{3} \rfloor} 2^{\lfloor \frac{2n+1}{3} \rfloor - 1}
	\end{equation}		\end{equation}
	for $n \geq 2$. This bound is not quite optimal; for instance, it gives a lower bound of $c'_{6,3}=344$.		for $n \geq 2$. This bound is not quite optimal; for instance, it gives a lower bound of $c'_{6,3} \geq 344$.

	\begin{remark} Let $c''_{n,3}$ be the size of the largest subset of ${\mathbb F}_3^n$ which contains no lines $x, x+r, x+2r$ with $x,r \in {\mathbb F}_3^n$ and $r \neq 0$, where ${\mathbb F}_3$ is the field of three elements. Clearly one has $c''_{n,3} \leq c'_{n,3} \leq c_{n,3}$. It is known that		\begin{remark} Let $c''_{n,3}$ be the size of the largest subset of ${\mathbb F}_3^n$ which contains no lines $x, x+r, x+2r$ with $x,r \in {\mathbb F}_3^n$ and $r \neq 0$, where ${\mathbb F}_3$ is the field of three elements. Clearly one has $c''_{n,3} \leq c'_{n,3} \leq c_{n,3}$. It is known that
Line 82:		Line 81:
	$$		$$
	for any line-free subset $A \subset [2]^n$, where the \emph{cell} $\Gamma_{a_1,\ldots,a_k} \subset [k]^n$ is the set of words in $[k]^n$ which contain exactly $a_i$ $i$'s for each $i=1,\ldots,k$. It is natural to ask whether this inequality can be extended to higher $k$. Let $\Delta_{n,k}$ denote the set of all tuples $(a_1,\ldots,a_k)$ of non-negative integers summing to $n$, define a \emph{simplex} to be a set of $k$ points in $\Delta_{n,k}$ of the form		for any line-free subset $A \subset [2]^n$, where the \emph{cell} $\Gamma_{a_1,\ldots,a_k} \subset [k]^n$ is the set of words in $[k]^n$ which contain exactly $a_i$ $i$'s for each $i=1,\ldots,k$. It is natural to ask whether this inequality can be extended to higher $k$. Let $\Delta_{n,k}$ denote the set of all tuples $(a_1,\ldots,a_k)$ of non-negative integers summing to $n$, define a \emph{simplex} to be a set of $k$ points in $\Delta_{n,k}$ of the form
	$(a_1+r,a_2,\ldots,a_k), (a_1,a_2+r,\ldots,a_k),\ldots,(a_1,a_2,\ldots,a_k+r)$ for some $0 < r \leq n$ and $a_1,\ldots,a_k$ summing to $n-r$, and define a \emph{Fujimura set}\footnote{Fujimura actually proposed the related problem of finding the largest subset of $\Delta_{n,k}$ that contained no ~~all~~ equilateral triangles; see \cite{fuji}. Our results for Fujimura sets can be found at the page {\tt Fujimura's problem} at \cite{polywiki}.} to be a subset $B \subset \Delta_{n,k}$ which contains no simplices. Observe that if $w$ is a combinatorial line in $[k]^n$, then		$(a_1+r,a_2,\ldots,a_k), (a_1,a_2+r,\ldots,a_k),\ldots,(a_1,a_2,\ldots,a_k+r)$ for some $0 < r \leq n$ and $a_1,\ldots,a_k$ summing to $n-r$, and define a \emph{Fujimura set}\footnote{Fujimura actually proposed the related problem of finding the largest subset of $\Delta_{n,k}$ that contained no equilateral triangles; see \cite{fuji}. Our results for Fujimura sets can be found at the page {\tt Fujimura's problem} at \cite{polywiki}.} to be a subset $B \subset \Delta_{n,k}$ which contains no simplices. Observe that if $w$ is a combinatorial line in $[k]^n$, then
	$$ w(1) \in \Gamma_{a_1+r,a_2,\ldots,a_k}, w(2) \in \Gamma_{a_1,a_2+r,\ldots,a_k}, \ldots, w(k) = \Gamma_{a_1,a_2,\ldots,a_k+r}$$		$$ w(1) \in \Gamma_{a_1+r,a_2,\ldots,a_k}, w(2) \in \Gamma_{a_1,a_2+r,\ldots,a_k}, \ldots, w(k) = \Gamma_{a_1,a_2,\ldots,a_k+r}$$
	for some simplex $(a_1+r,a_2,\ldots,a_k), (a_1,a_2+r,\ldots,a_k),\ldots,(a_1,a_2,\ldots,a_k+r)$. Thus, if $B$ is a Fujimura set, then $A := \bigcup_{\vec a \in B} \Gamma_{\vec a}$ is line-free. Note also that		for some simplex $(a_1+r,a_2,\ldots,a_k), (a_1,a_2+r,\ldots,a_k),\ldots,(a_1,a_2,\ldots,a_k+r)$. Thus, if $B$ is a Fujimura set, then $A := \bigcup_{\vec a \in B} \Gamma_{\vec a}$ is line-free. Note also that