Independent collections of translates of boxes and a conjecture due to Grünbaum (Q1196369)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Independent collections of translates of boxes and a conjecture due to Grünbaum |
scientific article |
Statements
Independent collections of translates of boxes and a conjecture due to Grünbaum (English)
0 references
14 December 1992
0 references
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.
0 references
independence
0 references
inclusion-exclusion
0 references
permutation
0 references
box
0 references
0 references
0 references