Coloring Hales-Jewett theorem

Introduction

The Hales-Jewett theorem states that for every k and every r there exists an n such that if you colour the elements of [math]\displaystyle{ [k]^n }[/math] with r colours, then there must be a combinatorial line with all its points of the same colour.

This is a consequence of the Density Hales-Jewett theorem, since there must be a set of density at least [math]\displaystyle{ r^{-1} }[/math] of elements of [math]\displaystyle{ [k]^n }[/math] all of whose elements have the same colour. It also follows from the Graham-Rothschild theorem.

By iterating the Hales-Jewett theorem, one can also show that one of the color classes contains an m-dimensional combinatorial subspace, if n is sufficiently large depending on k, r and m.

There are two combinatorial proofs of the Hales-Jewett theorem: the original one by Hales and Jewett, and a second proof by Shelah. They are given below.

There is an infinitary generalisation of this theorem known as the Carlson-Simpson theorem.

Here is the Wikipedia entry on this theorem.

For a fixed r and k, the least n needed for the Hales-Jewett theorem to apply is denoted HJ(k,r). The following bounds are known (see this paper):

[math]\displaystyle{ HJ(3,1) = 1 }[/math]

[math]\displaystyle{ HJ(3,2) = 4 }[/math]

[math]\displaystyle{ HJ(3,3) \gt 6 }[/math]

The original proof of the Hales-Jewett theorem

The first proof of the Hales-Jewett theorem was an abstraction of the argument used to prove van der Waerden's theorem. It goes like this. As above, let us write HJ(k,r) for the smallest n such that for every r-colouring of [math]\displaystyle{ [k]^n }[/math] there is a monochromatic combinatorial line. We shall attempt to bound HJ(k,r) in terms of the function [math]\displaystyle{ s\mapsto HJ(k-1,s), }[/math] which we may assume by induction to take finite values for every s.

Let [math]\displaystyle{ t_1,t_2,\dots,t_r }[/math] be a rapidly increasing sequence of integers, to be chosen later, let [math]\displaystyle{ n=t_1+\dots+t_r }[/math] and consider an r-colouring of [math]\displaystyle{ [k]^n=[k]^{t_1}\times\dots\times[k]^{t_r}. }[/math] Now define an induced [math]\displaystyle{ k^{n-t_r} }[/math]-colouring on [math]\displaystyle{ [k]^{t_r} }[/math] by colouring each x according to the function that takes [math]\displaystyle{ w\in[k]^{n-t_r} }[/math] to the colour of [math]\displaystyle{ (w,x). }[/math] By induction, we can find a monochromatic combinatorial line [math]\displaystyle{ L_r }[/math] in [math]\displaystyle{ [k]^{t_r} }[/math] such that all the points in that line have the same (induced) colour, with the possible exception of the point where the value of the variable coordinates is k. For this we need [math]\displaystyle{ t_r\geq HJ(k-1,k^{n-t_r}). }[/math]

Now pass to the subspace [math]\displaystyle{ [k]^{n-t_r}\times L_r, }[/math] and note that the only way a sequence in this space can depend on its final coordinate is through whether that final coordinate takes the value k or not. Inside this subspace, run precisely the same argument, but this time with [math]\displaystyle{ [k]^{t_{r-1}} }[/math] taking over the role of [math]\displaystyle{ [k]^{t_r}. }[/math] There is a choice here about what "precisely the same argument" means. It can either mean that we treat [math]\displaystyle{ [k]^{n-t_r}\times L_r }[/math] as [math]\displaystyle{ ([k]^{n-t_r-t_{r-1}}\times L_r)\times[k]^{t_{r-1}} }[/math] and talk about the original colouring, or it can mean that we restrict attention to the set [math]\displaystyle{ [k]^{n-t_r}=[k]^{t_1}\times\dots\times[k]^{t_{r-1}} }[/math] and talk about the colouring where the colour of w is the colour of (w,x) for the points [math]\displaystyle{ x\in L_r }[/math] with variable coordinate not equal to k. The usual argument goes via the second option, but for the sake of comparison with Shelah's proof it is nicer to go for the first (so what we are presenting here is not quite identical to the proof of Hales and Jewett).

After the second stage of the iteration, for which we require that [math]\displaystyle{ t_{r-1}\geq HJ(k-1,k^{n-t_r-t_{r-1}+1}), }[/math] we have a line [math]\displaystyle{ L_{r-1} }[/math] such that the colour of a point in [math]\displaystyle{ [k]^{t_1}\times\dots\times[k]^{t_{r-2}}\times L_{r-1}\times L_r }[/math] does not depend on which point you choose in [math]\displaystyle{ L_{r-1}\times L_r, }[/math] except if you change a non-k to a k or a k to a non-k.

Continuing this process, one ends up with a subspace [math]\displaystyle{ L_1\times\dots\times L_r }[/math] such that the colour of a point depends only on which of its coordinates are equal to k. This reduces the problem to HJ(2,r), which follows trivially from the pigeonhole principle. To spell it out, consider the points [math]\displaystyle{ (k-1,k-1,\dots,k-1), }[/math] [math]\displaystyle{ (k,k-1,k-1,\dots,k-1), }[/math] [math]\displaystyle{ (k,k,k-1,\dots,k-1),\dots(k,k,k,\dots,k). }[/math] There are r+1 of these points, so two of them have the same colour. Those two are the top two points of a combinatorial line, all the rest of which must have the same colour as well.

Shelah's proof of the Hales-Jewett theorem

This is very unfair to Shelah, but I am trying to present what he did as an almost trivial exercise in "turning an induction upside-down". The above proof used HJ(k-1) to create a subspace that we can treat as [math]\displaystyle{ [2]^r, }[/math] because the colouring in that subspace depends only on which coordinates are k and which are not k. Now let us try to use HJ(2) to create a subspace that we can treat as [math]\displaystyle{ [k-1]^m, }[/math] for some appropriate m, since in the subspace we shall ensure that the colouring is insensitive to changes between k-1 and k. To emphasize how easy this is, I shall paste the above paragraphs into this section and make the necessary adjustments.

Let [math]\displaystyle{ t_1,t_2,\dots,t_m }[/math] be a rapidly increasing sequence of integers, to be chosen later (including m), let [math]\displaystyle{ n=t_1+\dots+t_m }[/math] and consider an r-colouring of [math]\displaystyle{ [k]^n=[k]^{t_1}\times\dots\times[k]^{t_m}. }[/math] Now define an induced [math]\displaystyle{ k^{n-t_m} }[/math]-colouring on [math]\displaystyle{ [k]^{t_m} }[/math] by colouring each x according to the function that takes [math]\displaystyle{ w\in[k]^{n-t_m} }[/math] to the colour of [math]\displaystyle{ (w,x). }[/math] By HJ(2) (a trivial application of the pigeonhole principle, as we saw above), we can find a monochromatic combinatorial line [math]\displaystyle{ L_r }[/math] in [math]\displaystyle{ [k]^{t_m} }[/math] such that the first two points in that line have the same (induced) colour. For this we need [math]\displaystyle{ t_r\geq HJ(2,k^{n-t_m})=k^{n-t_m}. }[/math]

Now pass to the subspace [math]\displaystyle{ [k]^{n-t_m}\times L_m, }[/math] and note that if you change the final coordinate of a sequence in this space from a 1 to a 2, or vice versa, then it does not change the colour of the sequence. Inside this subspace, run precisely the same argument, but this time with [math]\displaystyle{ [k]^{t_{m-1}} }[/math] taking over the role of [math]\displaystyle{ [k]^{t_m} }[/math] and [math]\displaystyle{ L_m }[/math] taking over the role of [math]\displaystyle{ [k]^{t_{m-1}}. }[/math]

After the second stage of the iteration, for which we require that [math]\displaystyle{ t_{m-1}\geq HJ(2,k^{n-t_r-t_{m-1}+1})=k^{n-t_m-t_{m-1}}+1, }[/math] we have a line [math]\displaystyle{ L_{m-1} }[/math] such that the colour of a point in [math]\displaystyle{ [k]^{t_1}\times\dots\times[k]^{t_{m-2}}\times L_{m-1}\times L_m }[/math] does not change if you change any of the coordinates in [math]\displaystyle{ L_{m-1}\times L_m, }[/math] from a 1 to a 2 or vice versa.

Continuing this process, one ends up with a subspace [math]\displaystyle{ L_1\times\dots\times L_m }[/math] such that the colour of a point does not change if you change a coordinate from a 1 to a 2 or vice versa. This reduces the problem to HJ(k-1), so we can take m to be HJ(k-1,r) and we are done. To spell it out, consider the set of all points in [math]\displaystyle{ L_1\times\dots\times L_m }[/math] that have no variable coordinate equal to 1. Inside this set, we can find, by HJ(k-1,m), a combinatorial line such that all points in the line with variable coordinate not equal to 1 have the same colour. But by the way the subspace is chosen, we still have the same colour if we change the variable coordinate to a 1.

Improved bounds on HJ(3,3)

We can show that [math]\displaystyle{ HJ(3,3) \gt 7 }[/math] by exhibiting a 3-colouring of [math]\displaystyle{ [3]^7 }[/math] with no monochromatic lines.

We start with the set formed by removing (0,1,6), (1,0,6), (0,5,2), (5,0,2) , (1,5,1), (5,1,1),(1,6,0), (6,1,0) from D_7. Note that none of (0,1,6), (1,0,6), (0,5,2), (5,0,2) , (1,5,1), (5,1,1),(1,6,0), (6,1,0)contains a point whose coordinate sum is divisible by three we give it color 1 where (a,b,c) is shorthand for the slice Γ_a,b,c. It is combinatorial line free from the n=7 section of the upper and lower bounds wiki at http://michaelnielsen.org/polymath1/index.php?title=Upper_and_lower_bounds#n.3D7

then we divide the remaining points into all points whose coordinate sum is not equal to 0 mod 9 and all points of (0,1,6), (1,0,6), (0,5,2), (5,0,2) , (1,5,1), (5,1,1),(1,6,0), (6,1,0)whose coordinate sum is equal to 1 mod 3 We give these color 2

then we take all points of (0,1,6), (1,0,6), (0,5,2), (5,0,2) , (1,5,1), (5,1,1),(1,6,0), (6,1,0)whose coordinate sum equal to 2 mod 3 and those points whose sum is equal to 0 mod 9. We give these color 3.

Then with this coloring there are nor monochromatic lines. If there are any monochromatic Lines with number of moving coordinates not divisible by three in color 2 they must contain point whose coordinate sum is equal to 2 mod three But there are no such points with color 2. If there are any monochromatic lines whose coordinate sum is divisible by three Than they must contain points whose coordinate sum is 0 mod 9 but there are no such points with color 2. So there Are no monochromatic combinatorial lines with color 2.

If there are any monochromatic Lines with number of moving coordinates not divisible by three in color 3 they must contain point whose coordinate sum is equal to 1 mod three But there are no such points with color 3. If there are any monochromatic lines whose coordinate sum is divisible by three Than they must contain points whose coordinate sum is not 0 mod 9 but there are no such points with color 3.

As already noted color 1 is combinatorial line free and we are done.

Improved bounds on HJ(3,r)

HJ(3,3) is greater than 13

We take the slices of the thirteen dimensional hypercube of side three in the following way: We start with the Van der Warden number W(3,3) from Ramsey Theory By Ronald L. Graham, Bruce L. Rothschild, Joel H. Spencer second edition.

W(3,3)=27 which gives us a three coloring free of monochromatic progressions of length 3 of the numbers on through 27

We give the slice (a,b,c) the color associated with a + 2b +1 in the above coloring then the maximum value is 27 We add one because the coloring in W(3,3) starts with one and we have zero values in our slices.

Then we will not have a monochromatic combinatorial line because it would correspond to a monochromatic upward triangle and a monochromatic upward triangle would lead to an arithmetic progression of length three but we have forbidden such a progression by our choice of coloring so we are done. This is an improvement in the old value of HJ(3,3) is my value of 7 above before that there was a computer generated value of 6 in this paper http://www.math.ucsd.edu/~etressle/hj32.pdf.

HJ(3,4) is greater than 37

We color the slices of the 37 dimensional hypercube of side three in the following way: We start with the Van der Warden number W(3,4) from Ramsey Theory by Ronald L. Graham, Bruce L. Rothschild, Joel H. Spencer. We have an exact value: W(3,4) = 76 from Ramsey Theory by Ronald L. Graham, Bruce L. Rothschild, Joel H. Spencer. Which is associated with a four coloring of the numbers one through 76 which is free of monochromatic arithmetic progressions of length three.

We give the slice (a,b,c) the color associated with a + 2b + 1 in the above coloring then the maximum value is 75 so we can color each slice We add one because the coloring in W(3,4) starts with one and we have zero values in our slices. Then we will not have a monochromatic combinatorial line because it would correspond to a monochromatic upward triangle and a monochromatic upward triangle would lead to an arithmetic progression of length three but we have forbidden such a progression by our choice of coloring so we are done.

HJ(3,5) is greater than 84

We have from http://www.st.ewi.tudelft.nl/sat/waerden.php W(3,5) is greater than 170 which is associated with a five coloring of the points from 1 to 170 free of arithmetic progressions of lenght three from this we get a coloring of slices by giving the slice (a,b,c) the color in the above coloring associated with a+2b+1 then we will not have a monochromatic combinatorial line because it would correspond to a monochromatic upward triangle which would lead to an arithmetic progression of length three but we have forbidden such a progression by our choice of coloring so we are done. This leads to improvements in the existing bounds for c_n in the spreadsheet for values 82-84 as the density must be greater than 1/r=1/5 for n less than or equal to 84.

HJ(3,6) is greater than 103

We have from http://www.st.ewi.tudelft.nl/sat/waerden.php W(3,6) is greater than 207 which is associated with a six coloring of the points from 1 to 207 free of arithmetic progressions of length. three from this we get a coloring of slices by giving the slice (a,b,c) the color in the above coloring associated with a+2b+1 then we will not have a monochromatic combinatorial line because it would correspond to a monochromatic upward triangle which would lead to an arithmetic progression of length three but we have forbidden such a progression by our choice of coloring so we are done. Again this leads to improvements in the existing bounds for c_n for 82 to 98 again as the density must be greater than 1/r=1/6 for n less than or equal to 103 and the table stops at 98.

HJ(3,r) is greater than r^{clnr}/2-1

We have from from Ramsey Theory by Ronald L. Graham, Bruce L. Rothschild, Joel H. Spencer,second edition page 103. W(3,r) is greater than r^{clnr} which is associated with a t coloring of the points from 1 to r^{clnr} free of arithmetic progressions of length. three from this we get a coloring of slices by giving the slice (a,b,c) the color in the above coloring associated with a+2b+1 then we will not have a monochromatic combinatorial line because it would correspond to a monochromatic upward triangle which would lead to an arithmetic progression of length three but we have forbidden such a progression by our choice of coloring so we are done.

Improved bounds on HJ(4,r)

HJ(4,2) is greater than 11

We start with the Van der Warden number W(4,2) from Ramsey Theory by Ronald L. Graham, Bruce L. Rothschild, Joel H. Spencer for which we have an exact value: W(4,2)=35 with this is associated a two coloring of the numbers one through 35 with no monochromatic progression of length four.

We give the slices (a,b,c,d) of the 11th dimensional hypercube of side 4 the color associated with a + 2b + 3c + 1 then the maximum value is 34 so our coloring is well defined. We add one because the coloring in W(4,2) starts with one and we have zero values in our slices. Then we will not have a monochromatic combinatorial line because we will have no monochromatic upward tetrahedrons because they would lead to an arithmetic progression of length four which we have forbidden in our choice of coloring.

HJ(4,3) is greater than 97

We start with W(4,3) is greater than 292 from http://www.st.ewi.tudelft.nl/sat/waerden.php We let the dimension be 97 then give the slices the color associated with a+2b+3c+1 in the three coloring of 292 which has no monochromatic arithmetic progression of length four. Then since a monochromatic combinatorial line would lead to a monochromatic upward tetrahedron which would lead to an arithmetic progression of length four which we have forbidden we are done.

HJ(4,4) is greater than 349

We start with W(4,4) is greater than 1048 from http://www.st.ewi.tudelft.nl/sat/waerden.php We let the dimension be 349 then give the slices the color associated with a+2b+3c+1 in the three coloring of 1048 which has no monochromatic arithmetic progression of length four. Then since a monochromatic combinatorial line would lead to a monochromatic upward tetrahedron which would lead to an arithmetic progression of length four which we have forbidden we are done.

HJ(4,5) is greater than 751

We start with W(4,5) is greater than 2254 from http://www.st.ewi.tudelft.nl/sat/waerden.php We let the dimension be 751 then give the slices the color associated with a+2b+3c+1 in the three coloring of 2254 which has no monochromatic arithmetic progression of length four. Then since a monochromatic combinatorial line would lead to a monochromatic upward tetrahedron which would lead to an arithmetic progression which we have forbidden we are done.

HJ(4,6) is greater than 3259

We start with W(4,6) is greater than 9778 from http://www.st.ewi.tudelft.nl/sat/waerden.php We let the dimension be 3259 then give the slices the color associated with a+2b+3c+1 in the three coloring of 9778 which has no monochromatic arithmetic progression of length four. Then since a monochromatic combinatorial line would lead to a monochromatic upward tetrahedron which would lead to an arithmetic progression which we have forbidden we are done.

Improved bounds on HJ(5,r)

HJ(5,2) is greater than 59

We color the slices of the 59 dimensional hypercube of side five in the following way: We start with the Van der Warden number W(5,2) for which we have an exact value: W(5,2) =178 from Ramsey Theory by Ronald L. Graham, Bruce L. Rothschild, Joel H. Spencer this is associated with a two coloring of the numbers from 1 to 178 with no arithmetic progression of length 5 We give the slice (a,b,c,d,e) the color associated with a + 2b + 3c+4d+1 then the maximum value is 178 so the coloring is well defined. We add one because the coloring in W(5,2) starts with one and we have zero values in our slices. Then we will not have a monochromatic combinatorial line because it would correspond to a monochromatic upward simplex of dimension four whose vertices are (a+r,b,c,d,e), (a,b+r,c,d,e) etc. and a monochromatic upward simplex of dimension four would lead to an arithmetic progression of length five but we have forbidden such a progression by our choice of coloring so we are done.

HJ(5,3) is greater than 302

We color the slices of the 302 dimensional hypercube of side five in the following way: We start with the Van der Warden number W(5,3) for which we have W(5,3) is greater than 1209 see http://www.st.ewi.tudelft.nl/sat/waerden.php associated with a two coloring of the numbers from 1 to 1209 with no arithmetic progression of length 5 We give the slice (a,b,c,d,e) the color associated with a + 2b + 3c + 4d + 1 then the maximum value is 1209 so the coloring is well defined. We add one because the coloring in W(5,3) starts with one and we have zero values in our slices. Then we will not have a monochromatic combinatorial line because it would correspond to a monochromatic upward simplex of dimension four whose vertices are (a+r,b,c,d,e), (a,b+r,c,d,e) etc. and a monochromatic upward simplex of dimension four would lead to an arithmetic progression of length five but we have forbidden such a progression by our choice of coloring so we are done.

HJ(5,4) is greater than 2609

We color the slices of the 2609 dimensional hypercube of side five in the following way: We start with the Van der Warden number W(5,4) for which we have W(5,4) is greater than 10437 see http://www.st.ewi.tudelft.nl/sat/waerden.php associated with a three coloring of the numbers from 1 to 1209 with no arithmetic progression of length 5 We give the slice (a,b,c,d,e) the color associated with a + 2b + 3c + 4d + 1 then the maximum value is 2609 so the coloring is well defined. Then we will not have a monochromatic combinatorial line because it would correspond to a monochromatic upward simplex of dimension four and a monochromatic upward simplex of dimension four would lead to an arithmetic progression of length five but we have forbidden such a progression by our choice of coloring so we are done.

HJ(5,5) is greater than 6011

We color the slices of the 6011 dimensional hypercube of side five in the following way: We start with the Van der Warden number W(5,5) for which we have W(5,5) is greater than 24045 see http://www.st.ewi.tudelft.nl/sat/waerden.php associated with a three coloring of the numbers from 1 to 24045 with no arithmetic progression of length 5 We give the slice (a,b,c,d,e) the color associated with a + 2b + 3c + 4d + 1 Then we will not have a monochromatic combinatorial line because it would correspond to a monochromatic upward simplex of dimension four and a monochromatic upward simplex of dimension four would lead to an arithmetic progression of length five but we have forbidden such a progression by our choice of coloring so we are done.

HJ(5,6) is greater than 14173

We color the slices of the 14173 dimensional hypercube of side five in the following way: We start with the Van der Warden number W(5,6) for which we have W(5,6) is greater than 56693 see http://www.st.ewi.tudelft.nl/sat/waerden.php associated with a three coloring of the numbers from 1 to 56693 with no arithmetic progression of length 5 We give the slice (a,b,c,d,e) the color associated with a + 2b + 3c + 4d + 1 Then we will not have a monochromatic combinatorial line because it would correspond to a monochromatic upward simplex of dimension four and a monochromatic upward simplex of dimension four would lead to an arithmetic progression of length five but we have forbidden such a progression by our choice of coloring so we are done.

Improved bounds on HJ(6,r)

HJ(6,2) is greater than 226

We color the slices of the 226 dimensional hypercube of side six in the following way: We start with the Van der Warden number W(6,2) for which we have an exact value from http://www.st.ewi.tudelft.nl/sat/waerden.php: W(6,2) =1131 this is associated with a two coloring of the numbers from 1 to 1131 with no arithmetic progression of length 6.

We give the slice (a,b,c,d,e,f) the color associated with a + 2b + 3c + 4d +5e + 1 then the maximum value is 1131 so the coloring is well defined. We add one because the coloring in W(6,2) starts with one and we have zero values in our slices.

Then we will not have a monochromatic combinatorial line because it would correspond to a monochromatic upward simplex of dimension five whose vertices are (a+r,b,c,d,e,f), (a,b+r,c,d,e,f) etc. and a monochromatic upward simplex of dimension five would lead to an arithmetic progression of length six but we have forbidden such a progression by our choice of coloring so we are done.

HJ(6,3) is greater than 1777

We color the slices of the 1777 dimensional hypercube of side six in the following way: We start with the Van der Warden number W(6,3) for which we have from http://www.st.ewi.tudelft.nl/sat/waerden.php: W(6,3) is greater than 8886 this is associated with a three coloring of the numbers from 1 to 8886 with no arithmetic progression of length 6.

We give the slice (a,b,c,d,e,f) the color associated with a + 2b + 3c + 4d +5e + 1.

Then we will not have a monochromatic combinatorial line because it would correspond to a monochromatic upward simplex of dimension five and a monochromatic upward simplex of dimension five would lead to an arithmetic progression of length six but we have forbidden such a progression by our choice of coloring so we are done.

HJ(6,4) is greater than 18061

We color the slices of the 18061 dimensional hypercube of side six in the following way: We start with the Van der Warden number W(6,3) for which we have from http://www.st.ewi.tudelft.nl/sat/waerden.php: W(6,3)is greater than 90306.

We give the slice (a,b,c,d,e,f) the color associated with a + 2b + 3c + 4d +5e + 1.

Then we will not have a monochromatic combinatorial line because it would correspond to a monochromatic upward simplex of dimension five and a monochromatic upward simplex of dimension five would lead to an arithmetic progression of length six but we have forbidden such a progression by our choice of coloring so we are done.

HJ(6,5) is greater than 49391

We start with the Van der Warden number W(6,5) for which we have from http://www.st.ewi.tudelft.nl/sat/waerden.php: W(6,5)is greater than 246956.

We give the slice (a,b,c,d,e,f) the color associated with a + 2b + 3c + 4d +5e + 1.

Then we will not have a monochromatic combinatorial line because it would correspond to a monochromatic upward simplex of dimension five and a monochromatic upward simplex of dimension five would lead to an arithmetic progression of length six but we have forbidden such a progression by our choice of coloring so we are done.

HJ(6,6) is greater than 120097

We start with the Van der Warden number W(6,6) for which we have from http://www.st.ewi.tudelft.nl/sat/waerden.php: W(6,6)is greater than 600486.

We give the slice (a,b,c,d,e,f) the color associated with a + 2b + 3c + 4d +5e + 1.

Then we will not have a monochromatic combinatorial line because it would correspond to a monochromatic upward simplex of dimension five and a monochromatic upward simplex of dimension five would lead to an arithmetic progression of length six but we have forbidden such a progression by our choice of coloring so we are done.

Improved bounds on HJ(7,r)

HJ(7,2) is greater than 617

We color the slices of the 617 dimensional hypercube of side seven in the following way: We start with the Van der Warden number W(7,2) for which we have from http://www.st.ewi.tudelft.nl/sat/waerden.php: W(7,2)is greater than 3703 this is associated with a two coloring of the numbers from 1 to 3703 with no arithmetic progression of length 7.

We give the slice (a,b,c,d,e,f,g) the color associated with a + 2b + 3c + 4d +5e + 6f+ 1 then the maximum value is 3703 so the coloring is well defined. We add one because the coloring in W(7,2) starts with one and we have zero values in our slices.

Then we will not have a monochromatic combinatorial line because it would correspond to a monochromatic upward simplex of dimension six whose vertices are (a+r,b,c,d,e,f,g), (a,b+r,c,d,e,f,g) etc. and a monochromatic upward simplex of dimension six would lead to an arithmetic progression of length seven but we have forbidden such a progression by our choice of coloring so we are done.

HJ(7,3) is greater than 7309

We start with the Van der Warden number W(7,3) for which we have from http://www.st.ewi.tudelft.nl/sat/waerden.php: W(7,3) is greater than 43855 this is associated with a two coloring of the numbers from 1 to 43855 with no arithmetic progression of length 7.

We give the slice (a,b,c,d,e,f,g) the color associated with a + 2b + 3c + 4d +5e + 6f+ 1.

Then we will not have a monochromatic combinatorial line because it would correspond to a monochromatic upward simplex of dimension six (a+r,b,c,d,e,f,g) (a,b+r,c,d,e,f,g) etc. and a monochromatic upward simplex of dimension six would lead to an arithmetic progression of length seven but we have forbidden such a progression by our choice of coloring so we are done.

HJ(7,4) is greater than 64661

We start with the Van der Warden number W(7,4) for which we have from http://www.st.ewi.tudelft.nl/sat/waerden.php: W(7,4) is greater than 387967 this is associated with a two coloring of the numbers from 1 to 43855 with no arithmetic progression of length 7.

We give the slice (a,b,c,d,e,f,g) the color associated with a + 2b + 3c + 4d +5e + 6f+ 1.

Then we will not have a monochromatic combinatorial line because it would correspond to a monochromatic upward simplex of dimension six (a+r,b,c,d,e,f,g) (a,b+r,c,d,e,f,g) etc. and a monochromatic upward simplex of dimension six would lead to an arithmetic progression of length seven but we have forbidden such a progression by our choice of coloring so we are done.

Improved bounds on HJ(8,r)

HJ(8,2) is greater than 1069

We color the slices of the 1069 dimensional hypercube of side eight in the following way: We start with the Van der Warden number W(8,2) for which we have from http://www.st.ewi.tudelft.nl/sat/waerden.php: W(8,2) is greater than 7484 this is associated with a two coloring of the numbers from 1 to 7484 with no arithmetic progression of length 8.

We give the slice (a,b,c,d,e,f,g,h) the color associated with a + 2b + 3c + 4d +5e + 6f + 7g + 1. We add one because the coloring in W(8,2) starts with one and we have zero values in our slices.

Then we will not have a monochromatic combinatorial line because it would correspond to a monochromatic upward simplex of dimension seven whose vertices are (a+r,b,c,d,e,f,g,h) (a,b+r,c,d,e,f,g,h) etc. and a monochromatic upward simplex of dimension seven would lead to an arithmetic progression of length eight but we have forbidden such a progression by our choice of coloring so we are done.

HJ(8,3) is greater than 34057

We color the slices of the 34057 dimensional hypercube of side eight in the following way: We start with the Van der Warden number W(8,3) for which we have from http://www.st.ewi.tudelft.nl/sat/waerden.php: W(8,3) is greater than 238400 this is associated with a three coloring of the numbers from 1 to 238400 with no arithmetic progression of length 8.

We give the slice (a,b,c,d,e,f,g,h) the color associated with a + 2b + 3c + 4d +5e + 6f + 7g + 1. We add one because the coloring in W(8,3) starts with one and we have zero values in our slices.

Then we will not have a monochromatic combinatorial line because it would correspond to a monochromatic upward simplex of dimension seven whose vertices are (a+r,b,c,d,e,f,g,h), (a,b+r,c,d,e,f,g,h) etc. and a monochromatic upward simplex of dimension seven would lead to an arithmetic progression of length eight but we have forbidden such a progression by our choice of coloring so we are done.

Improved bounds on HJ(9,r)

HJ(9,2) is greater than 3389

We color the slices of the 3389 dimensional hypercube of side 9 in the following way: We start with the Van der Warden number W(9,2) for which we have from http://www.st.ewi.tudelft.nl/sat/waerden.php: W(9,2) is greater than 27113 this is associated with a two coloring of the numbers from 1 to 27113 with no arithmetic progression of length 9.

We give the slice (a,b,c,d,e,f,g,h,i) the color associated with a + 2b + 3c + 4d +5e + 6f + 7g + 8h + 1. We add one because the coloring in W(9,2) starts with one and we have zero values in our slices.

Then we will not have a monochromatic combinatorial line because it would correspond to a monochromatic upward simplex of dimension eight whose vertices are (a+r,b,c,d,e,f,g,h.i), (a,b+r,c,d,e,f,g,h,i) etc. and a monochromatic upward simplex of dimension eight would lead to an arithmetic progression of length nine but we have forbidden such a progression by our choice of coloring so we are done.

Improved bounds on HJ(n,r)

HJ(n,r) is greater than ((r^n/ern(1+o(1)))/n-1) -2

We start with the bound W(n,r) is greater than r^n/erk(1+o(1)) which is from the website

http://mathworld.wolfram.com/vanderWaerdenNumber.html

which gives the reference Heule, M. J. H. “Improving the Odds: New Lower Bounds for Van der Waerden Numbers.” March 4, 2008. http://www.st.ewi.tudelft.nl/sat/slides/waerden.pdf.

Set the dimension equal to ((r^n/ern(1+o(1)))/n-1) -2

then we take that coloring and give it to give a point the color associated with a +2b+.. continued n-1 times we can do tbis because the dimension is ((r^n/ern(1+o(1)))/n-1) -2 There is no n-1 dimensional upward simplex as then we would have a monochromatic arithmetic progression which we have forbidden but since we have no monochromatic upward n-1 dimensional simplex we will have no combinatorial lines and so we are done.