I have at my disposal the infinitary Hales-Jewett theorem. Denote by $\operatorname{Seq}(n)$ the set of all nonempty finite words generated by an $n$-letter alphabet.

If $\operatorname{Seq}(n)$ is finitely partitioned into $k$ parts, then for some $i \in \{1, \ldots, k\}$ part $i$ contains a combinatorial line.

I want to deduce the following finitary version of the theorem.

For any $n, k \in \mathbb{N}$ there exists $N \in \mathbb{N}$ such that for any $d > N$, if $n^d$ is partitioned into $k$ parts, then at least one of the parts contains a combinatorial line.

I'm approaching this by contradiction. Hence for any $N \in \mathbb{N}$, there is some $d > N$ such that $\{1,\ldots,n\}^d$ can be partitioned into $k$ parts but none of the parts contain a combinatorial line. Hence, for each $N \in \mathbb{N}$, we have some $d_N$ so that $\{1,\ldots,n\}^d$ can be made into a "bad partition".

I'm unsure how to proceed exactly. I think the idea is to extend the bad partition of $\{1, \ldots, n\}^d$ to a partition of $\operatorname{Seq}(n)$, but doing so is not obvious. I can of course extend every word in every part "upwards" by considering all its extensions, but this only gets me halfway to a partition of $\operatorname{Seq}(n)$; I also need to extend downwards. Doing so is tricky because words coming from different parts of the bad partition might have common prefixes. Instead, I thought perhaps I can bin all the words of length less than $d$ into a new part to form a partition of $\operatorname{Seq}(n)$. But then if I apply the infinitary Hales-Jewett, it could be that the combinatorial line is in this new part, and I'm unsure how to handle that. In fact, even if the combinatorial line that the infinitary Hales-Jewett theorem gives me is in one of the parts corresponding to a piece of the original bad partition, it's unclear to me how exactly I can use it to obtain a combinatorial line.

We saw this material in the context of ultrafilters (we used nonprincipal ultrafilters in the Stone-Cech compactification of $\operatorname{Seq}(n)$ to prove the infinitary Hales-Jewett theorem) so I believe I should use an argument involving an ultrafilter.


First, to prove that there exists some $N$ such that $n^N$ can be finitely partitioned into $m$ pieces in any way and have a combinatorial line in one of the pieces, suppose to the contrary that there is no such $N$. Then for every $N$ we have a bad partition into $m$ pieces, such that no piece contains a combinatorial line. For each stage $N$, enumerate the pieces of the bad partition by $P_{i,N}$ for $i \in [m]$. Define the family of sets $$ P_i = \bigcup_{j < \omega} P_{i,j} $$ for every $i \in [m]$. Note that this family of sets is a partition of $\operatorname{Seq}(n)$. By the infinitary Hales-Jewett theorem, there exists a piece, say $P_i$, in this partition that contains a combinatorial line, say $L$ generated by the variable word $w$ of length $l$. But then this combinatorial line is contained in $P_{i,l}$, which contradicts that the family of $P_{j,l}$ over $j < \omega$ is a bad partition.

Hence, no matter how $n^N$ is finitely partitioned into $m$ pieces, one of the pieces contains a combinatorial line.

Now we want to show that for any $d \geq N$, $n^d$ can be finitely partitioned in any way and have a piece with a combinatorial line.

We proceed by induction on $d$. The base case $d = N$ is covered by the above argument. Now for the step case suppose that $n^{d+1}$ is partitioned into $m$ pieces. We want to find a combinatorial line in one of the pieces. This induces a partition on the set of all words in $n^{d+1}$ that end in 1, which we can identify with words in $n^d$. Hence, this induces a partition on $n^d$, which by the induction hypothesis can be finitely partitioned in any way and have a piece with a combinatorial line, say $L$ generated by the variable word $w$ of length $d$. We can extend $w$ to $w^\prime \in n^{d+1}$ by appending the letter $1$. But then this generates a combinatorial line in the partition piece of $n^{d+1}$ corresponding to piece $i$ in $n^d$. Hence one of the pieces of $n^{d+1}$ contains a combinatorial line.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.