# Difference between revisions of "Fujimura's problem"

(→General n) |
(→n=4) |
||

Line 26: | Line 26: | ||

[Cleanup required here] | [Cleanup required here] | ||

− | \overline{c}^\mu_4=9: | + | :<math>\overline{c}^\mu_4=9:</math> |

− | The set of all (a,b,c) in \Delta_4 with exactly one of a,b,c =0, has 9 elements and doesn’t contain any equilateral triangles. | + | The set of all <math>(a,b,c)</math> in <math>\Delta_4</math> with exactly one of a,b,c =0, has 9 elements and doesn’t contain any equilateral triangles. |

− | Let S\subset \Delta_4 be a set without equilateral triangles. If (0,0,4)\in S, there can only be one of (0,x,4-x) and (x,0,4-x) in S for x=1,2,3,4. Thus there can only be 5 elements in S with a=0 or b=0. The set of | + | Let <math>S\subset \Delta_4</math> be a set without equilateral triangles. If <math>(0,0,4)\in S</math>, there can only be one of <math>(0,x,4-x)</math> and <math>(x,0,4-x)</math> in S for <math>x=1,2,3,4</math>. Thus there can only be 5 elements in S with <math>a=0</math> or <math>b=0</math>. The set of elements with <math>a,b>0</math> is isomorphic to <math>\Delta_2</math>, so S can at most have 4 elements in this set. So <math>|S|\leq 4+5=9</math>. Similar if S contain (0,4,0) or (4,0,0). So if <math>|S|>9</math> S doesn’t contain any of these. Also, S can’t contain all of <math>(0,1,3), (0,3,1), (2,1,1)</math>. Similar for <math>(3,0,1), (1,0,3),(1,2,1)</math> and <math>(1,3,0), (3,1,0), (1,1,2)</math>. So now we have found 6 elements not in S, but <math>|\Delta_4|=15</math>, so <math>S\leq 15-6=9</math>. |

could you give your explicit list for removals from \overline{c}^\mu_4? I am unable to reproduce a triangle-free configuration from your description. | could you give your explicit list for removals from \overline{c}^\mu_4? I am unable to reproduce a triangle-free configuration from your description. |

## Revision as of 21:29, 12 February 2009

Let [math]\overline{c}^\mu_n[/math] the largest subset of the triangular grid

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

which contains no equilateral triangles. Fujimura's problem is to compute [math]\overline{c}^\mu_n[/math]. This quantity is relevant to a certain "hyper-optimistic" version of DHJ(3).

## n=0

It is clear that [math]\overline{c}^\mu_0 = 1[/math].

## n=1

It is clear that [math]\overline{c}^\mu_1 = 2[/math].

## n=2

It is clear that [math]\overline{c}^\mu_2 = 4[/math] (e.g. remove (0,2,0) and (1,0,1) from [math]\Delta_2[/math]).

## n=3

Deleting (0,3,0), (0,2,1), (2,1,0), (1,0,2) from [math]\Delta_3[/math] shows that [math]\overline{c}^\mu_3 \geq 6[/math]. In fact [math]\overline{c}^\mu_3 = 6[/math]: just note (3,0,0) or something symmetrical has to be removed, leaving 3 triangles which do not intersect, so 3 more removals are required.

## n=4

[Cleanup required here]

- [math]\overline{c}^\mu_4=9:[/math]

The set of all [math](a,b,c)[/math] in [math]\Delta_4[/math] with exactly one of a,b,c =0, has 9 elements and doesn’t contain any equilateral triangles.

Let [math]S\subset \Delta_4[/math] be a set without equilateral triangles. If [math](0,0,4)\in S[/math], there can only be one of [math](0,x,4-x)[/math] and [math](x,0,4-x)[/math] in S for [math]x=1,2,3,4[/math]. Thus there can only be 5 elements in S with [math]a=0[/math] or [math]b=0[/math]. The set of elements with [math]a,b\gt0[/math] is isomorphic to [math]\Delta_2[/math], so S can at most have 4 elements in this set. So [math]|S|\leq 4+5=9[/math]. Similar if S contain (0,4,0) or (4,0,0). So if [math]|S|\gt9[/math] S doesn’t contain any of these. Also, S can’t contain all of [math](0,1,3), (0,3,1), (2,1,1)[/math]. Similar for [math](3,0,1), (1,0,3),(1,2,1)[/math] and [math](1,3,0), (3,1,0), (1,1,2)[/math]. So now we have found 6 elements not in S, but [math]|\Delta_4|=15[/math], so [math]S\leq 15-6=9[/math].

could you give your explicit list for removals from \overline{c}^\mu_4? I am unable to reproduce a triangle-free configuration from your description.

For example, (4,0,0) (0,4,0) (0,0,4) (2,1,1) (1,1,2) (1,2,1) leaves the triangle (2,2,0) (0,2,2) (2,0,2).

## n=5

[Cleanup required here]

\overline{c}^\mu_5=12: The set of all (a,b,c) in \Delta_5 with exactly one of a,b,c=0 has 12 elements and doesn’t contain any equilateral triangles.

Let S\subset \Delta_5 be a set without equilateral triangles. If (0,0,5)\in S, there can only be one of (0,x,5-x) and (x,0,5-x) in S for x=1,2,3,4,5. Thus there can only be 6 elements in S with a=0 or b=0. The set of element with a,b>0 is isomorph to \Delta_3, so S can at most have 6 elements in this set. So |S|\leq 6+6=12. Similar if S contain (0,5,0) or (5,0,0). So if |S| >12 S doesn’t contain any of these. S can only contain 2 point in each of the following equilateral triangles: (3,1,1),(0,4,1),(0,1,4) (4,1,0),(1,4,0),(1,1,3) (4,0,1),(1,3,1),(1,0,4) (1,2,2),(0,3,2),(0,2,3) (3,2,0),(2,3,0),(2,2,1) (3,0,2),(2,1,2),(2,0,3) So now we have found 9 elements not in S, but |\Delta_5|=21, so S\leq 21-9=12.

## General n

[Cleanup required here]

A lower bound for [math]\overline{c}^\mu_n[/math] is 3(n-1), made of all points in [math]\Delta_n[/math] with exactly one coordinate equal to zero.

A trivial upper bound is

- [math]\overline{c}^\mu_{n+1} \leq \overline{c}^\mu_n + n+2[/math]

since deleting the bottom row of a equilateral-triangle-free-set gives another equilateral-triangle-free-set.