Проблема покрытия Rado

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

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

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

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

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

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

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

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

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

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

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

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

Ссылки

• Айтай, Миклош (1973), «Решение проблемы Т. Радо», Вестник Польской академии наук, Серия математических, астрономических и физических наук , 21 : 61–63, MR   0319053
• Берег, Сергей; Думитреску, Адриан; Цзян, Минхуэй (2010), «О покрытии проблем Rado», Algorithmica , 57 (3): 538–561, doi : 10.1007/s00453-009-9298-z , MR   2609053 ; предварительное объявление в SWAT 2008 , дои : 10.1007/978-3-540-69903-3_27
• Крофт, Халлард Т.; Фальконер, Кеннет Дж .; Гай, Ричард К. (1991), Нерешенные проблемы по геометрии , Сборники задач по математике, Нью-Йорк: Springer-Verlag, doi : 10.1007/978-1-4612-0963-8 , ISBN  0-387-97506-3 , МР   1107516
• Радо, Тибор (1928), «О проблеме, связанной с теоремой Витали» , Fundamenta Mathematicae , 11 : 228–229, JFM   54.0098.02
• Радо, Ричард (1949), «Некоторые покрывающие теоремы (I)», Труды Лондонского математического общества , вторая серия, 51 : 232–264, doi : 10.1112/plms/s2-51.3.232 , MR   0030782
  —— (1951), «Некоторые покрывающие теоремы (II)», Труды Лондонского математического общества , вторая серия, 53 : 243–267, doi : 10.1112/plms/s2-53.4.243 , MR   0042149
• Соколин А. (1940), «К проблеме Радо», Известия АН СССР , 26 : 871–872, Zbl   0023.11203
• Zalgaller, V. A. (1960), "Замечания о задаче Радо" , Математика, ее преподавание, приложения и история , Matematicheskoe Prosveshchenie, Ser. 2 (in Russian), vol. 5, pp. 141–148, Zbl  0145.19203