Difference between revisions of "Talk:Fujimura's problem"

From Polymath1Wiki
Jump to: navigation, search
(n=0)
(General n)
Line 36: Line 36:
  
 
A lower bound of 6(n-1) can be obtained by removing (n,0,0,0), (0,n,0,0), (0,0,n,0), and (0,0,0,n) and all "internal points" (points where no coordinate is a zero). Alternatively, this can be thought of as keeping all points with exactly two coordinates equal to zero.
 
A lower bound of 6(n-1) can be obtained by removing (n,0,0,0), (0,n,0,0), (0,0,n,0), and (0,0,0,n) and all "internal points" (points where no coordinate is a zero). Alternatively, this can be thought of as keeping all points with exactly two coordinates equal to zero.
 +
 +
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.
 
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.
  
 
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>.
 
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>.

Revision as of 10:47, 28 March 2009

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 \gt 0[/math]; call such sets tetrahedron-free.

These are the currently known values of the sequence:

n 0 1 2
[math]\overline{c}^\mu_{n,4}[/math] 1 3 7

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 6(n-1) can be obtained by removing (n,0,0,0), (0,n,0,0), (0,0,n,0), and (0,0,0,n) and all "internal points" (points where no coordinate is a zero). Alternatively, this can be thought of as keeping all points with exactly two coordinates equal to zero.

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.

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].