Polymath Wiki - User contributions [en]

Higher-dimensional DHJ numbers

2009-07-06T21:06:09Z

85.11.27.57: Undo revision 1870 by 212.138.47.16 (Talk)

For any n, k let <math>c_{n,k}</math> denote the cardinality of the largest subset of <math>[k]^n</math> that does not contain a combinatorial line. When k=3, the quantity <math>c_{n,k} = c_n</math> is studied for instance in [[upper and lower bounds|this page]]. The [[DHJ|density Hales-Jewett theorem]] asserts that for any fixed k, <math>\lim_{n \to \infty} c_n / k^n = 0</math>.

A [http://abel.math.umu.se/~klasm/Data/HJ/ computer search] has found the following <math>c_n</math> values for different values of dimension n and edgelength k. Several of these values reach the upper bound of <math>(k-1)k^{n-1}</math>.

{| border=1 |
|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
|-
| 6 || 20 || 450 ||
|}

We trivially have
:<math>c_{n,1} = 0</math> for n > 0 (and <math>c_{0,0}=1</math>)
and [[Sperner's theorem]] tells us that
:<math>c_{n,2} = \binom{n}{\lfloor n/2\rfloor}</math>.

Now we look at the opposite regime, in which n is small and k is large. We easily have
:<math>c_{0,k} = 1</math>
and
:<math>c_{1,k} = k-1</math>;

together with the trivial bound
:<math>c_{n+1,k} \leq k c_{n,k}</math>

this implies that
:<math>c_{n,k} \leq (k-1) k^{n-1}</math>
for any <math>n \geq 1</math>. Let us call a pair (n,k) with n > 0 ''saturated'' if <math>c_{n,k} = (k-1) k^{n-1}</math>, thus there exists a line-free set with exactly one point omitted from every row and column.

'''Question''': Which pairs (n,k) are saturated?

From the above discussion we see that (1,k) is saturated for all k >= 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.

== (2,k) is saturated when k is at least 1 ==

It is simple to show when restricting to dimension two the maximal set size has to be 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

The number of optimal solutions is [http://www.research.att.com/~njas/sequences/A002467 this sequence].

== (3,k) is saturated when k is at least 3 ==

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.

Something similar should work in higher dimensions if one can find latin cubes etc with the right diagonal properties.

== (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.

== (4,k) ==

Divide the points into five types: xyzw, xxyz, xxyy, xxxy and xxxx. Let p(xyzw) be the number of points removed whose coordinates are all different, and so on.

There are seven types of line: *xyz, *xxy, *xxx, **xy, **xx, ***x, ****. Enough points must be removed to remove all lines. That leads to the following inequalities
* <math> 4p(xyzw)+2p(xxyz) \ge 4k(k-1)(k-2)</math>
* <math> 2p(xxyz)+4p(xxyy)+3p(xxxy) \ge 12k(k-1)</math>
* <math> p(xxxy)+4p(xxxx) \ge 4k </math>
* <math> p(xxyz)+3p(xxxy) \ge 6k(k-1) </math>
* <math> 2p(xxyy)+6p(xxxx) \ge 6k </math>
* <math> p(xxxx) \ge 1</math>

If (4,k) is saturated, then for some h between 0 and k-1 inclusive the k^3 missing points fall into the following types
* (k-1)(k-2)(k-3) - 6h of type xyzw
* 6(k-1)(k-2) + 12h of type xxyz
* 3(k-1) - 3h of type xxyy
* 4(k-1) - 4h of type xxxy
* 1 + h of type xxxx

As a result, the only combinatorial line with more than one deleted point is the major diagonal.

The saturated solutions described above for (n,k) have h=0, so the only xxxx point deleted is kkkk. When k is coprime to 6, the following saturated solution has all xxxx points deleted: the set of points (x,y,z,w) for which x+y+z+(k-3)w is a multiple of k.

== (5,k) ==

Any saturated coordinate-line-free solution of the five-dimensional k-cube, with <math>k^4</math> missing points, must have the following missing points of each type.

* p(vwxyz) = 24a + (k-1)(k-2)(k-3)(k-4)
* p(wwxyz) = -60a + 10(k-1)(k-2)(k-3)
* p(xxyyz) = 30a + 15(k-1)(k-2)
* p(xxxyz) = 20a + 10(k-1)(k-2)
* p(xxxyy) = -10a + 10(k-1)
* p(xxxxy) = -5a + 5(k-1)
* p(xxxxx) = a+1
* (a=0..k-1)

Again, the only combinatorial line with more than one missing point is the major diagonal. The number of missing points on the main diagonal (xxxxx) can be 1 or k, but then the number of each other type is fixed.

== General lower bounds ==

There are <math>k^{n-1}</math> disjoint lines *abcd..m, so the density of removed points must be at least 1/k, and retained points at most (k-1)/k.

If k is prime and k ≥ n, then one can remove all combinatorial lines by deleting all points whose coordinates sum to a multiple of k. So the density of deleted points in the optimal configuration is 1/k when k is prime.

The next two bounds rely on prime numbers close to k. The following paper shows there is a prime between <math>x-x^{0.525}</math> and x.

Baker, R. C.(1-BYU); Harman, G.(4-LNDHB); Pintz, J.(H-AOS)
The difference between consecutive primes. II.
Proc. London Math. Soc. (3) 83 (2001), no. 3, 532–562.

If n ≤ p ≤ k then one can get a density of (p-1)/p by deleting points whose coordinates sum to a multiple of p. The lower bound (p-1)/p approaches (k-1)/k as <math>k\rightarrow \infty</math>.

Let p be the smallest prime greater than or equal to both k and n. One can remove all combinatorial lines by deleting all points whose coordinates sum to 0 ≤ x ≤ p-k (mod p), So the density of deleted points is at most (p-k+1)/p. This approaches zero as <math>k\rightarrow\infty</math>.

I think these results can be used to get lower bounds on lines free sets for large n for all values of k. For any k and any n we can find a prime prelatively close to k^n then we remove the first k+1 values mod p then we pick a value then we remove the must k+1 so we only have k+2, 2k+3, etch
the idea is to prevent any two values on a line because two points on a combinatorial line increase by at most k. This has density 1/k so we have
a line free density of 1/(k+1).

I think the above bound could possibly be improved. First by getting most of the set concentrated around the point with equal numbers of ones twos and threes or the point with values closes to equality the standard deviation should be something like the square root of n. Then we could apply the near prime with sets c(k^.5 + 1) and get a density of roughly c/k^.5
which I think will be better than the Behrend-Elkin construction as e^-x will eventually be less than 1/x as x increases without limit and the square root of k will increase without limit.

Higher-dimensional DHJ numbers

2009-07-06T19:44:39Z

85.11.27.57: Undo revision 1867 by 200.238.83.49 (Talk)

Higher-dimensional DHJ numbers

2009-07-06T18:36:12Z

85.11.27.57: Undo revision 1862 by 114.127.246.36 (Talk)

Higher-dimensional DHJ numbers

2009-07-06T16:09:52Z

85.11.27.57: Undo revision 1856 by 201.251.92.116 (Talk)

Corners theorem

2009-07-06T16:09:25Z

85.11.27.57: Undo revision 1855 by 63.240.26.232 (Talk)

'''Corners theorem''': (<math>{\Bbb Z}/N{\Bbb Z}</math> version) If N is sufficiently large depending on <math>\delta</math>, then any <math>\delta</math>-dense subset of <math>{}[N]^2</math> must contain a "corner" (x,y), (x+r,y), (x,y+r) with <math>r > 0</math>.

'''Corners theorem''': (<math>({\Bbb Z}/3{\Bbb Z})^n</math> version) If n is sufficiently large depending on <math>\delta</math>, then any <math>\delta</math>-dense subset of <math>{}(({\Bbb Z}/3{\Bbb Z})^n)^2</math> must contain a "corner" (x,y), (x+r,y), (x,y+r) with <math>r \neq 0</math>.

This result was first proven by [[Ajtai-Szemerédi's proof of the corners theorem|Ajtai and Szemerédi]]. A simpler proof, based on the [[triangle removal lemma]], was obtained by Solymosi. The corners theorem implies [[Roth's theorem]] and is in turn implied by the [[IP-Szemerédi theorem]], which in turn follows from [[DHJ(3)]].

One consequence of the corners theorem is that any subset of the triangular grid

:<math>\Delta_n = \{ (a,b,c) \in {\Bbb Z}_+^3: a+b+c=n\}</math>

of density at least <math>\delta</math> will contain an equilateral triangle <math>(a+r,b,c),(a,b+r,c),(a,b,c+r)</math> with <math>r>0</math>, if n is sufficiently large depending on <math>\delta</math>.

A [[DHJ(1,3)|special case of the corners theorem]] is of interest in connection with [[DJH(1,3)]].

Higher-dimensional DHJ numbers

2009-07-06T08:57:09Z

85.11.27.57: Undo revision 1848 by 114.127.246.36 (Talk)

User:Rainjacket

2009-06-28T12:07:47Z

85.11.27.57: Removing all content from page

Coloring Hales-Jewett theorem

2009-06-27T17:48:05Z

85.11.27.57: Undo revision 1791 by 212.92.227.56 (Talk)

==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>[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>r^{-1}</math> of elements of <math>[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 [http://en.wikipedia.org/wiki/Hales%E2%80%93Jewett_theorem 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 [http://www.math.ucsd.edu/~etressle/hj32.pdf this paper]):

: <math>HJ(3,1) = 1</math>
: <math>HJ(3,2) = 4</math>
: <math>HJ(3,3) > 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>[k]^n</math> there is a monochromatic combinatorial line. We shall attempt to bound HJ(k,r) in terms of the function <math>s\mapsto HJ(k-1,s),</math> which we may assume by induction to take finite values for every s.

Let <math>t_1,t_2,\dots,t_r</math> be a rapidly increasing sequence of integers, to be chosen later, let <math>n=t_1+\dots+t_r</math> and consider an r-colouring of <math>[k]^n=[k]^{t_1}\times\dots\times[k]^{t_r}.</math> Now define an induced <math>k^{n-t_r}</math>-colouring on <math>[k]^{t_r}</math> by colouring each x according to the function that takes <math>w\in[k]^{n-t_r}</math> to the colour of <math>(w,x).</math> By induction, we can find a monochromatic combinatorial line <math>L_r</math> in <math>[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>t_r\geq HJ(k-1,k^{n-t_r}).</math>

Now pass to the subspace <math>[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>[k]^{t_{r-1}}</math> taking over the role of <math>[k]^{t_r}.</math> There is a choice here about what "precisely the same argument" means. It can either mean that we treat <math>[k]^{n-t_r}\times L_r</math> as <math>([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>[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>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>t_{r-1}\geq HJ(k-1,k^{n-t_r-t_{r-1}+1}),</math> we have a line <math>L_{r-1}</math> such that the colour of a point in <math>[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>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>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>(k-1,k-1,\dots,k-1),</math> <math>(k,k-1,k-1,\dots,k-1),</math> <math>(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>[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>[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>t_1,t_2,\dots,t_m</math> be a rapidly increasing sequence of integers, to be chosen later (including m), let <math>n=t_1+\dots+t_m</math> and consider an r-colouring of <math>[k]^n=[k]^{t_1}\times\dots\times[k]^{t_m}.</math> Now define an induced <math>k^{n-t_m}</math>-colouring on <math>[k]^{t_m}</math> by colouring each x according to the function that takes <math>w\in[k]^{n-t_m}</math> to the colour of <math>(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>L_r</math> in <math>[k]^{t_m}</math> such that the first two points in that line have the same (induced) colour. For this we need <math>t_r\geq HJ(2,k^{n-t_m})=k^{n-t_m}.</math>

Now pass to the subspace <math>[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>[k]^{t_{m-1}}</math> taking over the role of <math>[k]^{t_m}</math> and <math>L_m</math> taking over the role of <math>[k]^{t_{m-1}}.</math>

After the second stage of the iteration, for which we require that <math>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>L_{m-1}</math> such that the colour of a point in <math>[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>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>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>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>HJ(3,3) > 7</math> by exhibiting a 3-colouring of <math>[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.

Coloring Hales-Jewett theorem

2009-06-27T11:51:28Z

85.11.27.57: Undo revision 1789 by 212.92.227.56 (Talk)

Coloring Hales-Jewett theorem

2009-06-27T07:18:56Z

85.11.27.57: Undo revision 1784 by 212.92.227.56 (Talk)

Talk:Main Page

2009-06-21T18:35:34Z

85.11.27.57: Undo revision 1733 by 93.80.193.158 (Talk)

Metacomment: it would be cool to have a polymath logo to replace "set $wgLogo to the URL path...".

Coloring Hales-Jewett theorem

2009-06-20T12:13:49Z

85.11.27.57: Undo revision 1719 by 212.92.227.165 (Talk)

Talk:Corners theorem

2009-06-20T12:13:20Z

85.11.27.57: Undo revision 1720 by 194.8.75.145 (Talk)

Talk:Main Page

2009-06-17T21:40:00Z

85.11.27.57: Undo revision 1694 by 93.80.188.201 (Talk)

Metacomment: it would be cool to have a polymath logo to replace "set $wgLogo to the URL path...".

Coloring Hales-Jewett theorem

2009-06-09T20:53:43Z

85.11.27.57: Undo revision 1604 by 83.3.122.171 (Talk)

Talk:Main Page

2009-06-09T20:53:00Z

85.11.27.57: Undo revision 1605 by 89.178.120.134 (Talk)

Metacomment: it would be cool to have a polymath logo to replace "set $wgLogo to the URL path...".

Talk:Main Page

2009-06-07T16:18:58Z

85.11.27.57: Undo revision 1582 by 95.25.30.220 (Talk)

Metacomment: it would be cool to have a polymath logo to replace "set $wgLogo to the URL path...".

A general result about density increments

2009-06-04T16:37:21Z

85.11.27.57: Undo revision 1549 by 93.190.138.249 (Talk)

==Introduction==

The purpose of this page is to prove a general result about density-increment strategies. It is not logically necessary as part of the proof of DHJ(3) or DHJ(k), but it helps to explain why certain features of the proof are as they are.

==Terminology==

If A and B are two subsets of a finite set X, then we say that the ''density of'' A ''in'' B is <math>|A\cap B|/|B|.</math>

==Description of result==

Let us focus on the proof of DHJ(3), though what we say is much more general. That proof has two stages, which can be described as follows.

1. Prove that if <math>\mathcal{A}</math> is a subset of <math>[3]^n</math> of density <math>\delta</math> then there is a dense 12-subset <math>\mathcal{B}</math> of a subspace S of dimension tending to infinity, such that the density of <math>\mathcal{A}</math> in <math>\mathcal{B}</math> is at least <math>\delta+c(\delta),</math> where <math>c(\delta)>0.</math> (In fact, <math>c(\delta)</math> is proportional to <math>\delta^2.</math>)

2. Every 12-set can be almost entirely partitioned into m-dimensional subspaces, where m tends to infinity with n. Here, m depends only on the density of the part of the 12-set that is allowed not to be partitioned.

Once we have these two stages, we are basically done, for reasons that can be appreciated even if one does not know the definition of a 12-set. The reason is that if we partition all of a 12-set apart from a subset of measure at most <math>c(\delta)/2</math> into m-dimensional subspaces, then the density of <math>\mathcal{A}</math> in the partitioned part is at least <math>\delta+c(\delta)/2,</math> so by averaging <math>\mathcal{A}</math> has density at least <math>\delta+c(\delta)/2</math> in at least one of these subspaces. That gives us a density increment on a subspace, which is exactly what we need for a [[density-increment_strategies|density-increment strategy]].

Now let us generalize 2 very slightly. Given a finite set X, we define its ''characteristic measure'' <math>\xi</math> to be the function that takes the value <math>1/|X|</math> everywhere in X and 0 everywhere else. Given a set Y, we write <math>\xi(Y)</math> for <math>\sum_{y\in Y}\xi(y)=|X\cap Y|/|X|.</math> Let <math>\beta</math> be the characteristic measure of <math>\mathcal{B},</math> let <math>S_1,\dots,S_N</math> be a collection of subspaces, and for each i let <math>\sigma_i</math> be the characteristic measure of <math>S_i.</math> We are assuming that <math>\beta(\mathcal{A})\geq\delta+c(\delta).</math> If we can find a convex combination <math>\sum_{i=1}^N\lambda_i\sigma_i</math> such that <math>\|\sum_i\lambda_i\sigma_i-\beta\|\leq c(\delta)/2,</math> then <math>\sum_i\lambda_i\sigma_i(\mathcal{A})\geq\delta+c(\delta)/2.</math> It follows that there exists i such that <math>\sigma_i(\mathcal{A})\geq\delta+c(\delta)/2,</math> which is what we wanted.

The main result of this page is that a converse to this generalized step 2 is true as well. Loosely, this tells us that any proof that a density increase on a 12-set implies a density increase on a subspace must also show that a 12-set can be evenly covered with subspaces, up to a small error.

==The proof==

Suppose that we ''cannot'' find a convex combination <math>\sum_{i=1}^N\lambda_i\sigma_i</math> such that <math>\|\sum_i\lambda_i\sigma_i-\beta\|\leq c(\delta)/2.</math> Then the Hahn-Banach theorem provides us with a function F and non-negative reals <math>\lambda+\mu=1</math> such that <math>\mathbb{E}_{x\in\mathcal{B}}F(x)>1,</math> while <math>\|F\|_\infty\leq 2\lambda/c(\delta)</math> and <math>\sigma_i(F)=\mathbb{E}_{x\in S_i}F(x)\leq \mu</math> for every i. From this it follows that <math>\lambda>c(\delta)/2.</math>

Now let <math>G(x)=\delta(1+F(x)/\|F\|_\infty).</math> Then G takes values in <math>[0,2\delta],</math> and <math>\mathbb{E}_{x\in\mathcal{B}}G(x)>\delta(1+c(\delta)/2\lambda).</math> However, for each i we have <math>\sigma_i(G)\leq\delta(1+\mu/\|F\|_\infty)\leq\delta(1+c(\delta)^2\mu/2\lambda)</math><math></math><math></math><math></math><math></math><math></math><math></math><math></math>

Haven't quite finished this.

Obstructions to uniformity

2009-06-04T16:36:57Z

85.11.27.57: Undo revision 1548 by 93.190.138.249 (Talk)

Suppose that we have a definition of [[quasirandomness]] for subsets of some structure. As stated in the quasirandomness article, a definition of quasirandomness is not very useful unless one has some understanding of sets that are ''not'' quasirandom. Let S be a structure (such as a complete graph, <math>[3]^n,</math> a finite Abelian group, or <math>[n]^2</math>) and let A be a subset of S of density <math>\delta</math>. Let f be <math>1-\delta</math> on A and <math>-\delta</math> on the complement of A. Then the average of f is zero. Typically, one would like to show that if A, or equivalently f, is not quasirandom then there is some "structured subset" <math>S'\subset S</math> such that <math>\mathbb{E}_{x\in S'}f(x)\geq c</math> for some positive constant c that depends on <math>\delta</math> only. Better still, one would like a converse: that any function that has positive expectation on a substructure must fail to be quasirandom. If we can do this, then we say that we have a complete set of obstructions to uniformity. ("Uniformity" is sometimes used as a synonym for "quasirandomness".)

More generally, we can look not for structured sets but structured ''functions''. In this case we would like to find a set G of functions such that for every non-quasirandom function f there exists g in G such that <math>\mathbb{E}_{x\in S}f(x)g(x)\geq c,</math> and such that if there exists such a g then f is not quasirandom.

==Examples==

====Graphs====

If f is a non-quasirandom function defined on the edges of the complete graph <math>K_n,</math> then there are sets X and Y of vertices of linear size such that <math>\mathbb{E}_{(x,y)\in X\times Y}f(x,y)\geq c,</math> where c is a positive constant that depends on the degree of non-quasirandomness of f. Conversely, if such vertex sets exist, then f is not quasirandom.

====Functions defined on <math>\mathbb{Z}_N</math>====

If f is a non-quasirandom function defined on <math>\mathbb{Z}_N,</math> then there exists an integer r such that <math>\mathbb{E}_{x\in\Z_N}f(x)exp(2\pi irx/N)\geq c,</math> where again c is a positive constant that depends on the degree of non-quasirandomness of f. Again, the converse holds as well. Thus, in this case the trigonometric functions form a complete set of obstructions to quasirandomness.

==The relevance to the density Hales-Jewett theorem==

It is possible to think about obstructions to uniformity even in the absence of a precisely formulated definition of quasirandomness. For example, in the case of the density Hales-Jewett theorem, we know that we want quasirandom sets to contain roughly the expected number of combinatorial lines. Therefore, we can temporarily (and unsatisfactorily) ''define'' a quasirandom set to be one that contains roughly the expected number of combinatorial lines and try to classify "extreme examples" of sets that do not contain roughly the expected number. These extreme examples will typically be highly structured sets: for instance, the set of all sequences x such that <math>x_1=1</math> is easily shown to have more combinatorial lines than a random set of density 1/3, but it is also a highly structured subset of <math>[3]^n.</math> If these examples appear to belong to a limited number of types, we can then hypothesize that ''every'' set with the wrong number of combinatorial lines correlates with one of these extreme examples. It is these extreme examples that one calls obstructions to uniformity.

Once we have formulated a conjecture of this type, we would hope to prove it in two stages as follows.

*Every quasirandom set contains roughly as many combinatorial lines as a random set of the same density. Therefore, a set with the wrong number of combinatorial lines is not quasirandom.

*Every non-quasirandom set is noticeably correlated with an obstruction to uniformity.

==Possible candidates==

The obstructions to uniformity appear to be hard to describe if one uses the uniform measure on <math>[3]^n,</math> even if one localizes to a few slices. However, if one uses [[equal-slices measure]], then all known obstructions are sets of the following form. (The next couple of paragraphs are lifted from [http://michaelnielsen.org/polymath1/index.php?title=DHJ%283%29&section=4 the discussion of DHJ(1,3)].)

Let <math>\mathcal{U},\mathcal{V}</math> and <math>\mathcal{W}</math> be collections of subsets of <math>[n].</math> Define <math>\mathcal{A}(\mathcal{U},\mathcal{V},\mathcal{W})</math> to be the set of all triples <math>(U,V,W),</math> where <math>U,V,W</math> are disjoint, and <math>U\in\mathcal{U},V\in\mathcal{V},W\in\mathcal{W}.</math> These triples are in an obvious one-to-one correspondence with elements of <math>[3]^n.</math>

Call <math>\mathcal{A}</math> a ''set of complexity 1'' if it is of the form <math>\mathcal{A}(\mathcal{U},\mathcal{V},\mathcal{W})</math>. For instance, a [[slice]] <math>\Gamma_{a,b,c}</math> is of complexity 1, as is a union of slices of the form <math>\bigcup\{\Gamma_{a,b,c}:(a,b,c)\in A\times B\times C, a+b+c=n\}</math>

It is conceivable, though certainly not proved, that every set that does not contain roughly the expected number of combinatorial lines, given its density (where everything is with respect to equal-slices measure) correlates significantly with a set of complexity 1. In the opposite direction, sets of complexity 1 do give a large source of examples of sets with the wrong number of combinatorial lines.

Talk:Main Page

2009-06-01T15:54:20Z

85.11.27.57: Replacing page with 'Metacomment: it would be cool to have a polymath logo to replace "set $wgLogo to the URL path...".'

Metacomment: it would be cool to have a polymath logo to replace "set $wgLogo to the URL path...".

A general result about density increments

2009-05-31T15:31:00Z

85.11.27.57: Undo revision 1505 by 93.190.138.249 (Talk)

Talk:Main Page

2009-05-31T09:06:15Z

85.11.27.57:

Metacomment: it would be cool to have a polymath logo to replace "set $wgLogo to the URL path...".

Talk:Main Page

2009-05-09T20:06:55Z

85.11.27.57: Undo revision 1357 by 89.178.7.150 (Talk)

Metacomment: it would be cool to have a polymath logo to replace "set $wgLogo to the URL path...". [[User:Rainjacket|Rainjacket]]

Talk:Corners theorem

2009-05-08T22:19:12Z

85.11.27.57: Removing all content from page

Talk:Main Page

2009-05-08T22:17:28Z

85.11.27.57: Undo revision 1350 by 78.106.31.177 (Talk)

Metacomment: it would be cool to have a polymath logo to replace "set $wgLogo to the URL path...". [[User:Rainjacket|Rainjacket]]