tailieunhanh - Báo cáo toán học: "Sets of Points Determining Only Acute Angles and Some Related Colouring Problems"

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Sets of Points Determining Only Acute Angles and Some Related Colouring Problems. | Sets of Points Determining Only Acute Angles and Some Related Colouring Problems David Bevan Fernwood Leaford Crescent Watford Herts. WD24 5TW England dbevan@ Submitted Jan 20 2004 Accepted Feb 7 2006 Published Feb 15 2006 Mathematics Subject Classifications 05D40 51M16 Abstract We present both probabilistic and constructive lower bounds on the maximum size of a set of points S c Rd such that every angle determined by three points in S is acute considering especially the case S c 0 1 d. These results improve upon a probabilistic lower bound of Erdos and Furedi. We also present lower bounds for some generalisations of the acute angles problem considering especially some problems concerning colourings of sets of integers. 1 Introduction Let us say that a set of points Sc Rd is an acute d-set if every angle determined by a triple of S is acute 7 . Let us also say that S is a cubic acute d-set if S is an acute d-set and is also a subset of the unit d-cube . S c 0 1 d . Let us further say that a triple u v w 2 Rd is an acute triple a right triple or an obtuse triple if the angle determined by the triple with apex v is less than 2 equal to 7 or greater than 7 respectively. Note that we consider the triples u v w and w v u to be the same. We will denote by a d the size of a largest possible acute d-set. Similarly we will denote by n d the size of a largest possible cubic acute d-set. Clearly n d a d n d n d 1 and a d a d 1 for all d. THE ELECTRONIC JOURNAL OF COMBINATORICS 13 2006 R12 1 In EF Paul Erdos and Zoltán Fiiredi gave a probabilistic proof that n d see also AZ2 . This disproved an earlier conjecture of Ludwig Danzer and Branko Grunbaum DG that a d 2d 1. In the following two sections we give improved probabilistic lower bounds for n d and a d . In section 4 we present a construction that gives further improved lower bounds for n d for small d. In section 5 we tabulate the best lower bounds known for n d and a d for small d. Finally in sections 6-9 we .