How many atoms can be defined by boxes ?
type: Item
instance of: scholarly article
title: How many atoms can be defined by boxes ?
zbMATH Open document ID: 0598.52006
DOI: 10.1007/BF02579362
author: B. George
published in: Combinatorica
publication date: 1985-01-01T00:00:00Z
review text: 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.\)
Mathematics Subject Classification ID: 52A37
Mathematics Subject Classification ID: 52A20
Mathematics Subject Classification ID: 51M05
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 3964869
zbMATH Keywords: extremal families
zbMATH Keywords: overlap graph
zbMATH Keywords: overlay index
zbMATH Keywords: parallelepipeds
zbMATH Keywords: atoms
reviewed by: Wolfgang Weil
MaRDI profile type: Publication
cites work: Incidence matrices with the consecutive 1’s property
cites work: Q3328583
cites work: Q5663020
cites work: The structure of rectangle families dividing the plane into maximum number of atoms
cites work: Atoms of families of sets
description: scientific article; zbMATH DE number 3964869