Покрытие проблемы Rado - Covering problem of Rado

В прикрытие проблемы Rado это нерешенная проблема в геометрия о покрытии квадратами плоских множеств. Он был сформулирован в 1928 г. Тибор Радо и был обобщен на более общие формы и более высокие измерения Ричард Радо.

Формулировка

В письме к Вацлав Серпинский, мотивированные некоторыми результатами Джузеппе Витали, Тибор Радо заметил, что для каждого покрытие единичного интервала можно выбрать подпокрытие, состоящее из попарно непересекающихся интервалов общей длиной не менее 1/2, и это число не может быть улучшено. Затем он попросил аналогичное заявление в самолете.

Если площадь объединения конечного множества квадратов на плоскости с параллельными сторонами равна единице, какова гарантированная максимальная общая площадь попарно непересекающегося подмножества?

Радо доказал, что это число не меньше 1/9, и предположил, что это не менее 1/4 константа, которую нельзя улучшить. Это утверждение для случая равных квадратов независимо доказали А. Соколин, Р. Радо и Залгаллер В. А.. Однако в 1973 г. Миклош Айтай опровергнутый Гипотеза Радо, построив систему квадратов двух разных размеров, для которой любая подсистема, состоящая из непересекающихся квадратов, покрывает площадь не более 1/4 - 1/1728 от общей площади, покрываемой системой.

Верхняя и нижняя границы

Проблемы, аналогичные гипотезе Тибора Радо, но с участием других форм, рассматривал Ричард Радо, начиная с конца 1940-х годов. Типичная установка - это ограниченное семейство выпуклые фигуры в Евклидово пространство р^d которые гомотетичный к данному Икс, например, квадрат как в исходном вопросе, диск, или d-размерный куб. Позволять

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

куда S пробегает только что описанные конечные семейства, и для данного семейства S, я распространяется по всем подсемействам, которые независимый, т.е. состоят из непересекающихся множеств, а столбцы обозначают общий объем (или площадь в плоском случае). Хотя точное значение F(Икс) не известна ни для каких двумерных выпуклых Икс, много работы было посвящено установлению верхних и нижних оценок для различных классов фигур. Рассматривая только семейства, состоящие из множеств, параллельных и конгруэнтных Икс, аналогично определяется ж(Икс), который оказался намного проще в изучении. Таким образом, Р. Радо доказал, что если Икс это треугольник, ж(Икс) ровно 1/6 и если Икс центрально симметричный шестиугольник, ж(Икс) равно 1/4.

В 2008 году Сергей Берег, Адриан Думитреску и Минхуэй Цзян установили новые границы для различных F(Икс) и ж(Икс), улучшающие предыдущие результаты Р. Радо и В. А. Залгаллера. В частности, они доказали, что

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

и это ${displaystyle f (X) geq {frac {1} {6}}}$ для любого выпуклого плоского Икс.

Рекомендации

• Айтай М., Решение проблемы Т. Радо, Bulletin de l’Académie Polonaise des Sciences, Série des Sciences Math. Astr. et Phys. 21, 61–63 (1973)
• Берег, Сергей, Думитреску, Адриан, Цзян, Минхуэй, О освещении проблем Rado, в теории алгоритмов - SWAT 2008, под ред. Дж. Гудмунссона, Lect. Примечания в комп. Sci. 5124, 294–305 (2008), Springer ISBN  978-3-540-69900-2
• Крофт, Х.Т., Фальконер, К.Дж., Гай, Р.К., Нерешенные задачи геометрии, Спрингер, Нью-Йорк (1991)
• Радо, Т, Sur un problème relatif à un teorème de Vitali, Fundamenta Mathematicae 11: стр. 228–229 (1928).
• Радо, Р., Некоторые теоремы о покрытии (I), (II), Proc. Лондонской математики. Soc. 51, 241–264 (1949) и 53, 243–267 (1951).
• Залгаллер В.А., Замечания по проблеме Rado , Математическое просвещение, 5, 141–148 (1960)