Discrete Mathematics and Optimization Seminar

---

JANOS PACH
City College and Renyi Institute
Friday October 12th at 10.30am
Burnside 1214



Title. Decomposition Of Multiple Coverings.

Abstract. A family C of convex bodies form a k-fold covering of a region R
if every point of R is contained in at least k members of C. Twenty
years ago I proved that for each centrally symmetric convex polygon P,
there is a constant k = k(P) such that any k-fold covering of the plane
with translates of P can be decomposed into two coverings. Does the
same theorem remain true for (a) unit circles in the place of polygons,
(b) circles of arbitrary radii, (c) unit balls in higher dimensions? We
survey some old and new results of this type.

The case when C consists of axis-parallel rectangles will be discussed
in more detail. We construct, for every k, a k-fold covering
C(k) of the plane (or of a large square) with rectangles whose sides are
parallel to the coordinate-axes, such that C(k) cannot be split into two
coverings (P.-Tardos-Toth). We also present, for every k and c, a
probabilistic construction of a k-fold covering C(k;c) of the plane with
axis-parallel rectangles such that no matter how we color these rectangles
with c colors, we find a point that is covered only by rectangles of
the same color (P.-Tardos). The dual statement is also true.