ISSN:
1432-0444
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract A collection ofn setsA 1, ...,A n is said to beindependent provided every set of the formX 1 ⋂ ... ⋂X n is nonempty, where eachX i is eitherA i orA i c . We give a simple characterization for when translates of a given box form an independent set inR d. We use this to show that the largest number of such boxes forming an independent set inR d is given by ⌊3d/2⌋ ford≥2. This settles in the negative a conjecture of Grünbaum (1975), which states that the maximum size of an independent collection of sets homothetic to a fixed convex setC inR d isd+1. It also shows that the bound of 2d of Rényiet al. (1951) for the maximum number of boxes (not necessarily translates of a given one) with sides parallel to the coordinate axes in an independent collection inR d can be improved for these special collections.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02189309
