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.
H(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.
Improved bounds on HJ(4,r)
H(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.
H(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.
H(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.
H(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.
H(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)
H(5,2) is greater than 59
We color the slices of the 59 dimensional hypercube of side four 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 (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 four 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 (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 four 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 four 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 four 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)
H(6,2) is greater than 226
We color the slices of the 226 dimensional hypercube of side five 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 (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.
H(6,3) is greater than 1777
We color the slices of the 1777 dimensional hypercube of side five 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.
H(6,4) is greater than 18061
We color the slices of the 18061 dimensional hypercube of side five 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.
H(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.
H(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)
H(7,2) is greater than 617
We color the slices of the 617 dimensional hypercube of side six 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(6,2) is greater 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 (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 six but we have forbidden such a progression by our choice of coloring so we are done.
Improved bounds on HJ(n,r)
H(n,r) is greater than ((n^r/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 ((n^r/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 ((n^r/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. We can use this result to get a lower bound for c_n:
c_n is is greater than 3^n/(logn-log (log n) -log 3e(1+(o)1))
We have HJ(3,r) is greater than ((3^r/er3(1+o(1)))/2) -2 so we c_n greater than 3^n/r for n is less than ((3^r/er3(1+o(1)))/2) -2 and we get c_n is is greater than 3^n/(logn-log (log n) -log 3e(1+(o)1)) similarly we get in general the maximal number of points in a combinatorial line free cube of side m and dimension n is m^n/(logn-log (log n) -log (me(1+o1))
