Finite Sets as Complements of Finite Unions of Convex Sets

Suppose S?? ^d is a set of (finite) cardinality n, whose complement can be written as the union of k convex sets. It is perhaps intuitively appealing that when n is large k must also be large. This is true, as is shown here. First the case in which the convex sets must also be open is considered, and in this case a family of examples yields an upper bound, while a simple application of a theorem of Björner and Kalai yields a lower bound. Much cruder estimates are then obtained when the openness restriction is dropped. For a given set S the problem of determining the smallest number of convex sets whose union is ? ^d ?S is shown to be equivalent to the problem of finding the chromatic number of a certain (infinite) hypergraph ? _S . We consider the graph (mathcal {G}_{S}) whose edges are the 2-element edges of ? _S , and we show that, when d=2, for any sufficiently large set S, the chromatic number of (mathcal{G}_{S}) will be large, even though there exist arbitrarily large finite sets S for which (mathcal{G}_{S}) does not contain large cliques.