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
    0 references
    0 references
    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
    0 references
    independence
    0 references
    inclusion-exclusion
    0 references
    permutation
    0 references
    box
    0 references
    0 references