Дискретные трансверсали выпуклых множеств тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Акопян, Арсений Владимирович

• Акопян, Арсений Владимирович
• кандидат физико-математических наук
• 2010

Оглавление диссертации кандидат физико-математических наук Акопян, Арсений Владимирович

Используемые обозначения

Введение

ГЛАВА 1. Разбиение и покрытие множеств с общими ограничениями

1.1. Разбиение на части с ограниченным суммарным диаметром

1.2. О покрытии кругами множеств с (р, 2)г/-свойствами.

1.3. О трансверсалях семейства параллелепипедов с параллельными рёбрами.

1.4. Раскрашенная теорема Юнга и связанные с ней задачи.

ГЛАВА 2. РЬ-изометрпп

2.1. Определения и основные свойства.

2.2. Р£-1130метрия в классических однородных пространствах

2.3. Кусочно-лпнейнын аналог теоремы Киршбрауна.

ГЛАВА 3. РЬ-аналог теоремы Нэша-Кенпера

3.1. Формулировки основных результатов.

3.2. Доказательство для евклидовых полиэдральных пространств

3.3. Случаи полиэдральных пространств постоянной кривизны.

Введение диссертации (часть автореферата) на тему «Дискретные трансверсали выпуклых множеств»

Данная диссертация посвящена задачам о существовании конечных ' трансверсалей у семейств множеств. Работа состоит из трёх глав.

В первой главе исследуются такие классические вопросы дискретной геометрии, как существование трансверсали семейства выпуклых множеств и покрытия множеств кругами или транслятами выпуклого тела.

Во второй главе рассматриваются вопросы, связанньш с PL-нзометрпеп, то есть кусочно-линейным отображением, сохраняющем длины всех кривых. Также доказывается кусочно-линейный аналог теоремы Кпршбрауна, о продолжении сжимающего отображения. Теорема Кпршбрауна тесно связана с теоремой Хелли, то есть с существованием 1-трансверсалп у семейства шаров.

В третьей главе доказан кусочно-линейный аналог теоремы Нэша-Кенпера. Этот вариант теоремы можно интерпретировать, как существование конечной трансверсали для семейства шаров в метрических пространствах специального вида.

Напомним формулировку классической теоремы Хелли. Здесь и далее через Е'' будем обозначать ¿/-мерное евклидово пространство.

Теорема Хелли. Если & семейство выпуклых компактных множеств в Ef/ такое, что пересечение любых d + 1 из них не пусто, то пересечение всех множеств из & не пусто.

Естественным является следующий вопрос: каким требованиям должно удовлетворять семейство множеств, чтобы его можно было разбить на к частей, каждая из которых имеет непустое пересечение. В этом случае, множество из к точек «протыкающих» (piercing) всё множество называют /¿-трансверсалыо.

Вопросы о существовании /¿-трансверсали семейства выпуклых множеств тесно связаны с вопросами о покрытие произвольных множеств выпуклыми.

В. Клн [22] показал, что для любого N существует семейство выпуклых множеств на плоскости, такое что, для любых N из них существует 2-трансверсаль, однако для всего семейства множеств такая трансверсаль не существует. Данный пример показывает, что в общем случае не существует прямого обобщения теоремы Хеллн на случай /¿-трансверсали для произвольного семейства выпуклых множеств. Поэтому следует накладывать ряд ограничений на рассматриваемые семейства.

Если взять семейство транслятов или гомотетов некоторого компактного выпуклого множества или семейство параллелепипедов с параллельными рёбрами, то ряд положительных результатов может быть получен.

Л.Данцер и Б.Грюнбаум [6] доказали, что при некоторых натуральных (I и к существует аналог теоремы Хелли для семейства параллелепипедов с параллельными рёбрами в Ес/. Они нашли все такие й и к, тем самым полно-" стыо решив данную задачу. Также М. Качальскип и Д. Наштир [20] показали, что если любые девять треугольников из семейства гомотетов некоторого треугольника на плоскости имеют 2-трансверс;аль, то всё семейство имеет 2-трансверс;аль.

Г. Хадвигером и Г. Дебруннером [47] была также поставлена следующая задача. Существует ли и чему равно число М(р. д, с!) — наименьшее натуральное число такое, что если любое семейство выпуклых компактных .множеств в Ес/, обладающее свойством, что любое его подсемейство из р элементов имеет q элементов с непустым пересечением, то всё семейство в? имеет М(р, д, с/)-трансверсаль.

Ими было доказано, что М(р, д. с/) ^ р — д + 1, а также равенство

М(р, с?) = р - ^ + 1, если с1 + 1 < Я < Р < ^ <7 - (с/ + 1).

Ц X

Легко видеть, что если д = с/, то д, с/) — со. Примером служит множество гиперплоскостей общего положение. Среди них, любые с/ имеют непустое пересечение, однако их все невозможно разбить на конечное число подсемейств с непустым пересечением.

Существование чисел М(р, д, (£) для любых р ^ д > 1 было доказано Н. Алоном н Д. Клейтманом [1,2]. Полученные в этой работе оценки очень грубы.

Данные оценки можно существенно улучшить, если наложить ограничения на семейства рассматриваемых выпуклых компактных множеств. Р. Ка-расёв [18] показал, что М(2,2,2) = 3 для семейства транслятов выпуклой фигуры на плоскости.

В диссертации получены некоторые точные значения М(р, д, 2) для семейства равных кругов на плоскости.

Д. Фон-Дер-Флаас и А. Косточка [14] уточнили верхнюю оценку на М(р, 2, с/) для семейства параллелепипедов с параллельными рёбрами в Е^

2, с1) ^ (р - 1) 1оё^1(Р - 1) + с1 - \{р - 1) \о&2Ь> ~ !)•

В это1"1 же работе, они показали, что М(р, 2,2) ^

В работе улучшена верхняя оценка М(р, 2, сГ) для такого семейства.

Другой путь обобщения теорем типа Хеллп предложили Л. Ловас и И. Ба-рани [3]. Они рассмотрели «раскрашенные» («цветные») версии классических теорем комбинаторной геометрии. В частности, доказали «раскрашенную» версию теоремы Хеллп.

В данной работе доказывается «раскрашенный» вариант теоремы Юнга.

Вторая глава посвящена вопросам связанным с сжимающими отображениями. теоремой Кпршбрауна и РЬ-пзометрпей.

Отображение одного метрического пространства в другое называется сжимающим, если оно не увеличивает расстояние между любыми двумя точками.

М. Кпршбраун [21] доказал, что для любого сжимающего отображения <£>' : Л —У Е^, где Л С Е(/, существует такое сжимающее отображение <р : Ес1 Е(/, что <р'{х) =

Ф. Валентайн в серии работ [31-33] рассмотрел несколько обобщений этой теоремы, в частности, доказал её аналог для гиперболического пространства. Другие доказательства теоремы Киршбрауна, а также их обобщения были получены Е. Майклом [26], И. Шёнбергом [30], Б. Грюнбаумом [16].

У. Ланг и В. Шрёдер [24] доказали существование продолжения сжимающего отображения между пространствами с ограниченной по Александрову кривизной.

Из теоремы Хелли сразу следует, что теорем}' Киршбрауна достаточно доказывать для таких множеств Л, что \Л\ ^ с/ + 1.

Определение 2.2. РЬ-изометрией называется РР-отображеиие, сохраняющее длины всех кривых. Иначе говоря, если Т-Ч н Т>2 полиэдральные пространства (см. например [35]), то отображение <р : V2 называется РЬ-изометрией, если ограничение р на каждый симплекс некоторой локально конечной триангуляции "Р\ есть изометрия.

Разные свойства РЬ-нзометрии были исследованы в работе Дж. Лоуренса н Дж. Спннгарта [25]. В 1981-ом году У. Брем [5] показал, что существует Р£-изометрия, решающая задачу о продолжение Киршбрауна для конечного множества точек.

РЬ-изометрия может интерпретироваться как обобщение оригами. Поэтому классические задачи, связанные с оригами (см. например [9,46]), могут рассматриваться как задачи о РР-пзометрии. В работе было предложено решение известной задачи М. Гарднера [38] об «одном разрезе» для РЬ-изометрий.

В третьей главе доказывается кусочно-линейный вариант знаменитой теоремы Нэша-Кейпера [42,45] об аппроксимации гладкого вложения риманова многообразия в Е(/ гладким изометрическим вложением.

Естественными являются обобщения данной теоремы, где вместо гладких изометрических вложений рассматривается более широкий класс отображений, сохраняющих длины кривых.

Для произвольных сжимающих отображений обобщение теоремы Нэша-Кейпера было получено М. Громовым [39]. Он доказал, что если М.\ и М.2 римановы многообразия, причём сИт(Л41) ^ с1гт(ЛЛо), то любое сжимающее отображение / : ЛЛ\ —> АЛо можно аппроксимировать отображением цэ : АЛ\ —> -М2, сохраняющим длины всех кривых.

Ю. Д. Бураго и В. А. Залгаллер [37] доказали кусочно-линейный вариант теоремы Неша-Кеипера для двумерных РР-многообразий.

С. Крат, А. Петрунин и Д. Бураго [23] доказали кусочно-линейный вариант теоремы Громова, а именно показали, что любое сжимающее отображение f двумерного полиэдрального пространства Р в Е2 может быть аппроксимировано РР-изометрией, то есть для любого г > 0 существует РР-изометрня (рЕ : V —У Е2, что с1(/(х),1рЕ(х)) < в для всех х из V.

В диссертации эта теорема обобщается для произвольных размерностей. При доказательстве этого утверждения используются результаты второй главы о РЬ варианте теоремы Киршбрауна.

Как будет показано, данная задача связана с задачами о увеличении объёма многогранника. Д. Бликер [4] первым заметил, что для любого тетраэдра существует невынуклый-многограннпк, ограничивающий больший объём, поверхность которого изометрпчна (по внутренней метрике) поверхности тетраэдра. Пользуясь методом Блнкера. Г. Самарин [29] доказал аналогичное утверждение для всех выпуклых многогранников в трёхмерном пространстве. Одновременно этот результат был обобщён И. Паком [27].

В работе доказаны ослабленная версия теоремы Бликера-Пака-Самарина для произвольных размерностей.

Список литературы диссертационного исследования кандидат физико-математических наук Акопян, Арсений Владимирович, 2010 год

1. Alon N., Kleitman D. J. Piercing convex sets and the Hadwiger-Debrunner (p> q)-problem // Advances in Mathematics. 1992. Vol. 96, no. 1. Pp. 103112.

2. Alon N., Kleitman D. J. A purely combinatorial proof of the Hadwiger Debrunner (p, q)-conjecture // Electr. J. Comb. 1997. Vol. 4, no. 2.

3. Barany I. A generalization of Caratheodory's theorem // Discrete Mathematics. 1982. Vol. 40, no. 2-3. Pp. 141-152.

4. Bleeeker D. D. Volume increasing isometric deformation of convex polyhedra // Journal of Differential Geometry. 1996. Vol. 43, no. 3. Pp. 505526.

5. Brelnn U. Extensions of distance reducing mappings to piecewise congruent mappings on Шт // Journal of Geometry. 1981. Vol. 16, no. 1. Pp. 187-193.

6. Danzer L., Grunbaum B. Intersection properties of boxes in Ec/. // Combinatorica. 1982. Vol. 2, no. 3. Pp. 237-246.

7. Danzer L., Grunbaum В., Klee V. Helly's theorem and its relatives // Proc. Sympos. Pure Math., Vol. VII. Providence, R. I.: Amer. Math. Soc., 1963. Pp. 101-180.

8. Dekster В. V. The Jung theorem for spherical and hyperbolic spaces // Acta Mathematica Hungarica. 1995. Vol. 67, no. 4. Pp. 315-331.

9. Demaine E. D., Demaine M. L. Fold-and-cut magic // Tribute to a Mathemagician. 2004. Pp. 23-30.

10. Demaine E. D., Demaine M. L. Fold-and-Cut Magic // Tribute to a Mathemagician. А К Peters, 2004. Pp. 23-30.

11. Demaine E. D., Demaine M. L., Lubiw A. Folding and one straight cut suffico // Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms / Society for Industrial and Applied Mathematics. 1999. Pp. 891-892.

12. Demaine E. D., O'Rourke J. Geometric Folding Algorithms: Linkages, Origami, Polyhedra. Cambridge University Press, 2007.—6.

13. Ericson T., Zinoviev V. Codes on Euclidean spheres. North-Holland, 2001.

14. Fon-Der-Flaass D. G., Kostochka A. V. Covering boxes by points // Discrete Mathematics. 1993. Vol. 120, no. 1-3. Pp. 269-275.

15. Gromov M. Partial differential relations. Springer, 1986.

16. Griinbaum B. A generalization of theorems of Kirszbraun and Minty // Proceedings of the American Mathematical Society. 1962. Vol. 13, no. 5. Pp. 812-814.

17. Gyàrfâs A., Lehel J. Covering and coloring problems for relatives of intervals // Discrete Mathematics. 1985. Vol. 55, no. 2. Pp. 167-180.

18. Karascv R. Transversals for families of translates of a two-dimensional convex compact set // Discrete and Computational Geometry. 2000. Vol. 24, no. 2. Pp. 345-354.

19. Kârolyi G. Y. On point covers of parallel rectangles // Periodica Mathematica Hungarica. 1991. Vol. 23, no. 2. Pp. 105-107.

20. Kalchalski M., Nashtir D. On a conjecture of Danzer and Griinbaum // Proceedings of the American Mathematical Society. 1996. Vol. 124, no. 10. Pp. 3213-3218.

21. Kirszbraun M. D. Uber die zusammenziehenden und Lipschitzschen Transformationen // Fund. Math. 1934. Vol. 22. Pp. 77-108.

22. Klec V. Письмо к P.Vincensini от 27 октября. 1954.

23. Krat S., Burago D., Petrunin A. Approximating^ Short Maps by PL-isometies and Arnold's "Can You Make Your Dollar Biegger" Problem.: Ph. D. thesis.

24. Lang U., Schroeder V. Kirszbraun's theorem and metric spaces of bounded curvature // Geom. Funct, Anal. 1997. Vol. 7, no. 3. Pp. 535-560.

25. Lawrence J., Spingarn J. E. An intrinsic characterization of Foldings of Euclidean Space. // Ann. Inst. Henri Poincaré, Analyse non linéaire. 1989. Vol. S6. Pp. 365-383.

26. Mickle E. J. On the extension of a transformation // Bull. Amer. Math. Soc. 1949. Vol. 55. Pp. 160-164.

27. Рак I. Inflating polyhedral surfaces // preprint. 2006.

28. Petrunin A. On intrinsic isometries to Euclidean space // Arxiv preprint arXiv: 1003.5621. 2010.

29. Samarin G. A. Volume increasing isometric deformations of polyhedra // Computational Mathematics and Mathematical Physics. 2010. Vol. 50, no. 1. Pp. 54-64.

30. Sclioonberg I. J. On a theorem of Kirzbraun and Valentine // American Mathematical Monthly. 1953. Vol. 60, no. 9. Pp. 620-622.

31. Valentine F. A. On the extension of a vector function so as to preserve a Lipschitz condition // Bulletin of the American Mathematical Society. 1943. Vol. 49. Pp. 100-108.

32. Valentine F. A. Contractions in non-Euclidean spaces // Bulletin (New Series) of the American Mathematical Society. 1944. Vol. 50, no. 10. Pp. 710713.

33. Valentine F. A. A Lipschitz condition preserving extension for a vector function // American Journal of Mathematics. 1945. Vol. 67, no. 1. Pp. 8393.

34. Zalgaller V. A. Isometric imbedding of polyhedra // Dokl. Akad. Nauk SSSR. 1958. Vol. 123. Pp. 599-601.

35. Вураго Д. Ю., Бураго Ю. Д., Иванов С. В. Курс метрической геометрии. Ижевск: ИКИ, 2004.

36. Бураго Ю. Д. Задача о круге Юнга для сферы // Математическое просвещение. j\2 6. С. 165-169.

37. Бураго Ю. Д., Залгаллер В. А. Изометрические кусочно-линейные погружения двумерных многообразий с полиэдральной метрикой в Ж3 // Алгебра и анализ. 1995. Т. 7, № 3. С. 76-95.

38. Гарднер М. Математические досуги. Оникс М., 1995.

39. Громов М. Дифференциальные соотношения с частными производными. 1990.

40. Данцер Л., Грюнбаум Б., Кли В. Теорема Хелли. 1968.

41. Дольников В. Л. Устное сообщение. 2008.

42. Кейпер Н. X. О С^-изометрических вложениях // Математика. 1957. Т. 1, № 2. С. 17-28.

43. Конвей Д., Слоэн Н. Упаковки шаров, решетки и группы. М.: Мир, 1990.

44. Нарасимхан Р. Анализ на действительных и комплексных многообразиях. М.: Мир, 1971.

45. Нэш Д. О СЯ-изометрическнх вложениях // Математика. 1957. Т. 1, № 2. С. 3-16.

46. Тарасов А. С. Решение задачи Арнольда «о мятом рубле» // Чебышев-скпп сборник. 2004.— 5. Т. 1, № 9.

47. Хадвигер Г., Дебруннер Г. Комбинаторная геометрия плоскости. 1965.