Fujimura's problem

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

[math]\displaystyle{ \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]\displaystyle{ \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]\displaystyle{ \overline{c}^\mu_0 = 1 }[/math].

n=1

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

n=2

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

n=3

Deleting (0,3,0), (0,2,1), (2,1,0), (1,0,2) from [math]\displaystyle{ \Delta_3 }[/math] shows that [math]\displaystyle{ \overline{c}^\mu_3 \geq 6 }[/math]. In fact [math]\displaystyle{ \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]

\overline{c}^\mu_4=9:

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.

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 element with a,b>0 is isomorph to \Delta_2, so S can at most have 4 elements in this set. So |S|\leq 4+5=9. Similar if S contain (0,4,0) or (4,0,0). So if |S| >9 S doesn’t contain any of these. Also, S can’t contain all of (0,1,3), (0,3,1), (2,1,1). Similar for (3,0,1), (1,0,3),(1,2,1) and (1,3,0), (3,1,0), (1,1,2). So now we have found 6 elements not in S, but |\Delta_4|=15, so S\leq 15-6=9.

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]

Another lower bound is 3(n-1), as you keep most of all three sides of the triangle. Remove the corners and the inner triangle.