Covering planar sets

V. P. Filimonov

Sbornik. Mathematics, Tome 201 (2010) no. 8, pp. 1217-1248

Résumé

Problems connected with the classical Borsuk problem on partitioning a set in Euclidean space into subsets of smaller diameter, and also connected with the Nelson-Hadwiger problem on the chromatic number of Euclidean space, are studied. New bounds are obtained for the quantities $d_n=\sup d_n(\Phi)$ and $d'_n=\sup d'_n(\Phi)$, where the suprema are taken over all sets of unit diameter on a plane, and where the quantities $d_n(\Phi)$ and $d'_n(\Phi)$ are defined for a given bounded set $\Phi\subset\mathbb{R}^2$ as follows: \begin{align*} d_n(\Phi)&=\inf\{x\in\mathbb{R}^+:\Phi\subseteq \Phi_1\cup\dots\cup\Phi_n,\,\forall\, i\ \operatorname{diam}\Phi_i\le x\}, \\ d'_n(\Phi)&=\inf\{x\in\mathbb{R}^+:\Phi\subseteq \Phi_1\cup\dots\cup\Phi_n,\,\forall\, i\ \forall\, X,Y\in\Phi_i\,\ XY\ne x\}. \end{align*} Here the $\Phi_i\subset\mathbb R^2$ are subsets, $\operatorname{diam}\Phi_i$ is the diameter of $\Phi_i$, $XY$ is the distance between the points $X$ and $Y$, and $n\in \mathbb N$. The bounds obtained for $d_n$ are better than any known before; this paper is the first to consider the values $d'_n$. Bibliography: 19 titles.

Détail

Keywords: chromatic number, Borsuk problem, diameter of a set, coverings of planar sets, universal covering sets and systems.

Bibliographie

[1] K. Borsuk, “Drei Sätze uber die $n$-dimensionale euklidische Sphäre”, Fundamenta Math., 20 (1933), 177–190 | Zbl

[2] A. M. Raigorodskii, “Borsuk's problem and the chromatic numbers of some metric spaces”, Russian Math. Surveys, 56:1 (2001), 103–139 | DOI | MR | Zbl

[3] A. M. Raigorodskii, “Around Borsuk's hypothesis”, J. Math. Sci. (N. Y.), 154:4 (2008), 604–623 | DOI | MR | Zbl

[4] A. M. Raigorodskii, “Three lectures on the Borsuk partition problem”, London Math. Soc. Lecture Note Ser., 347, Cambridge Univ. Press, Cambridge, 2008, 202–247 | MR | Zbl

[5] V. G. Boltjansky, I. Ts. Gohberg, Results and problems in combinatorial geometry, Cambridge Univ. Press, Cambridge, 1985 | MR | MR | Zbl | Zbl

[6] V. Boltyanski, H. Martini, P. S. Soltan, Excursions into combinatorial geometry, Universitext, Springer-Verlag, Berlin, 1997 | MR | Zbl

[7] A. Soifer, “Khromaticheskoe chislo ploskosti: ego proshloe, nastoyaschee i buduschee”, Matem. prosveschenie, 2004, no. 8, 186–221

[8] A. M. Raigorodskii, Lineino-algebraicheskii metod v kombinatorike, MTsNMO, M., 2007

[9] L. A. Székely, “Erdős on unit distances and the Szemerédi–Trotter theorems”, Paul Erdős and his mathematics. II (Budapest, Hungary, 1999), Bolyai Soc. Math. Stud., 11, Springer-Verlag, Berlin; János Bolyai Math. Soc., Budapest, 2002, 649–666 | MR | Zbl

[10] P. Brass, W. Moser, J. Pach, Research problems in discrete geometry, Springer-Verlag, New York, 2005 | MR | Zbl

[11] H. G. Eggleston, Convexity, Cambridge Univ. Press, Cambridge, 1958 | MR | Zbl

[12] H. Lenz, “Zerlegung ebener Bereiche in konvexe Zellen von möglichst kleinem Durchmesser”, Jber. Deutsch. Math. Verein., 58 (1956), 87–97 | MR | Zbl

[13] H. Lenz, “Über die Bedeckung ebener Punktmengen durch solche kleineren Durchmessers”, Arch. Math. (Basel), 7:1 (1956), 34–40 | DOI | MR | Zbl

[14] H. Hadwiger, H. Debrunner, Kombinatorische Geometrie in der Ebene, Institut de Math., Genève, 1960 | MR | MR | Zbl

[15] M. Dembiński, M. Lassak, “Covering plane sets with sets of three times less diameter”, Demonstratio Math., 18:2 (1985), 517–526 | MR | Zbl

[16] B. Weissbach, “Polyhedral covers”, Intuitive geometry (Siófok, Hungary, 1985), Colloq. Math. Soc. Janos Bolyai, 48, North-Holland, Amsterdam, 1987, 639–646 | MR | Zbl

[17] V. V. Makeev, “Universal coverings and projections of bodies of constant width”, J. Soviet Math., 59:2 (1992), 750–752 | DOI | MR | Zbl | Zbl

[18] J. Pál, “Über ein elementares Variationsproblem”, Bull. de l'Acad. de Dan, 3:2 (1920), 1–35 | Zbl

[19] A. M. Raigorodskii, Khromaticheskie chisla, MTsNMO, M., 2003