Friday October 12th at 10.30am

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.