Intersection properties of boxes. I: An upper-bound theorem
type: Item
instance of: scholarly article
title: Intersection properties of boxes. I: An upper-bound theorem
zbMATH Open document ID: 0653.52003
DOI: 10.1007/BF02783298
author: Jürgen Eckhoff
published in: Israel Journal of Mathematics
publication date: 1988-01-01T00:00:00Z
review text: 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.\)
Mathematics Subject Classification ID: 52A20
Mathematics Subject Classification ID: 52A35
zbMATH DE Number: 4065815
zbMATH Keywords: convex set
zbMATH Keywords: Helly theorem
zbMATH Keywords: boxes
reviewed by: Radu Precup
MaRDI profile type: Publication
cites work: A Turan type problem for interval graphs
cites work: A simple proof of the upper bound theorem
cites work: On a Coloring Problem.
cites work: Q3852212
cites work: Intersection properties of boxes in \(R^ n\).
cites work: An upper-bound theorem for families of convex sets
cites work: The structure of rectangle families dividing the plane into maximum number of atoms
cites work: Q4143339
cites work: Intersection patterns of convex sets
cites work: Boxes in Rn —A ‘Fractional’ Theorem
cites work: A Problem of Geometry in R n
cites work: The maximum numbers of faces of a convex polytope
cites work: Sur l'indépendance de domaines simples dans l'espace euclidien à n dimensions
cites work: Q5588433
cites work: The maximum number of q-cliques in a graph with no p-clique
cites work: Q5781249
cites work: On the theory of graphs
cites work: Über eine kombinatorisch-geometrische Frage von Hadwiger und Debrunner
cites work: Q5790850
description: scientific article; zbMATH DE number 4065815