Independent collections of translates of boxes and a conjecture due to Grünbaum
type: Item
instance of: scholarly article
title: Independent collections of translates of boxes and a conjecture due to Grünbaum
zbMATH Open document ID: 0764.52001
DOI: 10.1007/BF02189309
author: Daniel Q. Naiman
author: Henry P. Wynn
published in: Discrete \& Computational Geometry
publication date: 1992-12-14T00:00:00Z
full work available at URL: https://eudml.org/doc/131236
review text: A collection \(\{A_ 1,\dots,A_ n\}\) of \(n\) sets is independent if \(\bigcap^ n_{i=1}X_ i\neq\emptyset\) whenever \(X_ i\in\{A_ i,A_ i^ c\}\) for \(i=1,\dots,n\). A box in \(\mathbb{R}^ d\) is a set of the form \(I_ 1\times\dots\times I_ d\) where each \(I_ j\) is a finite closed interval, and the intervals are in linearly independent subspaces. The main result of the authors is that the maximum number of boxes in an independent collection, all of which are translates of a given box, is \(\left\lfloor{3d\over 2}\right\rfloor\) for \(d\geq 2\). This shows that the conjecture of \(d+1\) by Grünbaum (1975) is false for \(d\geq 4\), and improves on the upper bound of \(2d\) of Rényi et al. (1951) for this special case.
Mathematics Subject Classification ID: 52A37
Mathematics Subject Classification ID: 05A18
zbMATH DE Number: 78495
zbMATH Keywords: independence
zbMATH Keywords: inclusion-exclusion
zbMATH Keywords: permutation
zbMATH Keywords: box
Wikidata QID: Q61855989
reviewed by: T. Bisztriczky
MaRDI profile type: Publication
cites work: A performance comparison of nodal discontinuous Galerkin methods on triangles and quadrilaterals
cites work: Indépendance d'ensembles et prolongement de mesures (Résultats et problèmes)
cites work: Inclusion-exclusion-Bonferroni identities and inequalities for discrete tube-like problems via Euler characteristics
cites work: Distances between intuitionistic fuzzy sets and/or interval-valued fuzzy sets based on the Hausdorff metric
OpenAlex ID: W2018152997
DBLP publication ID: journals/dcg/NaimanW93
description: scientific article; zbMATH DE number 78495