Pokrývající problém Rado - Covering problem of Rado

The pokrývající problém Rado je nevyřešený problém v geometrie týkající se zakrytí rovinných sad čtverci. To bylo formulováno v roce 1928 Tibor Radó a byl zobecněn na obecnější tvary a vyšší rozměry pomocí Richard Rado.

Formulace

V dopise Wacław Sierpiński, motivován některými výsledky Giuseppe Vitali, Poznamenal Tibor Radó pro každého krytina jednotkového intervalu lze vybrat subkrytí skládající se z párových disjunktních intervalů s celkovou délkou alespoň 1/2 a že tento počet nelze zlepšit. Poté požádal o analogické prohlášení v letadle.

Pokud je oblast spojení konečné sady čtverců v rovině s rovnoběžnými stranami jedna, jaká je zaručená maximální celková plocha párové disjunktní podmnožiny?

Radó dokázal, že toto číslo je alespoň 1/9, a domníval se, že je to alespoň 1/4 konstanta, kterou nelze dále vylepšovat. Toto tvrzení prokázali pro případ rovných čtverců nezávisle A. Sokolin, R. Rado a V. A. Zalgaller. V roce 1973 však Miklós Ajtai vyvrácen Radóova domněnka, vytvořením systému čtverců dvou různých velikostí, pro který jakýkoli subsystém skládající se z disjunktních čtverců pokrývá oblast maximálně 1/4 - 1/1728 z celkové plochy pokryté systémem.

Horní a dolní mez

Problémy analogické domněnce Tibora Radó, které se však týkaly jiných tvarů, zvažoval Richard Rado od konce 40. let. Typickým prostředím je konečná rodina konvexní postavy v Euklidovský prostor R^d to jsou homotetický k danému Xnapříklad čtverec jako v původní otázce, a disk nebo d-dimenzionální krychle. Nechat

${displaystyle F (X) = inf _ {S} sup _ {I} {frac {| I |} {| S |}},}$

kde S sahá přes právě popsané konečné rodiny a pro danou rodinu S, Já rozsahy přes všechny podskupiny, které jsou nezávislý, tj. skládají se z nesouvislých množin a pruhy označují celkový objem (nebo plochu, v případě roviny). Ačkoli přesná hodnota F(X) není znám pro žádný dvourozměrný konvexní X, mnoho práce bylo věnováno stanovení horních a dolních mezí v různých třídách tvarů. Tím, že vezmeme v úvahu pouze rodiny sestávající ze sad, které jsou paralelní a shodné X, jeden podobně definuje F(X), což se ukázalo být mnohem snazší studovat. R. Rado tedy dokázal, že pokud X je trojúhelník, F(X) je přesně 1/6 a pokud X je centrálně symetrický šestiúhelník, F(X) se rovná 1/4.

V roce 2008 vytvořili Sergey Bereg, Adrian Dumitrescu a Minghui Jiang nové hranice pro různé F(X) a F(X), které zlepšují dřívější výsledky R. Rada a V. A. Zalgallera. Zejména to dokázali

${displaystyle {frac {1} {8.4797}} leq F ({extrm {square}}) leq {frac {1} {4}} - {frac {1} {384}},}$

a to ${displaystyle f (X) geq {frac {1} {6}}}$ pro jakékoli konvexní planární X.

Reference

• Ajtai, M., Řešení problému 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, Na pokrytí problémů Rado, v teorii algoritmu - SWAT 2008, ed. J. Gudmunsson, přednáška. Poznámky v komp. Sci. 5124, 294–305 (2008), Springer ISBN  978-3-540-69900-2
• Croft, H.T., Falconer, K.J., Guy, R.K., Nevyřešené problémy v geometrii, Springer, New York (1991)
• Radó, T, Sur un problème relatif à un théorème de Vitali, Fundamenta Mathematicae 11: str. 228–229 (1928)
• Rado, R., Některé krycí věty (I), (II), Proc. z London Math. Soc. 51, 241–264 (1949) a 53, 243–267 (1951)
• Zalgaller, V.A., Poznámky k problému Rado (v ruštině), Matematicheskoe Prosveshchenie 5, 141–148 (1960)