Covering problem of Rado

Covering problem of Rado

The covering problem of Rado is an unsolved problem in geometry concerning covering planar sets by squares. It was formulated in 1928 by Tibor Radó and has been generalized to more general shapes and higher dimensions by Richard Rado.

Formulation

In a letter to Wacław Sierpiński, motivated by some results of Giuseppe Vitali, Tibor Radó observed that for every covering of a unit interval, one can select a subcovering consisting of pairwise disjoint intervals with total length at least 1/2 and that this number cannot be improved. He then asked for an analogous statement in the plane.

If the area of the union of a finite set of squares in the plane with parallel sides is one, what is the guaranteed maximum total area of a pairwise disjoint subset?

Radó proved that this number is at least 1/9 and conjectured that it is at least 1/4 a constant which cannot be further improved. This assertion was proved for the case of equal squares independently by A. Sokolin, R. Rado, and V. A. Zalgaller. However, in 1973, Miklós Ajtai disproved Radó's conjecture, by constructing a system of squares of two different sizes for which any subsystem consisting of disjoint squares covers the area at most 1/4 − 1/1728 of the total area covered by the system.

Upper and lower bounds

Problems analogous to Tibor Radó's conjecture but involving other shapes were considered by Richard Rado starting in late 1940s. A typical setting is a finite family of convex figures in the Euclidean space Rd that are homothetic to a given X, for example, a square as in the original question, a disk, or a d-dimensional cube. Let

 F(X)=\inf_{S}\sup_{I}\frac{|I|}{|S|},

where S ranges over finite families just described, and for a given family S, I ranges over all subfamilies that are independent, i.e. consist of disjoint sets, and bars denote the total volume (or area, in the plane case). Although the exact value of F(X) is not known for any two-dimensional convex X, much work was devoted to establishing upper and lower bounds in various classes of shapes. By considering only families consisting of sets that are parallel and congruent to X, one similarly defines f(X), which turned out to be much easier to study. Thus, R. Rado proved that if X is a triangle, f(X) is exactly 1/6 and if X is a centrally symmetric hexagon, f(X) is equal to 1/4.

In 2008, Sergey Bereg, Adrian Dumitrescu, and Minghui Jiang established new bounds for various F(X) and f(X) that improve upon earlier results of R. Rado and V. A. Zalgaller. In particular, they proved that

 \frac{1}{8.4797}\leq F(\textrm{square})\leq\frac{1}{4}-\frac{1}{384},

and that f(X)\geq\frac{1}{6} for any convex planar X.

References

  • Ajtai, M., The solution of a problem of T. Rado, Bulletin de l’Académie Polonaise des Sciences, Série des Sciences Math. Astr. et Phys. 21, 61–63 (1973)
  • Bereg, Sergey, Dumitrescu, Adrian, Jiang, Minghui, On covering problems of Rado, in Algorithm theory — SWAT 2008, ed by J. Gudmunsson, Lect. Notes in Comp. Sci. 5124, 294–305 (2008), Springer ISBN 978-3-540-69900-2
  • Croft, H.T., Falconer, K.J., Guy, R.K., Unsolved Problems in Geometry, Springer, New York (1991)
  • Radó, T, Sur un problème relatif à un théorème de Vitali, Fundamenta Mathematica 11, 228–229 (1928)
  • Rado, R., Some covering theorems (I), (II), Proc. of the London Math. Soc. 51, 241–264 (1949) and 53, 243–267 (1951)

Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • Differential geometry of surfaces — Carl Friedrich Gauss in 1828 In mathematics, the differential geometry of surfaces deals with smooth surfaces with various additional structures, most often, a Riemannian metric. Surfaces have been extensively studied from various perspectives:… …   Wikipedia

  • Matroid — In combinatorics, a branch of mathematics, a matroid (  /ˈmeɪ …   Wikipedia

  • Terapia de reorientación sexual — La terapia de reorientación sexual (también conocida como terapia reparativa o terapia de conversión) se refiere a una serie de métodos enfocados al cambio de la orientación sexual de homosexuales y bisexuales para convertirlos en personas… …   Wikipedia Español

  • Pottery — Pot and Pots redirect here. For Pot, see Pot (disambiguation). For POTS, see POTS (disambiguation). Unfired green ware pottery on a traditional drying rack at Conner Prairie living history museum …   Wikipedia

  • Jehovah's Witnesses and child sex abuse — As with other religious organisations, Jehovah s Witnesses have been obliged in recent years to develop child protection policies to deal with cases of child abuse in their congregations.Details of the policy have been published in Jehovah s… …   Wikipedia

  • Slovenia — /sloh vee nee euh, veen yeuh/, n. a republic in SE Europe: formerly part of Yugoslavia. 1,945,998; 7819 sq. mi. (20,250 sq. km). Cap.: Ljubljana. * * * Slovenia Introduction Slovenia Background: The Slovene lands were part of the Holy Roman… …   Universalium

  • Deaths in 2003 — Contents 1 January 2003 2 February 2003 3 March 2003 4 A …   Wikipedia

  • Herzog–Schönheim conjecture — In mathematics, the Herzog–Schönheim conjecture is a combinatorial problem in the area of group theory.Let G be a group, and let:A={a 1G 1, ldots, a kG k}be a finite system of left cosets of subgroupsG 1,ldots,G k of G.In 1974 M. Herzog and J.… …   Wikipedia

  • The Great Global Warming Swindle — infobox television caption = DVD cover show name = The Great Global Warming Swindle format = Documentary runtime = 75 mins creator = Martin Durkin country = United Kingdom network = Channel 4, 8 March, 2007 Original run = March 8 2007 website =… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”