Intersection properties of boxes. I: An upper-bound theorem (Q1107826): Difference between revisions

Let \({\mathcal P}\) be a family of n boxes in \({\mathbb{R}}^ d\) (convex parallelohedrons with edges parallel to the coordinate axes). For \(k=0,1,...\), denote by \(f_ k({\mathcal P})\) the number of subfamilies of \({\mathcal P}\) of size \(k+1\) with non-empty intersection. The author proves that if \(f_ r({\mathcal P})=0\) for some \(r\leq n\), then the numbers \(f_ k({\mathcal P})\), \(k=1,...,\) \(r-1,\) are upper-bounded, respectively, by certain numbers \(f_ k(n,d,r)\) which are effectively determined. Moreover, these upper bounds are the best possible for each k. In particular, for \(k=1\), it is proved the following conjecture proposed by \textit{G. Kalai} [Isr. J. Math. 48, 167-174 (1984; Zbl 0557.52005)]: If \(f_ r({\mathcal P})=0\), then \(f_ 1({\mathcal P})\leq t_ r(n)\) for \(r\leq d\) and \(f_ 1({\mathcal P})\leq t_ d(n-r+d)+ (n-r+d)(r-d)+\binom{r-d}{2}\) for \(r\geq d\), where \(t_ r(n)\) denotes the number of edges of the Turán graph on n vertices, i.e. \(t_ r(n)\) is the maximum possible number of edges in a graph on n vertices containing no complete subgraph on \(r+1\) vertices. As an application, the author proves a theorem of ``fractional'' Helly-type in the sense of \textit{M. Katchalski} and \textit{A. Liu} [Proc. Am. Math. Soc. 75, 284-288 (1979; Zbl 0418.52013)] for families of boxes in \({\mathbb{R}}^ d.\)