Covering with Euclidean boxes. (English) Zbl 0623.05041

The authors prove the following box cover theorem: For each dimension d there exists a constant c depending only on d such that any finite (or compact) set \(V\subset {\mathbb{R}}^ d\) contains a subset S with \(| S| \leq c\) and satisfying \(V\subset \cup_{p,q\in S}box(p,q)\) (box(p,q) denotes the smallest box containing p and q and whose faces are parallel to the coordinate axes of \({\mathbb{R}}^ d)\). For \(d=2\), the result was shown, with \(c=4\), by A. Gyárfás and the second author [Combinatorica 3, 351-358 (1983; Zbl 0534.05052)].
As a first consequence of the box cover theorem, it is shown that if H is a d-dimensional box-hypergraph then \(\rho\) (H)\(\leq c_ 0\cdot \alpha (H)^ c\), where \(\alpha\) (H) and \(\rho\) (H) denote, respectively, the stability and the covering number of H, and c and \(c_ 0\) are constants depending only on d. Another consequence is the extension to the general case of boxes defined by arbitrary finite-cone-subdivisions of \({\mathbb{R}}^ d\). Geometric variants of these results, with boxes replaced by angles, are also derived.
Reviewer: J.Weinstein


05C65 Hypergraphs
52A37 Other problems of combinatorial convexity
51M20 Polyhedra and polytopes; regular figures, division of spaces


Zbl 0534.05052
Full Text: DOI


[1] I. Bárány, An extension of the Erdös-Szekeres theorem on large angles, to appear.
[2] Berge, C., ()
[3] Chvatal, V., Monochromatic paths in edge-colored graphs, J. combin. theory soc. B,, 13, 69-70, (1972) · Zbl 0221.05064
[4] Cochand, M.; Duchet, P., Sous LES paves, Annals discr. math., 17, 191-202, (1983) · Zbl 0522.52001
[5] Erdös, P.; Szekeres, G., A combinatorial problem in geometry, Compositio math., 2, 463-470, (1935) · Zbl 0012.27010
[6] Gyárfás, A.; Lehel, J., A Helly-type problem in trees, (), 571-584
[7] Gyárfás, A.; Lehel, J., A Ramsey-type problem in directed and bipartite graphs, Periodica math. hung., 3, 299-304, (1973) · Zbl 0267.05115
[8] Gyárfás, A., J. Lehel, Hypergraph families with bounded edge cover or transversal number. combinatorica, 3, 351-358, (1983)
[9] Sands, B.; Sauer, N.; Woodrow, R., On monochromatic paths in edge-coloured diagraphs, J. combin. theory. ser. B, 33, 271-275, (1982) · Zbl 0488.05036
[10] Todd, M.J., ()
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.