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

На правах рукописи

00461ОИОО

Акопян Арсений Владимирович

ДИСКРЕТНЫЕ ТРАНСВЕРСАЛИ ВЫПУКЛЫХ МНОЖЕСТВ

Специальность

01.01.09 - Дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание учёной степени кандидата физико-математических наук

Ярославль - 2010

- 2 пек 2010

004615038

Работа выполнена в Учреждении Российской икадемт наук Институте системного анализа РАН.

Научные руководители:

Официальные оппоненты:

Ведущая организация:

доктор физика-матшагпических паук, профессор Владимир Леонидович Дольников доктор физико-математических наук, профессор Александр Петрович Афанасьев доктор физико-математических наук, профессор Николай Петрович Долбилип кандидат физико-математических наук, доцент Роман Николаевич Карассв Московский государственный, университет имени М. В. Ломоносова

Защита состоится 28 декабря 2010г. в 16:00 на заседании диссертационного попета Д 212.002.03 при Ярославском государственном университете им.. П. Г. Демидова, расположенном по адресу: 150008 г. Ярославль, ул. Союзная, д. 144, аудитория 426.

С диссертацией можно ознакомиться в библиотеке Ярославского государственного университета им. П. Г. Демидова.

Автореферат разослан ок-тъ- /^о < 2010г.

"Ученый секретарь диссертационного совета ¿¡¿З^^ Яблокова С. И.

Общая характеристика работы

Актуальность темы

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

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

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

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

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

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

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

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

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

'Klee V. Письмо к P.Vincensim от 27 октября 1954г.

сгвует 2-трансверсаль, но для всего семейства множеств такая трансверсаль не существует. Данный пример показывает, что в общем случае не существует прямого обобщения теоремы Хелли па случай к-трансвсрсали для произвольного семейства выпуклых множеств. Поэтому следует накладывать ряд ограничений на рассматриваемые семейства.

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

Л.Данцер и Б.Грюнбаум2 доказали, что при некоторых натуральных d и к существует аналог теоремы Хелли для семейства параллелепипедов с параллельными рёбрами в Ed. Они нашли все такие d ц к, тем самым полностью решив данную задачу. Также М. Качаль-скнй и Д. Каштир3 показали, что если любые девять треугольников из семейства гомотетов некоторого треугольника на плоскости имеют 2-трансверсаль, то всё семейство имеет 2-трансверсаль.

Г. Хадвцгером и Г. Дебруннером4 была также поставлена следующая задача. Существует ли и чему равно число M(p,q,d) — наименьшее натуральное число такое, что если любое семейство выпуклых компактных множеств в Erf. обладающее свойством, что любое сто подсемейство из р элементов имеет q элементов с непустым пересечением, то всё семейство & имеет M{р, q, ¿)-трансверсаль.

Ими было доказано, что M(p>q,d) ^ р - q + 1, а также равенство

M (p. q,d)=p-q + l. если d+ ~ + 1).

а — 1

Легко видеть, что если q < d, то М(р, q, d) = оо.

Существование чисел М(р, q, d) для любых р Js q > d + 1 было

2Danzer L., Griinba-am В. Intersection properties of boxes in // Combinatorica. 1982. Vol. 2, no. З.Рр. 237 246.

JI<atchalski M., Nashtir D. On a conjecture of Danzer and Griinbaum // F'roceedings of the American Mathematieal Society. 1996. Vol. 124, no. 10. Pp. 32133218.

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

доказало0 Н. Алоггом и Д. Клейтманом. Полученные в этой работе оценки очень грубы.

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

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

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

М(р,2,d) £ (р - 1) iogpL(p _ l) + d - i(p - 1) Iog^2(p - .1).

В этой же работе они показали, что М(р, 2,2) j^f-j ■

В диссертации улучшена верхняя оценка M(p,2,d) для таких семейств.

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

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

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

'Alon N.. Kleitman D. Piercing convex sets and the Hadwiger-Debrunner (p, q)-problcm // Advances in Mathematics. 1992. Vol. 96, no. 1. Pp. 103-112.

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

6Karasev R. IVansversals for families of translates of a two-dimensional convex compact set // Discrete and Computational Geometry. 2000. Vol. 24, no. 2. Pp. 345354.

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

8Barrfny I. A generalization of Carat neodory's theorem //Discrete Mathematics. 1982. Vol. 40, no. 2-3. Pp. 141-152.

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

М. Киршбраун9 в 1934 году доказал, что для любого сжимающего отображения </?' : Л -> Ed, где А С Ed, существует такое сжимающее отображение <р : Ed Ed, что <р'(х) = у>(я)Ц.

Ф. Валентайн в серии работ10 рассмотрел несколько обобщений этой теоремы, в частности, доказал её аналог для гиперболического пространства. Другие доказательства теоремы Киршбрауна, а также их обобщения были получены Е. Майклом11, И. Шёнбергом12. Б. Грюнбаумом1".

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

Из теоремы Хелли сразу следует, что теорему Киршбрауна достаточно доказывать для таких множеств А что |Л| d, + 1.

Определение 2.2. PL-изометрией называется Р/.-отображение, сохраняющее длины всех кривых. Иначе говоря, если V\ и 'Pi полиэдральные пространства (см. например15), то отображение tp : "Pi —> Vi называется PL-изометрией, если ог раничение 9 на каждый симплекс

°Kirszbraun М. Uber die zusammenziehenden unci Lipschitzschen Transformationen // Fund. Math. 1934. Vol. 22.Pp. 77-108.

10 Valentine F. A. On the extension of a vcetor function so as to preserve a Lipschitz condition /' Bulletin of the American Mathematical Society. 1943. Vol. 49. Pp. 100108.

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

Valentine F. A. A Lipschitz condition preserving extension for a vector function // American Journal of Mathematics. 1945. Vol. 67, 110. 1. Pp. 83-93.

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

12Schoenberg I. On a theorem of Kirzbraun and Valentine // American Mathematical Monthly, 1953. Vol. GO, no. 9. Pp. 620-622,

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

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

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

некоторой локально конечной триангуляции V\ есть изометрия.

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

PL-изометрия может интерпретироваться как обобщение оригами. Поэтому классические задачи, связанные с оригами (см. например18), могут рассматриваться как задачи о PL-изометрия. В работе было предложено решение известной задачи М. Гарднера19 об «одном разрезе» для PL-изомстрий.

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

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

Для произвольных сжимающих отображений обобщение теоремы Нэша-Кейпера было получено М. Громовым21. Он доказал, что если Л4\ и М2 римановы многообразия, причём dim(M i) ^ dim(M2)• то любое сжимающее отображение / : Mi -* Мч можно аппроксимировать отображением : Mi -> М2, сохраняющим длины всех кривых.

Ю. Д. Бураго и В. А. Зал галл ер22 доказали кусочно-линейный

lbLawrence Л., Spingaru J. An intrinsic characterization of Foldings of Euclidean

Space. // Ann. Inst. Henri Poiucare, Analyse uon Unenire. 1989. Vol. S6. Pp. 365-

383.

1'Brehm U. Extensions of distance reducing mappings to piecewise congruent

mappings on R'n /7 Journal of Geometry. 1981. Vol. 16,110. 1. Pp. 187-193.

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

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

10Гарднер M., Смородинский Я. А., Данилов Ю. А. Математические досуги Оникс М.: 1995.

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

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

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

22Бураго Ю. Д., Залгаллер В. А. Изометрические кусочно-линейные погруже-

вариант теоремы Нсша-Кейпера для двумерных PL-многообразий.

С. Крат, А. Петрунин и Д. Бураго2'* доказали кусочно-линейный вариант теоремы Громова, а именно показали, что любое сжимающее отображение / двумерного полиэдрального пространства V в Е2 может быть аппроксимировано PL-изометрисй, то есть для любого е > 0 существует PL-изометрия щ : V Е2, что d(f(x),ipe{x)) < г для всех х аз V.

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

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

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

Цель работы

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

ни я двумерных многообразий с полиэдральной метрикой в К15 /'/ Алгебра ц анализ. 1935. Т. 7, № 3. С. 76-95.

A,Krat S., Burago D., Petrunin A. Approximating® Short Maps by PjWsomctics and Arnold's "'Can You Make Your Dollar Biegger" Problem.: Ph.D. thesis.

~1Bleecker D. Volume increasing isometric deformation of convex polyhedra /,' .'Journal of Differential Geometry. 1996. Vol. 43, no. 3. Pp. 505-526.

2r'Samarin G. A. Volume increasing isometric deformations of polyhedra // Computational Mathematics and Mathematical Physics. 2010. Vol. 50, no. 1. Pp. 5464.

2fiPak I. Inflating polyhedral surfaces ,//' preprint.2006.

диаметров частей. Получить обобщение теоремы Юнга на случай покрытия множеств несколькими шарами, а также раскрашенную теорему Юнга.

2. Доказать ряд свойств РЬ-изометрии в гиперболических пространствах. Дать конструктивное доказательство теоремы Киршбра-уна для случая конечного числа точек в гиперболическом пространстве.

3. Применить разработанную в диссертации технику для доказательства дискретного аналога теоремы Нэша-Кейттера. Доказать, что для любого выпуклого многогранника существует кусочно-линейно нзометричный ему «псевдомногогранник» большего объёма.

Основные методы исследования

В первой главе диссертации используются классические методы дискретной, метрической и выпуклой геометрии и теории графов.

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

Научная новизна

Основные результаты диссертации являются новыми и состоят в следующем:

1. Улучшена оценка на мощность трансверсали для семейства параллелепипедов в таких, что среди любых р из них два имеют не пустое пересечение или. другими словами, любые р имеют (р— 1 )-трансверсаль. Усилины оценки на мощность трансверсали семейства равных кругов на плоскости.

2. Показано, что при некоторых естественных условиях на множество в метрическом пространстве, существует разбиение этого множества на несколько частей с ограниченным суммарным диаметром. Найдены следствия из этой теоремы.

3. Дано конструктивное доказательство теоремы Киршбрауна для конечного множества точек в пространстве Лобачевского. Найдены следствия из этой теоремы.

4. Доказано, что любое сжимающее отображение полиэдра в пространство постоянной кривизны не меньшей размерности допускает аппроксимацию кусочно-линейной изометрией.

Теоретическая и практическая ценность

Диссертация имеет теоретический характер,

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

Результаты второй и третьей главы диссертации могут быть использованы при исследовании сжимающих отображений PL и рима-повых многообразий, а также в теории многогранников.

Апробация результатов

Основные результаты диссертации неоднократно докладывались на семинаре «Дискретная геометрия и геометрия чисел» под руководством Н. П. Долбилина, Н. Г. Мощевитина и М. Д. Ковалева (мех-мат МГУ, 2006-2009 гг.); На семинаре «Арифметика и геометрия» под руководством Н. Г. Мощевитина и А. М. Рай городского (мех-ма.т МГУ, 2006 г.); На геометрическом семинаре под руководством И. X. Сабитова и В. Ю. Протасова (МЦМНО, 2007-2010гг.); На геометрическом семинаре ПОМИ РАН им. А. Д. Александрова под руководством Ю. Д. Бураго (ПОМИ РАН, 2008 г.).

Также результаты диссертации докладывались на следующих международных конференциях и семинарах: IX Международный семинар «Дискретная математика и её приложения», посвященный 75-летию со дня рождения академика О.Б. Лупанова, Москва (2007); Mathematics research seminar. UTB, Brownsville, USA (2009-2010); Combinatoire Algébrique et Géométrique, Paris, France (2009); Workshop on Combinatorial Geometry and Topology, South Padre Island, USA (2009-2010); Workshop "Voronoi-2008" Honoring 140th anniversary of G. F. Voronoi

"Numerical geometry, grid generation and scientific computing" ,Москва (2008); The 17tli Annual Meeting of the South Texas Mathematics Consortium, Edinburg, USA (2009); "Geometry, Topology, Algebra and Number Theory Applications" dedicated to the 120th anniversary of Boris Delone, Москва (2010).

Публикации

Основные результаты диссертации опубликованы в пяти работах, из них три в журналах из перечня ВАК. Список работ приведён в конце автореферата [1-5].

Структура диссертации

Диссертация состоит из введения, трёх глав и списка используемых источников. Полный объём — диссертации 75 страниц, библиография включает 47 наименований.

Краткое содержание работы Во введении даётся обзор результатов по теме диссертации и формулируются основные результаты работы.

В первой главе доказаны различные обобщения теоремы Юнга и связанные с ними результаты.

Определение 1.2. Точки х,у в метрическом пространстве М назовём й-близкими. если (1(х,у) < с?. Будем говорить, что множество V в М (|У| ^ р) обладает (р, с1)-свойством, если среди любых р точек множества. V найдутся д попарно (¿-близких.

Наиболее важным результатом первого параграфа является следующая теорема.

Теорема 1.5. Если множест-во V обладает (р,д,(1)-свойством, то его можно разбить на р — 1 частей с суммой диаметров < Эта теорема имеет несколько следствий.

По теореме Юнга любое множество диаметра (I в Е" может быть покрыто шаром радиуса (1 • у^п+Т) • Поэтому верно следующее следствие теоремы 1.5.

Следствие 1.6. "Пусть множество V в Е" обладает (р,д, с1)-свойством. Тогда 'V можно покрыть р — 1 шарами с суммой радиусов

Кроме того, каждое множество диаметра <], в евклидовом пространстве можно покрыть кубом с рёбрами равными ^ и параллельными осям координат. Значит, верно следующее утверждение.

Следствие 1.7. Если множество V еЕп обладает (р,д, д.)-свойством, то V можно покрыть р — 1 кубами с суммой длин рёбер рёбра

которых параллельны осям координат.

Если рассмотреть граф со стандартной псевдометрикой, то можно получить следующее следствие теоремы 1.5.

Следствие 1.8. Если в конечном графе из любых р вершин можно выбрать (¡-клику, то граф можно разбить па не более чем р — 1 подграфов с сумм,ой диаметров (по внутренней метрике частей) не большей чем

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

Второй и третий параграф посвящен частным случаем задачи Хадви-гера и Дебруннера о М(р, д, с/)-трансверсали.

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

Определение 1.5. Будем говорить, что множество V ( |У| > р) в метрическом пространстве М обладает (р,ц)г-свойством, если любые р точек этого множества можно покрыть д шарами радиуса, г.

Доказаны следующие две теоремы и их следствия. Теорема 1.12 даёт ответ на вопрос Б. Грюнбаума27.

Теорема 1.12. ЕслиУ С Е2 обладает (4,2)г-свойс.твом, то его можно покрыть 4-мя кругами радиуса г. Данное число кругов является наилгеньшим.

Отметим, что Б. Грюнбаум предполагал, что наименьшее число кругов в данном случае равно 6.

27Данцер Л., Грюнбаум В., Кли В. Теорема Хелли // М: Мир. 1968. стр. 104.

Следствие 1.13. Пусть в Е2 дано семейство равных кругов, обладающее свойством, что для любые четыре из них имеют 2-трансверсалъ. Тогда всё семейство имеет, 4-трансосрсаль.

Теорема 1.14. Если V С Е2 обладает (3,2)г-свойством, то его .можно покрыть 6-ю кругами радиуса г. Данное число кругов является наименьшим.

Следствие 1.15. Пусть в Е2 дано семейство равных кругов, что из любых трёх из них два пересекаются. Тогда всё семейство имеет 6-трансвереаль.

Также в этом параграфе уточнён контрпример В. Клп к обобщению теоремы Хелли для fc-трансвсрсали, при k > 1. Теорема 1.16 Для любого N существует семейство из N+1 выпуклого множества на плоскости такое, что для любых N множеств из этого семейства существует 2-трансверсалъ. но для всего семейства 2-трансверсали не существует.

Заметим, что пример В. Кли приводится только для чётных Аг. В третьем параграфе улучшается оценка на число М(р, 2, ci) для семейства параллелепипедов с параллельными рёбрами.

Теорема 1.21. Пусть h(p) — plog а,-др + р. Тогда:

M(p,2,2)^h(p-l).

Теорема 1.22.

М(р, 2, d) < (log з^ 2 + o(l))plogf1 p.

В четвёртом параграфе изучаются ¿-близкие множества.

Определение 1.6. Два непустых множества V\ и V2 в метрическом пространстве М назовём ¿¿-близкими, если d(x,y) ^ d для любых х <Е Vi и у е VV

Доказана следующая теорема, которую можно назвать «раскрашенной теоремой Юнга».

Теорема 1.23. Если в пространстве Е™ задано семейство из k > 1 попарно d-близких множеств Vi, V2, • • ■, Vfc, то одно из множеств

можно покрыть кругом радиуса R, где

В = dесли k ^ п; R — d- yj2(n+i)' если к > Пш

Причем оценка на R является точной.

Обобщения теоремы Юнга для сферического пространства и пространства Лобачевского исследовались в работах Ю. Д. Бураго28 и Б. В. Декстера29. В диссертации доказаны «раскрашенные» версии теоремы Юпга для этих пространств. Для пространства Лобачевского ИГ":

ch R — ch~ d, если fc ^ d\ sh R— y^jy sh f, если k > d.

Для случая множеств в Sn, лежащих внутри некоторой фиксированной единичной полусфере соответствующие радиусы равны:

cos R = cos2 d, если k, < d\ sin R — у sin 5, если k > d.

Очевидно, что если дано несколько попарно (/-близких множеств, то диаметр каждого из них не превосходит 2d. Интересно оценить наименьший из диаметров этих множеств. Оказалось, что данная задача равносильна известной задаче о поиске оптимального антиподального кода-

Определение 1.7. Сферическим кодом называется любое конечное множество различных точек сферы S". Сферический код назовём антиподальпыли если он симметричен относительно центра сферы.

Сферический код W из гп точек называется оптимальным, если он обладает максимальным минимальным диаметром (ттс^О^, у), где х, у € W и х ^ у) среди всех сферических кодов мощности т.

Через Dn{k) будем обозначать минимальный диаметр оптимального антиподального кода мощности 2к на единичной сфере S"-1.

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

JflDekster В. V. The Jung theorem for spherical and hyperbolic spaces // Acta Mathematics Hungarica. 1995. Vol. 67, no. 4. Pp. 315 331.

Теорема 1.25. Earn в пространстве Е™ задано семейство из к > 1 попарно d-близких лтожеств Vj, V2, ..., V&, то диаметр одного из них не. превосходит

, м .

\Л - 0„(Ч2

Причём оценка на D является точной.

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

Наглядным примером PL-изометрпи служит отображение, переводящие обычный лист бумаги в фигуру оригами. Однако, не всегда «PL-изометрия листа бумаги» может быть реализована как оригами.

В первом параграфе приводятся различные примеры двумерных Р£-изометрии и обсуждаются вопросы о том, когда PL-изометрия является оригами, а когда пет.

Во втором параграфе доказывается ряд теорем о PL-изометрии.

Назовём политопом пересечение конечного числа полупространств.

В начале параграфа показывается, что PL-изометрия пространства может рассматриваться, как разрезание данного пространства па выпуклые политопы, называемых листами, на каждом из которых PZ-изометрия является некоторым движением, причём для каждого политопа движения отличаются.

Следующие две теоремы 2.1 и 2.2 для Ed доказали30 Дж. Лоуренс и Дж. Спингарт. В диссертации найдено более короткое и наглядное доказательство этих теорем, что даёт возможность перенести их на пространства Srf и Hd. Обозначим через X одно из пространств Erf, Sd и M1*.

Теорема 2.1. Локально конечное разбиение политопа Р из X на листы является РL-изометрией тогда и только тогда, когда любая грань коразмерности 2, принадлежит, чётному числу листов, причём альтерированная сумма двумерных углов (то есть, соседние углы входят в сумму с разными знаками) при этой грани равна 0.

30Lawrence J., Spingarn J. An intrinsic characterization of Foldings of Euclidean Space. //' Ann. Inst. Henri Poincaré, Analyse non linéaire. 1989. Vol. S6. Pp. 365383.

Теорема 2.2. Отображение ip : V —> X является PL-изометрией тогда и только тогда, когда выполнено следующее требование:

V.t € V,3г(х)Уу е В(х,г(х))31 верно d(x,y) = d(ip(x), ср(у)).

В третьем параграфе приводится доказательство PL-варианта теоремы Киршбрауна, а также некоторых следствий из этой теоремы.

Теорема 2.5. Пусть о пространстве X даны два конечных множества точек А — («1,02, •.. ,an} и Б — • ■ J>n}> причём для любых различных i и j верно d(a.i,a,j) ^ d(bi,bj). Тогда существует PL-изометрия ф : X X такая, что у(а;) — h.

Как оказалось, полученная конструкция PL-изометрии в теореме 2.5 во многом похожа на конструкцию У. Брема1'. Но техника, предложенная автором, в отличии от конструкции Брема, также работает и для пространства Лобачевского.

Следствие 2.6. Пусть в пространстве Е71 ил,и Ип даны два конечных мтжества точек Л — {ау,а2,..., ап} и 8 — {61,62, — 6П}, такие, что для любых г и j выполнено d(ai,aj) ^ d(bubj). Тогда существует такая точка р, что для любого i, выполнено:

d(p,a.i) ^ d{p,bi).

Назовём кусочно-линейной фигурой ограниченное множество на плоскости, граница которого является конечным объединением непересекающихся и несамопсресекающихся замкнутых ломаных.

С помощью теоремы 2.5 можно легко получить решение задачи М. Гарднера19 «об одном разрезе» в классе PL-изометрий. Неформально её можно сформулировать так: для любой наперёд заданной кусочно-линейной фигуры на листе бумаге, существует сгибание этого листа, такое что данная фигура может быть вырезана одним прямолинейным надрезом ножницами.

Теорема 2.7. Для любой кусочно-линейной фигуры существует PL-изометрия ip такая, что границы фигуры отображаются на одну

Я1 Здесь, через В(х,г(х)) обозначается шар с центром в ж и радиуса г(х).

11 Brehm U. Extensions of distance reducing mappings to piecewise congruent mappings on Rm /,/ Journal of Geometry. 1981. Vol. 16, no. 1. Pp. 187-193.

'"Гарднер M, Смородинский Я. А., Данилов Ю. А. Математические досуги. Оникс М., 1995.

прямую, кроме того эта прямая не пересекает, образ внутренностей фигуры.

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

Основным результатом этой главы является следующая теорема.

Теорема 3.7. Пусть V — конечное:32 (1-мерное евклидово полиэдральное пространство, отображение / : V Еп (п ^ <1) является сжимающим. Тогда для любого е > О существует РЬ-изометрия

: V Е" такая, что й(/(х), <ре.{х)) < е для любой точки х из V.

Теоремы 3.18 и 3.17 обобщают этот результат для сферических и гиперболических полиэдральных пространств.

Назовём псевдомногогранником образ РЬ-многообразия гомеоморф-ного сфере при /'¿-отображении в Назовём его объёмом, объём множества точек, которые находятся в разных компонентах связности с бесконечно удаленной точкой.

Теорема 3.11. Для любого выпуклого многогранника Р в пространстве Е* существует, псьвдомногогранник Р'. ограничивающая больший объём чем Р, такой, что поверхность Р' изометрична поверхности Р.

Данная теорема является прямым следствием теоремы 3.7 и теоремы И. Пака26 о существовании поверхности изометричной поверхности выпуклого многогранника Р и, ограничивающей объём больший чем Р.

чо u

то есть сответствующии комплекс состоит из конечного числа многогранников. *'&Pak I. Inflating polyhedral surfaces /'/ preprint.2006.

Публикации автора по теме диссертации

1. Akopyan А. V., Tarasov A. S. PL-analogue for Nash-Kuiper theorem. /,/ Numerical geometry, grid generation and scientific computing. Special event: Workshop "Voronoi-2008". Honoring 140th anniversary of G.F. Voronoi / Ed. by V. Garangza. Y. G. Evtuslienko, N. Weatherill. Издательство Фолиум, 2008.

В данной работе A.C. Тарасову принадлежит постановка задачи. Доказательство основных результатов принадлежит A.B. Акопяну.

2. Акопян А. В. О пересечении параллелепипедов в // Математические заметки. 2008. Т. 83, № 1. С. 153-156.

3. Акопян А. В., Дольников В. Л. Некоторые обобщения диаметра множества и задача Юнга // Моделирование и Анализ Информационных Систем. 2006. Т. 13. С. 66-70.

В данной работе В.Л.Дольникову принадлежит постановка задач. Доказательство основных результатов принадлежит A.B. Акопяну.

4. Акопян А. В., Тарасов А. С. О складывании бумаги, переводящее одно заданное множество точек в другое // Материалы IX Международного семинара «ДИСКРЕТНАЯ МАТЕМАТИКА И ЕЕ ПРИЛОЖЕНИЯ посвященного 75-легию со дня рождения академика O.E. ЛУПАНОВА». 2007. С. 362-363.

В данной работе A.C. Тарасову принадлежит постановка задачи. Доказательство основного результата принадлежит A.B. Акопяну.

5. Акопян А. В.. Тарасов А. С. Конструктивное доказательство теоремы Киршбрауна // Математические заметки. 2008. Т. 84. № 5. С. 781 784.

В данной работе A.C. Тарасову принадлежит постановка задачи. Доказательство основного результата принадлежит A.B. Акопяну.

Отпечатано в копицентре « СТ ПРИНТ » Москва, Ленинские горы, МГУ, 1 Гуманитарный корпус, e-mail: globus9393338@yandex.ru тел.: 939-33-38 Тираж 100 экз. Подписано в печать 25.10.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].

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

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.