Polymath Wiki - User contributions [en]

Talk:Main Page

2009-05-04T20:23:14Z

130.237.201.143: Undo revision 1348 by 78.106.205.141 (Talk)

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

Talk:Main Page

2009-05-03T16:39:57Z

130.237.201.143: Undo revision 1346 by 78.106.31.125 (Talk)

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

Talk:Main Page

2009-05-01T19:27:34Z

130.237.201.143: Undo revision 1332 by 93.80.109.76 (Talk)

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

Talk:Main Page

2009-05-01T06:52:11Z

130.237.201.143: Undo revision 1330 by 78.106.118.182 (Talk)

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

Ergodic-inspired methods

2009-04-30T06:08:44Z

130.237.201.143: Undo revision 1328 by 125.76.228.201 (Talk)

These methods are inspired by the [[Furstenberg-Katznelson argument]] and the [[ergodic perspective]].

== Idea #1: extreme localisation ==

Let <math>A \subset [3]^n</math> be line-free with density <math>\delta</math>.
Let <math>m = m(\delta)</math> be a medium size integer independent of n. We embed <math>[3]^m</math> inside <math>[3]^n</math>
to create a random set <math>A_m \subset [3]^m</math> which enjoys stationarity properties. We then look at the events
<math>E_{i,j}</math> for <math>1 \leq i \leq j \leq m</math>, which are the event that <math>1^i 0^{j-i} 2^{m-j}</math> lies in <math>A_m</math>. As A is line-free, we observe that <math>E_{i,i}, E_{i,j}, E_{j,j}</math> cannot simultaneously occur for any <math>1 \leq i < j \leq m</math>. Also, each of the <math>E_{i,j}</math> have probability about <math>\delta</math>.

On the other hand, by the first moment method, many of the <math>E_{i,i}</math> hold with positive probability. Some Cauchy-Schwarz then tells us that there exists <math>1 \leq i < i' < j < j' \leq n</math> such that <math>E_{i,j} \wedge E_{i',j} \wedge E_{i,j'} \wedge E_{i',j'}</math> has probability significantly larger than <math>\delta^4</math>.

One can view the events <math>E_{i,j}</math> as an i+m-j-uniform hypergraph, by fixing a base point x and viewing the random subspace <math>[3]^m</math> as formed by modifying x on m random indices. The above correlation would mean some significant irregularity in this hypergraph; the hope is that this implies some sort of usable structure on A that can be used, for instance to locate a density increment.

== Idea #2: IP Roth first ==

'''McCutcheon.508''' (revised 2-17): I will give my general idea for a proof. I’m pretty sure it’s sound, though it may not be feasible in practice. On the other hand I may be badly mistaken about something. I will throw it out there for someone else to attempt, or say why it’s nonsense, or perhaps ignore. I won’t formulate it as a strategy to prove DHJ, but of what I’ve called IP Roth. If successful, one could possibly adapt it to the DHJ, k=3 situation, but there would be complications that would obscure what was going on.

We work in <math>X=[n]^{[n]}\times [n]^{[n]}.</math> For a real valued function <math>f</math> defined on <math>X</math>, define <math>||f||_1=(\mathrm{IP-lim}_a\mathrm{IP-lim}_b {1\over |X|}\sum_{(x,y)\in X} f((x,y))f((x+a,y))f((x+b,y-b))f((x+a+b,y-b)))^{1/4},</math>

<math>||f||_2=(\mathrm{IP-lim}_a\mathrm{IP-lim}_b {1\over |X|}\sum_{(x,y)\in X} f((x,y))f((x,y+a))f((x+b,y-b))f((x+b,y+a-b)))^{1/4}.</math>
Now, let me explain what this means. <math>a</math> and <math>b</math> are subsets of <math>[n]</math>, and we identify <math>a</math> with the characteristic function of <math>a</math>, which is a member of <math>[n]^{[n]}.</math> (That is how we can add <math>a</math> to <math>x</math> inside, etc. Since <math>[n]</math> is a finite set, you can’t really take limits, but if <math>n</math> is large, we can do something almost as good, namely ensure that whenever <math>\max\alpha<\min\beta</math>, the expression we are taking the limit of is close to something (Milliken Taylor ensures this, I think). Of course, you have to restrict <math>a</math> and <math>b</math> to a subspace. What is a subspace? You take a sequence <math>a_i</math> of subsets of <math>[n]</math> with <math>\max a_i<\min a_{i+1}</math> and then restrict to unions of the <math>a_i.</math>

Now here is the idea. Take a subset <math>E</math> of <math>X</math> and let <math>f</math> be its balanced indicator function. You first want to show that if ''either'' of the above-defined 2-norms of <math>f</math> is small, then <math>E</math> contains about the right number of corners <math>\{ (x,y), (x+a,y), (x,y+a)\}.</math> Restricted to the subspace of course. What does that mean? Well, you treat each of the <math>a_i</math> as a single coordinate, moving them together. The other coordinates I’m not sure about. Maybe you can just fix them in the right way and have the norm that was small summing over all of <math>X</math> still come out small. At any rate, the real trick is to show that if ''both'' coordinate 2-norms are big, you get a density increment on a subspace. Here a subspace surely means that you find some <math>a_i</math>s, treat them as single coordinates, and fix the values on the other coordinates. (If the analogy with Shkredov's proof of the Szemeredi corners theorem holds, you probably only need for one of these norms to be big....)

Talk:Main Page

2009-04-27T18:54:53Z

130.237.201.143: Undo revision 1322 by 78.106.190.31 (Talk)

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

Talk:Main Page

2009-04-26T07:55:05Z

130.237.201.143: Undo revision 1320 by 78.106.127.146 (Talk)

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

Higher-dimensional DHJ numbers

2009-04-22T19:01:48Z

130.237.201.143:

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-04-22T18:55:29Z

130.237.201.143:

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 || 14406
|}

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.

Modification of the Ajtai-Szemerédi argument

2009-04-22T18:53:01Z

130.237.201.143: Undo revision 1303 by 201.46.247.177 (Talk)

==Introduction==

This page is devoted to a detailed outline of a proof of the [[corners theorem]]. It is closely related to the [[Ajtai-Szemerédi's_proof_of_the_corners_theorem|proof of Ajtai and Szemerédi]], but it is not quite identical. Their proof feels a bit like a clever trick: it is possible to regard this proof as an explanation of why theirs works. Here, for completeness, is a statement of the theorem.

'''Theorem.''' (Ajtai and Szemerédi) For every <math>\delta>0</math> there exists n such that every subset A of <math>[n]^2</math> of size at least <math>\delta n^2</math> contains a triple of points <math>(x,y),(x+d,y),(x,y+d)</math> with <math>d>0.</math>

==Notation and terminology==

A [[corner]] is a subset of <math>[n]^2</math> of the form <math>\{(x,y),(x+d,y),(x,y+d)\}</math> with <math>d>0.</math> A ''corner-free'' subset of <math>[n]^2</math> is a subset that contains no corners. A ''grid'' is a subset of <math>[n]^2</math> of the form <math>P\times Q</math> where P and Q are arithmetic progressions with the same common difference. A ''diagonal'' is a set of the form <math>\{(x,y):x+y=t\}</math> for some t.

A ''1-set'' is a subset of <math>[n]^2</math> of the form <math>X\times [n].</math> A ''2-set'' is a set of the form <math>[n]\times Y.</math> A ''12-set'' is a set of the form <math>X\times Y.</math> The 12-set <math>X\times Y</math> is the intersection of the 1-set <math>X\times[n]</math>with the 2-set <math>[n]\times Y.</math> These definitions localize to grids in an obvious way: for example, a ''1-subset'' of the grid <math>P\times Q</math> is a set of the form <math>R\times Q</math> where R is a subset of P.

We shall use words like "long" and "large" to mean "of size that tends to infinity with n". For instance, if P and Q are arithmetic progressions with the same common difference and length <math>\log\log\log\log\log\log n,</math> then <math>P\times Q</math> is a large grid and P and Q are long arithmetic progressions. Also, if A is the set inside which we are trying to find a corner and X is some subset of <math>[n]^2,</math>, then we shall refer to the number <math>|A\cap X|/|X|</math> both as ''the density of'' A '' inside'' X, and also as ''the density of'' X. We shall use the latter wording only when there is no question of our being interested in the number <math>|X|/n^2.</math>

==The proof==

===Step 1: finding a dense diagonal===

There are only 2n-1 diagonals, and each diagonal has length at most n. Therefore, if A has size <math>\delta n^2,</math> then there must be a diagonal that contains at least <math>\delta n/2</math> points of A, and inside this diagonal A must have density at least <math>\delta/2.</math>

===Step 2: a dense 12-set disjoint from A===

Pick a dense diagonal. That is, pick t such that the set <math>\{(x,y):x+y=t\}</math> has density at least <math>\delta/2.</math> Enumerate the points of this diagonal as <math>(x_1,y_1),\dots,(x_{2m},y_{2m}),</math> in increasing order of x. (If there are an odd number, then remove one.) Let <math>X=\{x_1,\dots,x_m\}</math> and let <math>Y=\{y_{m+1},\dots,y_{2m}\}.</math> If <math>(x_i,y_j)\in A</math> for some <math>i<j,</math> then the three points <math>(x_i,y_j),(x_i,t-x_i),(t-y_j,y_j)</math> form a corner. (The d in this corner is <math>t-x_i-y_j,</math> which is greater than zero because <math>y_j<y_i=t-x_i.)</math> Therefore the set <math>X\times Y,</math> which has density at least <math>\delta^2/16</math> in <math>[n]^2,</math> is disjoint from A.

===Step 3: a dense 12-set that correlates with A===

Now partition <math>[n]^2</math> into the four sets <math>X\times Y, X\times Y^c, X^c\times Y</math> and <math>X^c\times Y^c.</math> Let f be the balanced function of A. (That is, <math>f(x,y)=1-\delta</math> when <math>(x,y)\in A</math> and <math>-\delta</math> otherwise.) Then <math>\sum_{(x,y)\in X\times Y}f(x,y)\leq-\delta^3n^2/16,</math> so on one of the other three sets the sum must be at least <math>\delta^3n^2/48.</math> This gives us a 12-set <math>U\times V</math> such that the density of A inside <math>U\times V</math> is at least <math>\delta+\delta^3/48.</math> And trivially the set must have density at least <math>\delta^3/48</math> (though with a bit more effort one can do better than this).

===Step 4: a dense 1-set can be almost entirely partitioned into large grids===

Let <math>X\times[n]</math> be a dense 1-set. By Szemerédi's theorem we can find a long arithmetic progression <math>P_1</math> inside X, then a long arithmetic progression <math>P_2</math> inside <math>X\setminus P_1,</math> and so on. We can continue this process until what is left of X has density at most <math>\eta.</math> This partitions almost all of X into sets of the form <math>P_i\times[n].</math> If we have also ensured that the widths of these progressions <math>P_i</math> are not too large (which is easy to do -- I am defining the width to be the difference between the maximal element and the minimal element), then for each i one can partition almost all of <math>[n]</math> into translates <math>Q_{i1},\dots,Q_{ir_i}</math> of <math>P_i.</math> And then the sets <math>P_i\times Q_{ij}</math> partition almost all of <math>X\times[n].</math>

===Step 5: a dense 12-set can be almost entirely partitioned into large grids===

Let <math>X\times Y</math> be a dense 12-set. Use the previous step to partition almost all of <math>X\times[n]</math> into large grids. Throw away any of these grids<math>P\times Q</math> if Y has very small density inside <math>Q:</math> the total number of points of <math>[n]\times Y</math> in the discarded grids is a very small fraction of <math>n^2.</math> For all the remaining grids <math>P\times Q,</math> <math>P\times(Y\cap Q)</math> is a dense 2-subset of <math>P\times Q</math> and hence, by the previous step, can be almost entirely partitioned into large grids. The result is a partition of almost all of <math>X\times Y</math> into large grids.

===Step 6: obtaining a density increment on a large grid===

We are almost finished. Let A be a corner-free set of density <math>\delta.</math> By Step 3 we can find a dense 12-set <math>X\times Y</math> inside which A has density at least <math>\delta+c\delta^3.</math> By Step 5, we can partition almost all of <math>X\times Y</math> into large grids. Therefore, by averaging we have a large grid inside which the density is at least <math>\delta+c\delta^3/2.</math> That density increase allows us to iterate, so the corners theorem is proved.

==Remark==

This proof is clearly very similar to the proof of Ajtai and Szemerédi. However, it is not quite identical, because we take correlation with a 12-set as our starting point. This streamlines the argument considerably, because it is not necessary to keep track of the density of A inside grids: we just have to partition the 12-set into large grids and an averaging argument at the end finishes things off. (Note that in the above proof we did not have a lemma that said that if A often has reduced density in certain subsets then it must sometimes have increased density: all that was contained in the final trivial averaging argument.)

Aside from this simplification, the main motivation for this argument is that it is now in a form that is much more easily transferable to DHJ(3). See [[A_second_outline_of_a_density-increment_argument|this page]] for details.

IP-Szemerédi theorem

2009-04-16T06:58:49Z

130.237.201.143: Undo revision 1296 by 212.116.219.92 (Talk)

'''IP-Szemerédi theorem''': If n is sufficiently large depending on <math>\delta > 0</math>, then any subset of <math>[2]^n \times [2]^n</math> of density at least <math>\delta</math> contains a corner <math>(x,y), (x+r,y), (x,y+r)</math>, where x, y, x+r, y+r all lie in <math>[2]^n</math> and r lies in <math>[2]^n \backslash 0^n</math>.

Implies the [[corners theorem]], and hence [[Roth's theorem]]. Is implied in turn by the [[density Hales-Jewett theorem]], and may thus be a simpler test case.

No combinatorial proof of this theorem is currently known.

Randall McCutcheon proposes a slightly weaker version of this theorem in which <math>[2]^n</math> is replaced by <math>[n]^n</math>, but r is still constrained to <math>[2]^n \backslash 0^n</math>.

== Relationship with DHJ(3) ==

First note that the density Hales-Jewett theorem for <math>k=3</math> is equivalent to the following statement.

'''Theorem.''' Let <math>\mathcal{A}</math> be a dense subset of the set of all pairs <math>(A,B)</math> of disjoint subsets of <math>[n].</math> Then <math>\mathcal{A}</math> contains a triple of the form <math>(A,B),(A\cup D,B),(A,B\cup D),</math> where A, B and D are all disjoint.

To see the equivalence, just associate with each pair <math>(A,B)</math> the sequence in <math>[3]^n</math> that is 1 on A, 2 on B and 3 everywhere else. Then a triple of pairs as described in the theorem corresponds to a combinatorial line. (One can of course modify the statement above to obtain a version that is equivalent to DHJ(3) with the [[equal-slices measure]].)

Now let us see how to modify the set-pairs formulation of DHJ(3) to obtain a statement equivalent to the IP-Szemerédi theorem. All we have to do is drop the condition that A and B should be disjoint.

'''Theorem.''' Let <math>\mathcal{A}</math> be a dense subset of the set of all pairs <math>(A,B)</math> of subsets of <math>[n].</math> Then <math>\mathcal{A}</math> contains a triple of the form <math>(A,B),(A\cup D,B),(A,B\cup D),</math> where D is disjoint from both A and B.

The equivalence of this with the IP-Szemerédi theorem is even easier to see: one just associates each set with its characteristic function.

== Motivation for considering the IP-Szemerédi theorem ==

When trying to solve a problem, one good strategy is to look for the simplest related problem that involves the same difficulties (or some of the same difficulties) that one is facing. The IP-Szemerédi theorem is a good candidate for a result that has this relationship with DHJ(3). Since no combinatorial proof is known, it clearly involves some serious difficulties. However, if we drop the condition that A and B have to be disjoint, then the bipartite graph formed by joining A to B if and only if <math>(A,B)\in\mathcal{A}</math> is dense if <math>\mathcal{A}</math> is dense. This means that one third of the natural tripartite graph associated with the problem (see the article on the [[triangle removal lemma]] for details) is dense, which should make it easier, but not too much easier, to analyse than the tripartite graph naturally associated with DHJ(3).

== Unorganised discussion ==

'''Solymosi.2:''' In this note I will try to argue that we should consider a variant of the original problem first. If the removal technique doesn’t work here, then it won’t work in the more difficult setting. If it works, then we have a nice result! Consider the Cartesian product of an IP_d set. (An IP_d set is generated by d numbers by taking all the <math>2^d</math> possible sums. So, if the n numbers are independent then the size of the IP_d set is <math>2^d</math>. In the following statements we will suppose that our IP_d sets have size <math>2^n</math>.)

Prove that for any <math>c>0</math> there is a <math>d</math>, such that any <math>c</math>-dense subset of the Cartesian product of an IP_d set (it is a two dimensional pointset) has a corner.

The statement is true. One can even prove that the dense subset of a Cartesian product contains a square, by using the density HJ for <math>k=4</math>. (I will sketch the simple proof later) What is promising here is that one can build a not-very-large tripartite graph where we can try to prove a removal lemma. The vertex sets are the vertical, horizontal, and slope -1 lines, having intersection with the Cartesian product. Two vertices are connected by an edge if the corresponding lines meet in a point of our <math>c</math>-dense subset. Every point defines a triangle, and if you can find another, non-degenerate, triangle then we are done. This graph is still sparse, but maybe it is well-structured for a removal lemma.

Finally, let me prove that there is square if <math>d</math> is large enough compare to <math>c</math>. Every point of the Cartesian product has two coordinates, a 0,1 sequence of length <math>d</math>. It has a one to one mapping to <math>[4]^d</math>; Given a point <math>( (x_1,…,x_d),(y_1,…,y_d) )</math> where <math>x_i,y_j</math> are 0 or 1, it maps to <math>(z_1,…,z_d)</math>, where <math>z_i=0</math> if <math>x_i=y_i=0</math>, <math>z_i=1</math> if <math>x_i=1</math> and <math>y_i=0, z_i=2</math> if <math>x_i=0</math> and <math>y_i=1</math>, and finally <math>z_i=3</math> if <math>x_i=y_i=1</math>. Any combinatorial line in <math>[4]^d</math> defines a square in the Cartesian product, so the density HJ implies the statement.

'''Gowers.7:''' With reference to Jozsef’s comment, if we suppose that the <math>d</math> numbers used to generate the set are indeed independent, then it’s natural to label a typical point of the Cartesian product as <math>(\epsilon,\eta)</math>, where each of <math>\epsilon</math> and <math>\eta</math> is a 01-sequence of length <math>d</math>. Then a corner is a triple of the form <math>(\epsilon,\eta)</math>, <math>(\epsilon,\eta+\delta)</math>, <math>(\epsilon+\delta,\eta)</math>, where <math>\delta</math> is a <math>\{-1,0,1\}</math>-valued sequence of length <math>d</math> with the property that both <math>\epsilon+\delta</math> and <math>\eta+\delta</math> are 01-sequences. So the question is whether corners exist in every dense subset of the original Cartesian product.

This is simpler than the density Hales-Jewett problem in at least one respect: it involves 01-sequences rather than 012-sequences. But that simplicity may be slightly misleading because we are looking for corners in the Cartesian product. A possible disadvantage is that in this formulation we lose the symmetry of the corners: the horizontal and vertical lines will intersect this set in a different way from how the lines of slope -1 do.

I feel that this is a promising avenue to explore, but I would also like a little more justification of the suggestion that this variant is likely to be simpler.

'''Gowers.22:''' A slight variant of the problem you propose is this. Let’s take as our ground set the set of all pairs <math>(U,V)</math> of subsets of <math>[n]</math>, and let’s take as our definition of a corner a triple of the form <math>(U,V), (U\cup D,V), (U,V\cup D)</math>, where both the unions must be disjoint unions. This is asking for more than you asked for because I insist that the difference <math>D</math> is positive, so to speak. It seems to be a nice combination of Sperner’s theorem and the usual corners result. But perhaps it would be more sensible not to insist on that positivity and instead ask for a triple of the form <math>(U,V), ((U\cup D)\setminus C,V), (U, (V\cup D)\setminus C</math>, where <math>D</math> is disjoint from both <math>U</math> and <math>V</math> and <math>C</math> is contained in both <math>U</math> and <math>V</math>. That is your original problem I think.

I think I now understand better why your problem could be a good toy problem to look at first. Let’s quickly work out what triangle-removal statement would be needed to solve it. (You’ve already done that, so I just want to reformulate it in set-theoretic language, which I find easier to understand.) We let all of <math>X</math>, <math>Y</math> and <math>Z</math> equal the power set of <math>[n]</math>. We join <math>U\in X</math> to <math>V\in Y</math> if <math>(U,V)\in A</math>.

Ah, I see now that there’s a problem with what I’m suggesting, which is that in the normal corners problem we say that <math>(x,y+d)</math> and <math>(x+d,y)</math> lie in a line because both points have the same coordinate sum. When should we say that <math>(U,V\cup D)</math> and <math>(U\cup D,V)</math> lie in a line? It looks to me as though we have to treat the sets as 01-sequences and take the sum again. So it’s not really a set-theoretic reformulation after all.

'''O'Donnell.35:''' Just to confirm I have the question right…

There is a dense subset <math>A</math> of <math>\{0,1\}^n x \{0,1\}^n</math>. Is it true that it must contain three nonidentical strings <math>(x,x’), (y,y’), (z,z’)</math> such that for each <math>i = 1…n,</math> the 6 bits

<math>[ x_i x'_i ]</math>

<math>[ y_i y'_i ]</math>

<math>[ z_i z'_i ]</math>

are equal to one of the following:

<math>[ 0 0 ] [ 0 0 ] [ 0, 1 ] [ 1 0 ] [ 1 1 ] [ 1 1 ]</math>

<math>[ 0 0 ], [ 0 1 ], [ 0, 1 ], [ 1 0 ], [ 1 0 ], [ 1 1 ],</math>

<math>[ 0 0 ] [ 1 0 ] [ 0, 1 ] [ 1 0 ] [ 0 1 ] [ 1 1 ]</math>

?

'''McCutcheon.469:''' IP Roth:

Just to be clear on the formulation I had in mind (with apologies for the unprocessed code): for every <math>\delta>0</math> there is an <math>n</math> such that any <math>E\subset [n]^{[n]}\times [n]^{[n]}</math> having relative density at least <math>\delta</math> contains a corner of the form <math>\{a, a+(\sum_{i\in \alpha} e_i ,0),a+(0, \sum_{i\in \alpha} e_i)\}</math>. Here <math>(e_i)</math> is the coordinate basis for <math>[n]^{[n]}</math>, i.e. <math>e_i(j)=\delta_{ij}</math>.

Presumably, this should be (perhaps much) simpler than DHJ, <math>k=3</math>.

Higher-dimensional DHJ numbers

2009-04-09T05:42:17Z

130.237.201.143:

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
|}

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) ==

There are five types of points: 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

== General lower bounds ==

There are k^{n-1} 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 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>.

If k is prime and <math>k \ge n</math>, 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.

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 <math>0\le x\le p-k</math> (mod p), So the density of deleted points is at most (p-k+1)/p. This approaches zero as <math>k\rightarrow\infty</math>. For example, the following paper shows there is a prime between x-x^0.525 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.

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 Fujimura

2009-04-07T08:29:41Z

130.237.201.143:

Let <math>\overline{c}^\mu_{n,4}</math> be the largest subset of the tetrahedral grid:

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

which contains no tetrahedrons <math>(a+r,b,c,d), (a,b+r,c,d), (a,b,c+r,d), (a,b,c,d+r)</math> with <math>r > 0</math>; call such sets ''tetrahedron-free''.

These are the currently known values of the sequence:

{|
| n || 0 || 1 || 2 || 3 || 4 || 5 || 6 || 7
|-
| <math>\overline{c}^\mu_{n,4}</math> || 1 || 3 || 7 || 14 || 24 || 37 || 55 || 78
|}

== n=0 ==

<math>\overline{c}^\mu_{0,4} = 1</math>:

There are no tetrahedrons, so no removals are needed.

== n=1 ==

<math>\overline{c}^\mu_{1,4} = 3</math>:

Removing any one point on the grid will leave the set tetrahedron-free.

== n=2 ==

<math>\overline{c}^\mu_{2,4} = 7</math>:

Suppose the set can be tetrahedron-free in two removals. One of (2,0,0,0), (0,2,0,0), (0,0,2,0), and (0,0,0,2) must be removed. Removing any one of the four leaves three tetrahedrons to remove. However, no point coincides with all three tetrahedrons, therefore there must be more than two removals.

Three removals (for example (0,0,0,2), (1,1,0,0) and (0,0,2,0)) leaves the set tetrahedron-free with a set size of 7.

== General n ==

A lower bound of 2(n-1)(n-2) can be obtained by keeping all points with exactly one coordinate equal to zero.

You get a non-constructive quadratic lower bound for the quadruple problem by taking a random subset of size <math>cn^2</math>. If c is not too large the linearity of expectation shows that the expected number of tetrahedrons in such a set is less than one, and so there must be a set of that size with no tetrahedrons. I think <math> c = \frac{24^{1/4}}{6} + o(\frac{1}{n})</math>.

With coordinates (a,b,c,d), take the value a+2b+3c. This forms an arithmetic progression of length 4 for any of the tetrahedrons we are looking for. So we can take subsets of the form a+2b+3c=k, where k comes from a set with no such arithmetic progressions. [[http://arxiv.org/PS_cache/arxiv/pdf/0811/0811.3057v2.pdf This paper]] gives a complicated formula for the possible number of subsets.

One upper bound can be found by counting tetrahedrons. For a given n the tetrahedral grid has <math>\frac{1}{24}n(n+1)(n+2)(n+3)</math> tetrahedrons. Each point on the grid is part of n tetrahedrons, so <math>\frac{1}{24}(n+1)(n+2)(n+3)</math> points must be removed to remove all tetrahedrons. This gives an upper bound of <math>\frac{1}{8}(n+1)(n+2)(n+3)</math>.

IP-Szemerédi theorem

2009-04-05T07:22:37Z

130.237.201.143: Undo revision 1255 by 148.233.239.24 (Talk)