Higher-dimensional Fujimura - Revision history

124.177.190.1: /* General n */

2009-04-14T14:28:49Z

General n

← Older revision		Revision as of 07:28, 14 April 2009
Line 39:		Line 39:
	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. However, <math> c = (24^{1/4})/6 + o(1/n)</math>, which is lower than the previous lower bound.		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. However, <math> c = (24^{1/4})/6 + o(1/n)</math>, which is lower than the previous lower bound.

	With coordinates (a,b,c,d), consider 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, Corollary 1]] gives ~~a complicated~~ formula for a lower bound on the proportion of retained points:		With coordinates (a,b,c,d), consider 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, Corollary 1]] gives this formula for a lower bound on the proportion of retained points:
	<math>C\frac{(log N)^{1/4}}{2^\sqrt{8 log N}}</math>, for some absolute constant C.		<math>C\frac{(log N)^{1/4}}{2^\sqrt{8 log N}}</math>, for some absolute constant C.

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

124.177.190.1: /* General n */

2009-04-14T14:28:00Z

General n

← Older revision		Revision as of 07:28, 14 April 2009
Line 37:		Line 37:
	A lower bound of 2(n-1)(n-2) can be obtained by keeping all points with exactly one coordinate 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. ~~I think~~ <math> c = ~~\frac{~~24^{1/4}}{6} + o(~~\frac{~~1}{n})</math>.		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. However, <math> c = (24^{1/4})/6 + o(1/n)</math>, which is lower than the previous lower bound.

	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~~.		With coordinates (a,b,c,d), consider 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, Corollary 1]] gives a complicated formula for a lower bound on the proportion of retained points:
			<math>C\frac{(log N)^{1/4}}{2^\sqrt{8 log N}}</math>, for some absolute constant C.

	~~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>~~.		An upper bound can be found by counting tetrahedrons. For a given n the tetrahedral grid has n(n+1)(n+2)(n+3)/24 tetrahedrons. Each point on the grid is part of n tetrahedrons, so (n+1)(n+2)(n+3)/24 points must be removed to remove all tetrahedrons. This gives an upper bound of (n+1)(n+2)(n+3)/8 remaining points.

130.237.201.143 at 08:29, 7 April 2009

2009-04-07T08:29:41Z

← Older revision		Revision as of 01:29, 7 April 2009
Line 8:		Line 8:

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

Jbd at 13:37, 30 March 2009

2009-03-30T13:37:43Z

← Older revision		Revision as of 06:37, 30 March 2009
Line 8:		Line 8:

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

Jbd: New page: Let $\overline{c}^\mu_{n,4}$ be the largest subset of the tetrahedral grid: : $\{ (a,b,c,d) \in {\Bbb Z}_+^4: a+b+c+d=n \}$ which contains no tetrahedrons $(a+...$

2009-03-30T01:59:48Z

New page: 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+...

New page

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

Higher-dimensional Fujimura - Revision history

124.177.190.1: /* General n */

124.177.190.1: /* General n */

130.237.201.143 at 08:29, 7 April 2009

Jbd at 13:37, 30 March 2009

Jbd: New page: Let \overline{c}^\mu_{n,4} be the largest subset of the tetrahedral grid: : \{ (a,b,c,d) \in {\Bbb Z}_+^4: a+b+c+d=n \} which contains no tetrahedrons (a+...

Jbd: New page: Let $\overline{c}^\mu_{n,4}$ be the largest subset of the tetrahedral grid: : $\{ (a,b,c,d) \in {\Bbb Z}_+^4: a+b+c+d=n \}$ which contains no tetrahedrons $(a+...$