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 ci . 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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Grünbaum, B. (1975). Venn diagrams and independent families of sets.Math. Mag. 48, 12–23.
Marczewski, E. (1947). Indépendance d'ensembles et prolongements de mesures.Colloq. Math. 1, 122–132.
Naiman, D. Q., and Wynn, H. P. (1991a). Inclusion-exclusion bonferroni identities and inequalities for discrete tube-like problems via Euler characteristics.Ann. of Statist., to appear.
Naiman, D. Q., and Wynn, H. P. (1991b). Discrete Tube Theory inR d. Unpublished manuscript.
Rényi, A., Rényi, C., and Surányi, J. (1951). Sur l'independence des domaines simples dans l'espace euclidien àn dimensions.Colloq. Math. 2, 130–135.
Author information
Authors and Affiliations
Additional information
Daniel Q. Naiman was supported by National Science Foundation Grant No. DMS-9103126. Henry P. Wynn was supported by the Science and Engineering Research Council, UK.
Rights and permissions
About this article
Cite this article
Naiman, D.Q., Wynn, H.P. Independent collections of translates of boxes and a conjecture due to Grünbaum. Discrete Comput Geom 9, 101–105 (1993). https://doi.org/10.1007/BF02189309
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/BF02189309