How many atoms can be defined by boxes ?
A family \({\mathcal B}_ n=\{B_ 1,...,B_ n\}\) of boxes \(B_ i\subset E^ d\) (parallelepipeds with sides parallel to the coordinate axes) defines an equivalence relation between points x,y\(\in \cup^{n}_{i=1}B_ i\) (x,y are equivalent if, for \(i=1,...,n\), \(x\in B_ i\) if and only if \(y\in B_ i)\). The equivalence classes are called atoms of \({\mathcal B}_ n\). The number of atoms and, in particular, the maximal number b(n,d) was studied by \textit{R. Rado} [Combinatorica 2, 311- 314 (1982; Zbl 0509.05004)], who proved that \(b(n,1)=2n-1\) and gave bounds for b(n,d), \(d\geq 2\). Here, the authors characterize the interval families in \(E^ 1\) with 2n-1 atoms, they prove that \(b(n,2)=2n^ 2- 6n+7,\) and they study the asymptotic behaviour of b(n,d) for \(n\to \infty\). In particular, they show that \(\lim_{n\to \infty}b(n,3)/n^ 3=8/9.\)
scientific article; zbMATH DE number 3964869