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 GSmathcal {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 GSmathcal{G}_{S} will be large, even though there exist arbitrarily large finite sets S for which GSmathcal{G}_{S} does not contain large cliques.
展开▼
机译：假设S⊆ℝ d 是（有限）基数n的集合，其补码可以写成k个凸集的并集。也许直观上吸引人的是，当n大时，k也必须大。如此处所示，这是正确的。首先，考虑其中凸集也必须开放的情况，在这种情况下，一系列示例产生一个上限，而简单应用Björner和Kalai定理则产生一个下界。当取消开放性限制时，可以得到很多粗略的估计。对于给定的集合S，确定其并集为ℝ d ∖S的凸集的最小数量的问题与寻找某个（无限）超图ℋ的色数的问题等效。 S 。我们考虑图G S 数学{G} _ {S}，其边是ℋ S 的2个元素的边，并且表明，当d = 2时，对于任何足够大的集S，即使存在任意大的有限集S，G S mathcal {G} _ {S}的色数也会很大。 sub> mathcal {G} _ {S}不包含大型集团。
展开▼
