SPHERE OF INFLUENCE GRAPHS - EDGE DENSITY AND CLIQUE SIZE

Let X = {X(1),...,X(n)} be a set of n points (n greater than or equal to 2) in the metric space M. Let r(i) denote the minimum distance betw een X(i) and any other point in X. The closed ball (B) over bar(i) wit h center X(i) and radius r(i) is the closed sphere of influence at X(i ). The closed sphere of influence graph CSIG (M, X) has vertex set X w ith distinct vertices X(i) and X(j) adjacent provided (B) over bar(i) boolean AND (B) over bar(j) not equal 0. The graph G is an M-CSIG prov ided G is isomorphic to CSIG(M, X) for some set X of points in M. We p rove that, for any metric space M, the clique number is bounded over t he class of M-CSIGs if and only if there is a constant (C) over bar, s o that the inequality \E\ less than or equal to (C) over bar\V\ holds whenever G = (V, E) is an M-CSIG. The proof uses Ramsey's Theorem, We also prove that if M = (R(d),rho) is a d-dimensional Minkowski space, then (C) over bar less than or equal to 5(d) - 3/2.