Covering with Euclidean boxes
type: Item
instance of: scholarly article
title: Covering with Euclidean boxes
zbMATH Open document ID: 0623.05041
DOI: 10.1016/S0195-6698(87)80001-X
published in: European Journal of Combinatorics
publication date: 1987-01-01T00:00:00Z
review text: 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 \textit{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.
reviewed by: J.Weinstein
Mathematics Subject Classification ID: 05C65
Mathematics Subject Classification ID: 52A37
Mathematics Subject Classification ID: 51M20
zbMATH DE Number: 4010563
zbMATH Keywords: stability number
zbMATH Keywords: box cover theorem
zbMATH Keywords: box-hypergraph
zbMATH Keywords: covering number
zbMATH Keywords: finite-cone-subdivisions
author: Imre Bárány
author: Jeno Lehel
MaRDI profile type: Publication
cites work: Q3941433
cites work: Monochromatic paths in edge-colored graphs
cites work: Sous Les Pavés…
cites work: Q5759552
cites work: Q5609148
cites work: A Ramsey-type problem in directed and bipartite graphs
cites work: Hypergraph families with bounded edge cover or transversal number
cites work: On monochromatic paths in edge-coloured digraphs
cites work: The computation of fixed points and applications
Recommended article: On the cubicity of certain graphs
Recommended article: Boxicity and maximum degree
Recommended article: Grid intersection graphs and boxicity
Recommended article: Boxicity of line graphs
Recommended article: Cubicity, boxicity, and vertex cover
Recommended article: On point covers of multiple intervals and axis-parallel rectangles
Recommended article: New bounds on the maximum number of neighborly boxes in \(\mathbb{R}^d\)
Recommended article: Q3201796
Recommended article: The cubicity of hypercube graphs
Recommended article: Asymptotic bounds on the equilateral dimension of hypercubes
description: scientific article; zbMATH DE number 4010563