Теоремы типа Борсука-Улама в комбинаторной и выпуклой геометрии

1.1 Историческая справка.

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

Типичным (и одним их первых) результатом в этом направлении является теорема Брауэра о неподвижной точке [12].

Теорема 1.1 (Теорема Брауэра). Пусть К С М^ выпуклый компакт. Тогда для всякого непрерывного отображения /: К —"• К найдётся неподвижная точка, то есть точка х € К. для которой х = /(ж).

Первые доказательства теоремы Брауэра были основаны на геометрических идеях, или, чуть позже, на использовании комбинаторной леммы Шперпера [53] (см. главу 5). Впоследствии доказательства теоремы Брауэра были переформулированы в рамках топологических препятствий, которые, но сути являются относительными классами Эйлера (см. главу 2 и теоремы 3.1 и 3.2). Осознание наличия гомологического препятствия позволило построить нрактически эффективные алгоритмы нахождения неподвижной точки, см. [16, 36].

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

Теорема 1.2 (О гомотопическом продолжении). Пусть расслоение V —У X имеет ненулевой класс Эйлера. Пусть также гoмomonuяst связывает два сечения этого расслоения во и вь Тогда в пространстве гомотопии X х [0,1] некоторая компонента множества нулей пересекается и с X х {0}, и с X х {1}.

В случае, если X является многообразием размерности п. слои V также имеют размерность п. и гомотопия вь находится в общем положении, утверждение теоремы просто говорит о том, что некоторый нуль во связан гладкой кривой с некоторым нулём 51 в пространстве X х [0,1]. Это наблюдение позволяет построить эффективные вычислительные алгоритмы для нахождения некоторых нулей произвольного сечения 51, если для некоторого фиксированного сечения во все пули известны.

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

Ещё один тип теорем существования в геометрии даёт теорема Хелли [27] и разнообразные её следствия и обобщения.

Теорема 1.3 (Теорема Хелли). Пусть У7 конечное семейство выпуклых множеств в Тогда семейство Т имеет общую точку т, огда и только тогда, когда, всякое подсемейство 0 С Т с Я < с?+ 1 имеет общую точку.

Сама по себе теорема Хелли, в частности, допускает топологическое доказательство (см. [79]) путём рассмотрения нерва покрытия У Т семейством Т7 как симилициального комплекса и рассмотрения гомологий этого комплекса. Также существует доказательство теоремы Хелли через теорему Брауэра.

В литературе «теоремой типа Хелли» называется утверждение о семействе множеств, в котором некоторое свойство семейства выводится из выполнения того же или аналогичного свойства для всех подсемейств фиксированного размера. В частности, изучаются такое свойство, как наличие плоской трансверсали, то есть плоскости заданной размерности, пересекающей все множества семейства. Для плоских трапсверсалей простых обобщений теоремы Хелли не существует (даже в случае трансверсалей прямых), однако разнообразные утверждения типа теоремы Хелли всё же возможны. Некоторые из них рассматриваются и в этой работе.

Вернёмся собственно к теореме Хелли. Одним из способов доказательства теоремы Хелли является, применение теоремы Радона [50], более общая формулировка которой доказана Твербергом [58[.

Теорема 1.4 (Теорема Тверберга). Пусть конечное множество X € состоит из (с/+1)(п—1) + 1 точек. Тогда, X можно разбить нап множеств Х,., Хп, выпуклые оболочки которых имеют общую точку.

Позднее в работах Вагапу. БЫойтап, Бгйсз, ЁгуаЦеук:. УгесНса, Во-ловикова были получены топологические доказательства теоремы Тверберга и её цветного обобщения [3, 60, 67, 74] для случая, когда речь идёт о разбиении на п частей и число п является степенью простого. Фактически, доказательства основывались па неравенстве нулю эквивариантного класса Эйлера некоторого расслоения.

Приведём формулировки цветных обобщений теоремы Тверберга. В работе [5] доказана цветная теорема Тверберга на плоскости.

Теорема 1.5 (Двумерная цветная теорема Тверберга). Пусть на плоскости дано множество из 3п точек. Пусть эти точки раскрашены в три цвета так, чт, о точек каждого цвета ровной. Тогда эти точки можно разбить на п разноцветных троек так, что треугольники, соответствующие точкам, имеют общую точку.

Обобщить этот результат на (с1+ 1) п точек в пока не удалось, однако в работе [67] с помощью топологической техники доказано утверждение, в котором точки берутся с некоторым запасом.

Теорема 1.6 (Цветная теорема Тверберга). Пусть в дано множество из (б? 4- 1)? точек, где I > 2 г — 1. г — рк, р — простое число. Пусть эти точки разбиты нас1+ 1 множество (цвет) по? элементов.

Тогда из данных точек люжно выбрать г непересекающихся наборов Х[,., ХГ с выполнениелг следующих условий. Для любого г = 1,., г |Х:| = д + 1 и в присутствуют все цвета. Кроме того г.

Р|С0ПУХ-^0. г=1.

Приведём также одну из эквивалентных формулировок теоремы Борсука-Улама [85, 11], которая тесно связана с теоремами Хелли и Брауэра.

Теорема 1.7 (Теорема Борсука-Люстерпика-Шнирельмана). Если сфера 5″ покрыта п + 1-м замкнутым множеством., Хп+1, то по крайней, мере одно из Х-ь содержит пару диаметрально противоположных точек на сфере.

В главах 5 и 6 будут рассмотрены разного рода обобщения и следствия из обобщений этой теоремы, в которых вместо покрытия сферы рассматриваются некоторые покрытия канонического расслоения над грассманианом.

Отметим также эквивалентную формулировку теоремы Борсука-Улама [11], в которой вместо покрытий рассматриваются функции.

Теорема 1.8 (Теорема Борсука-Улама). Если на сфере Sn даны и нечётных непрерывных функций fi,., fn. то для некоторой точки х е Sn.

Ых) = f2(x) = ¦ ¦ • = fn (x) = 0.

Близким к теореме Борсука-Улама утверждением является теорема Люстерпика-Шнирельмапа о категории проективного пространства. Ниже приведена одна из возможных формулировок.

Теорема 1.9 (Теорема Люстерника-Шнирельмана). Если сфера Sn покрыта п замкнутыми множествами Х,., Хп. инвариантными относительно отражения х У —х, то для некоторого г одна из колтонент связности XL содержит пару диаметрально противоположных точек на сфере.

Одним из следствий теоремы Хелли является теорема Неймана-Радо [46. 49] о центральной точке меры.

Теорема 1.10 (Теорема о центральной точке). Для абсолютно непрерывной вероятностной меры, i на W1 найдётся, такая точка х Е.

M.d, что для всякого полупространства Н Э х }i{H) > ^ ^.

Отметим также другой известный результат о делении мер (см. работы Stone. Tukey, Steinhaus [55, 54]), являющийся следствием теоремы Борсука-Улама.

Теорема 1.11 (Теорема «о бутерброде»). Пусть на W1 заданы d абсолютно непрерывных вероятностных мер /ii,.,. Тогда найдётся полупространство Н С такое, что для любого г = 1,., d.

Я) = ½.

В работах Дольникова, ЙуаЦеую. Угеспса [65, 81, 82] теорема о центральной точке была обобщена на случай нескольких мер. Причём данное обобщение в случае т = (I— 1 даёт теорему «о бутерброде».

Теорема 1.12 (Теорема о центральной трансверсали). Пусть на заданы? д+1 абсолютно непрерывная вероятностная мера^о./.?т.

Тогда найдётся т-плоскость Ь € М^ такая, что для всякого полупространства Н 1Э Ь и всякого? = 0,., тп + 1.

1 М (Н) > с1 — т + 1.

Теоремы Тверберга и гипотезу Тверберга о трансверсалях (формулировка. в главе 4) можно рассматривать как некоторые дискретные обобщения теорем о центральной точке и центральной трансверсали соответственно.

К теореме о центральной трансверсали близко следующее утверждение из [81. 82]:

Теорема 1.13 (Теорема Дольникова о трансверсали). Пусть 0 < к < с1 — 1 и в Ж'1 даны к + 1 семейство Ть (1 = 0,., к) выпуклых компактов. Предположим, что в каждом селгействе любыед+1—к множеств им, еют общую т, очку. Тогда существует к-плоскость, пересекаются все. множества из.

Из этой теоремы при к = 0 получается обычная теорема Хелли. Следующая теорема из [30, 35] также имеет дело с плоскими транс-версалями.

Теорема 1.14 (Теорема Хорна-Кли). Для натуральных 1 < к < <1 и семейства Т выпуклых компактов в М^, следующие три условия эквивалентны:

1) Каждые к множеств из Т имеют общую точку;

2) Каждая плоскость коразмерности к — 1 в Жг/ имеет транс-лят. пересекающий все лаю жесте, а Т;

3) Каждая плоскость коразмерности к в принадлежит плоскости коразмерности к — 1. пересекающий все множества Т.

В главе б будут приведены некоторые новые результаты по плоским трансверсалям, близкие к теоремам Борсука-Улама, теореме Хел-ли и двум вышеприведённым теоремам.

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

Одна из первых теорем о вписывании из [102].

Теорема 1.15 (Теорема Шнирельмана). Для всякой гладкой замкнутой кривой С С М2 найдётся квадрат, все вершины которого лежат на кривой С.

Другая типичная теорема об оиисывании имеет вид [34].

Теорема 1.16 (Теорема Какутани). Вокруг всякого выпуклого тела К С М3 можно описать куб.

Конечно, эти теоремы являются простейшими промерами. Множество разных утверждений о вписывании и описывапии можно найти в работах [77. 88, 89, 90, 91]. Например, в диссертации Макеева [89] доказан следующий аналог теоремы Шнирельмана.

Теорема 1.17 (Теорема Макеева). Во всякое гладкое выпуклое те, ло К С М3 м, ожно вписать октаэдр.

Предметом данной работы является, в частности, обобщение этой теоремы на большие размерности.

Близкими к задаче вписывания многогранника является серия задач о бильярдных траекториях в выпуклых телах. Типичный результат такого рода даёт теорема (ф (п) — функция Эйлера).

Теорема 1.18 (Теорема Биркгофа). Для всякого гладкого выпуклого компакта К С К2 найдётся, не менее ф (п) различных замкнутых бильярдных траекторий в К с п ударениями о край.

Некоторые результаты, но многомерному обобщению данной теоремы были доказаны в работах Бабенко, Фарбера и Табачникова [ТО, 20, 21]. В этой работе будет доказано аналогичное утверждение в случае простой длины (количества звеньев) траектории и произвольной размерности (1> 3.

1. G. Birkhoff, «Dynamical systems», Amer. Math. Soc. Coll. Puhl, 9 (1927).10| T. Bisztriczky, «On separated families of convex bodies», Arch. Math., 54 (1990), 193—199.

2. K. Borsuk, «Drei Satze uber die n-dimensionale euklidische Sphare'', Fund. Math., 20 (1933), 177−190.12j L. Brouwer, «Uber abbildung von mannigfaltigkeiten», Mathematische Annalen. 71 (1910), 97−115.

3. S.E. Cappell S.E., J.E. Goodman, J. Pach, R. Pollack, M. Sliarir, R. Wenger, «Common tangents and common transversals», Adv. in Math., 106 (1994), 198—215.

4. L. Danzer L., B. Grunbaum, V. Klee, «Helly's theorem and its relatives», Convexity, Proc. of Symposia in Pure Math, 7, Amer. Math. Soc., Providence, 1963. 101−180.

5. V.L. Dol’nikov, «Some generalizations of transversal theorems» (to appear).16| B. Eaves, «Homotopies for computation of fixed points», Mathematical Programming, 3 (1972), 1−22.

6. R. Kellogg, T. Li, J. Yorke, «Constructive proof of the Brouwer fixed point theorem and computational results», SIAM J. Numer. Anal., 13 (1976). 473 483.

7. B. Knaster, «Problem 4», Colloq. Math., 30 (1947), 30−31.

8. M.A. Krasnosel’skii. «On special coverings of a finite-dimensional sphere», Dokl. Akad. Nauk SSSR, 103 (1955), 961−964.

9. N.H. Kuiper, «Double normals of convex bodies», Israel Jo urnal of Mathematics. 2 (1964), 71−80.43| E.L. Lusk, «The mod p Smith index and a generalized Borsuk-Ulam theorem», Michigan Math. J., 22 (1975), 151−160.

10. J. Matousek, Using the Borsuk-Ulam theorem, Springer Verlag, BerlinHeidelberg, 2003.45| J. McClearv, A user’s guide to spectral sequences, Cambridge University Press, 2001.

11. B.H. Neumann, «On an invariant of plane regions and mass distributions», ./. London Math. Soc., 20 (1945), 226−237.

12. R. Palais, «Homotopy theory of infinite dimensional manifolds», Topology, 5 (1966), 1−16.

13. R. Palais. «Lusternik-Schnirelmann theory on Banach manifolds», Topology, 5 (1966), 115−132.49| R. Rado. «A theorem on general measure», J. London Math. Soc., 21 (1946). 291−300.

14. J. Radon, «Mengen konvexer Korper, die einen gemeinsamen Punkt enthalteir, Math. Ann., 83 (1921), 113−115.

15. E.A. Ramos, «Equipartiotion of mass distributions by hyperplanes», Discrete and Computational Geometry, 15 (1996), 147−167.

16. И. К. Бабсико, «Периодические траектории трехмерных бильярдов Биркго-фа», Marri, сборник, 181:9 (1990), 1155−1169.71J К. Браун, Когомологии групп, Наука, М., 1987.72| В. А. Васильев, Лагранжевы и лежандровы характеристические классы. МЦНМО, М., 2000.

17. А. Ю. Воловиков, «Точки совпадения отображений ^'-пространств», Изв. РАН. Сер. мат, ем., 69:5 (2005), 53−106.77| М. Л. Громов, «О симплексах, вписанных в гиперповерхности», Мат. заметки, 5:1 (1969), 81−89.

18. Б. Грюнбаум, Этюды по комбинаторной геометрии и теории выпуклых тел, Наука, М., 1971.

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

20. В. Л. Дольников, «Обобщенные трансверсали семейств множеств в К» и связи между теоремами Хелли и Борсука", Докл. АН СССР, 297:4 (1987), 777 780.

21. В. Л. Дольников, «Об одном обобщении теоремы о бутерброде», Мат. заметки. 52:2 (1992), 112−133.

22. В. Л. Дольников, Теоремы типа Хелли для трансверсалей семейств множеств и их приложения. Диссертация на соискание учёной степени доктора физико-математических наук, Ярославский государственный университет им. П. Г. Демидова, Ярославль, 2001.

23. В. В. Макеев, «Вписанные и описанные многогранники для выпуклого тела и задача о непрерывных функциях на сфере в евклидовом пространстве», Алгебра и анализ, 18 (2006), 187−204.

24. В. В. Макеев, «Некоторые экстремальные задачи для векторных расслоений», Алгебра и анализ, 19:2 (2007), 131−155.92| Д. Милнор, Д. Сташеф. Характеристические классы, Мир, М., 1979.

25. A.C. Мищенко, Векторные расслоение и их применения, Наука, М., 1984.94. ¿-ЪНирепбсрг, Лекции по нелинейному функциональному анализу, Мир, М.,.

26. Е. С. Половинкин, Элементы теории многозначных отображений, Московский физико-технический институт, М., 1982.

27. У И Сян, Когомологическая теория топологических групп преобразований, Мир, М., 1979.

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

29. М. Холл, Комбинаторика, Мир, М., 1970.

30. С. Улам, Нерешённые математические задачи, Наука, М., 1964.

31. А. Т. Фоменко, Д. Б. Фукс, Курс гомотопической топологии, Наука. М., 1989.101| Г. Е. Шилов, Б. Л. Гуревич, Интеграл, мера и производная, Наука, М., 1967.

32. Л. Г. Шннрельман, «О некоторых геометрических свойствах замкнутых кривых», Успехи мат. наук, 10 (1944), 34−44.