University:
California State University, Northridge
Course:
MATH 360 | Abstract Algebra I
Academic year:

2006
Views:

447

Pages:

11
Author:

Layla Bonilla

On the Number of Equilateral Triangles in Euclidean Spaces I In 1946 Paul Erdos [5] posed the seemingly innocent problem of finding the maximum number of unit segments that can be determined by a set of n points in the plane. This question turned out to be one of the most challenging unsolved problems ever proposed by Erdos. Even though the solution has long been out of reach, the quest for solving the problem generated a considerable amount of research in combinatorial geometry. Since then many problems sharing the same spirit have been raised; problems concerning the maximum number of geometric objects that can be determined by an n-point set in an euclidean space. In this article we address one of them. "What is the maximum number of equilateral triangles that can be determined by n points in the plane?" This problem was proposed several times by Erdos and Purdy ([8],[9],[10],[11]), and it is also mentioned in [3] not as a famous unsolved problem but as a problem that deserves to be studied. For an arbitrary finite set P denote by E(P) the number of triplets in P that are the vertices of an equilateral triangle, we define E(n) = max E(P). IPl=n Pi;;;IR2 It is easy to see that E( n) � i (�) since every pair of points in the plane are the vertices of at most two equilateral triangles; also by considering a suitable set of the regular triangular 1 Theorem 6 E5 (n) = 0 ( n 3 -½). Proof. Suppose that for some n � no there is an n-point set P determining at least n3 -½ equilateral triangles. Consider the 3-uniform hypergraph G = (P, � (P)). Then G 3 contains a subhypergraph H isomorphic to K� ). Assume x1,x2,x3,y1,Y2,Y3,Z1,z2,z3 are the vertices of Hand all triplets of the form {xj,Yk,zl} are the corresponding 3-edges. It can be shown that all sides of triangles in H have the same length (since all triangles in H are equilateral and have many sides in common). Assume without loss of generality that they have unit length. Then for all j E {1,2,3} the set {y1,Y 2 ,y3 ,z1,z 2 ,z3 } is contained in the 4-dimensional unit sphere SxJ with center in Xj. This implies that the 3-dimensional spheres S1, 2 := Sx 1 n Sx 2 and S1,3 := Sx 1 n Sx3 also contain the set {y1,Y2,y3,z1,z2,z3}. Note that the spheres S1,2 and S1,3 are distinct, since their centers are the middle points of the segments x1x 2 and x1x3 respectively. Hence S := S1,2 n S1,3 is a 2-dimensional sphere containing {y1, Y2, y3, z1, z 2 , z3}. Let Vi,2 be the set of points in S equidistant to Y1 and Y 2 , and similarly define Vi,3· Then Vi,2 and Vi,3 are distinct circles contained in S. To get a contradiction ■ observe that {z1,z2,z3} � Vi,2 n Vi,3 but IVi,2 n Vi,31 :::; 2. To complete this section we present examples in dimensions 4 and 5 with large number of unit equilateral triangles. l Proof. Let A � IR. 2 be the set of vertices of i j unit squares centered at the origin. Define P � IR.2 x IR. 2 by P =(Ax {0}) U ( {0}x A). Notice that if a1a2 is a unit segment in A then the triangle (a, 0),(0,a1),(0,a2 ) is equilateral for any a EA. Therefore F4(n) � F(P) � 32 liJ 2 = O(n2 ). For the second part consider the sphere S � IR.3 of radius � centered at the origin. Clarkson et al. [2] proved the existence of an j-point set B � S which determines O(n413 ) unit distances. Define the set Q =(Ax {0}) U ( {0}x B) � IR. 2 x IR.3 . Again if b1b2 is a unit segment in B then the triangle (a, 0), (0,b1),(0,b2) is equilateral for any a E A. Therefore l� 11

The Number of Equilateral Triangles in Euclidean Spaces I