Higherk.tex

A mixed bag here: relations between Moser and DHJ, failure of HOC, numerical results, small n results. Please edit at

\section{Higher-dimensional DHJ numbers} For any $n$, $k$ let $c_{n,k}$ denote the cardinality of the largest subset of $[k]{}^n$ that does not contain a combinatorial line. When $k=3$, the quantity $c_{n,k} = c_n$ is studied for instance in section \ref{???}. The density Hales-Jewett theorem asserts that for any fixed $k$, $\lim_{n\rightarrow\infty} c_n/k^n = 0$ . We trivially have $c_{n,1} = 0$ for $n > 0$, and Sperner's theorem tells us that $$c_{n,2} = \binom{n}{\floor{n/2}}$$. Now we look at the opposite regime, in which $n$ is small and $k$ is large. We easily have $c_{1,k} = k-1$ together with the trivial bound $c_{n+1,k} \leq kc_{n,k}$. This implies that $$c_{n,k}\leq (k-1)k^{n-1}$$ for any $n\geq 1$. Let us call a pair $(n,k)$ with $n > 0$ \emph{saturated} if $c_{n,k}=(k-1)k^{n-1}$, thus there exists a line-free set with exactly one point omitted from every row and column. The question naturally arises, Which pairs $(n,k)$ are saturated? From the above discussion we see that $(1,k)$ is saturated for all $k \geq 1$, and $(n,1)$ is (rather trivially) saturated for all $n$. Sperner's theorem tells us that $(n,2)$ is saturated only for $n= 1, 2$. Note that if $(n,k)$ is unsaturated then $(n',k)$ will be unsaturated for all $n' > n$. A computer search has found the following $c_{n,k}$ values for different values of dimension $n$ and edgelength $k$. Several of these values reach the upper bound of $(k − 1)k^{n-1}$. \begin{table} n\k & 2& 3 & 4 & 5 & 6 & 7 \\ 2 & 2 & 6 & 12 & 20 & 30 & 42\\ 3 & 3 & 18 & 48 & 100 & 180 & 294\\ 4 & 6 & 52 & 183 & 500 & 1051-1079 & 2058\\ 5 & 10 & 150 & 712-732 & 2500 & 6325-6480 & 14406 \end{table}

$(2,k)$ is saturated when $k$ is at least $1$. In dimension two the maximal set size is $k(k-1)$. This can be done by removing the diagonal values $11, 22, 33, …, kk$. Since they are in disjoint lines this removal is minimal. The $k$ missing points are one per line and one per column. So their $y$-coordinates are a shuffle of their $x$-coordinates. There are $k!$ rearrangements of the numbers $1$ to $k$. The $k$ points include a point on the diagonal, so this shuffle is not a derangement. There are $k!/e$ derangements of the numbers $1$ to $k$, so $k!(1-1/e)$ optimal solutions. This number of optimal solutions is sequence A002467 from the Online Encyclopedia of Integer Sequences.

$(3,k)$ is saturated when $k>2$. Let $S$ be a latin square of side $k$ on the symbols $1…k$, with colour $i$ in position $(i,i)$ (This is not possible for $k=2$) Let axis one in $S$ correspond to coordinate $1$ in $[k]{}^3$, axis two to coordinate $2$ and interpret the colour in position $(i,j)$ as the third coordinate. Delete the points so defined. The line with three wild cards has now been removed. A line with two wildcards will be missing the point corresponding to the diagonal in $S$. A line with a single wildcard will be missing a point corresponding to an off diagonal point in $S$.

\subsection{$(n,k)$ is saturated when all prime divisors of $k$ are at least $n$} First consider the case when $k$ is prime and at least $n$: Delete those points whose coordinates add up to a multiple of $k$. Every combinatorial line has one point deleted, except for the major diagonal of $n=k$, which has all points deleted. Now consider for instance the case $(n,k) = (4,35)$. Select one value modulo $35$ and eliminate it. Combinatorial lines with one, two, three or four moving coordinates will realize all values modulo $35$ as one, two, three, or four are units modulo $35$, thus $(4,35)$ is saturated. The same argument tells us that $(n,k)$ is saturated when all prime divisors of $k$ are at least $n$. On the other hand, computer data shows that $(4,4)$ and $(4,6)$ are not saturated.

http://michaelnielsen.org/polymath1/index.php?title=Higherk.tex