Теорема Тверберга

В дискретной геометрии теорема Тверберга , впервые сформулированная Хельге Твербергом в 1966 году, ^[1] является результатом того, что достаточное количество точек в d -мерном евклидовом пространстве можно разбить на подмножества с пересекающимися выпуклыми оболочками . В частности, для любых натуральных чисел d , r и любого набора

(d+1)(r-1)+1\

точек существует разбиение данных точек на г подмножеств, все выпуклые оболочки которых имеют общую точку; другими словами, существует точка x (не обязательно одна из заданных точек) такая, что x принадлежит выпуклой оболочке всех подмножеств. Разбиение, полученное в результате этой теоремы, известно как разбиение Тверберга .

Частный случай r = 2 был ранее доказан Радоном и известен как теорема Радона .

Примеры

Случай d = 1 означает, что любые 2 r −1 точек на вещественной прямой можно разбить на r подмножеств с пересекающимися выпуклыми оболочками. Действительно, если точки имеют вид x ₁ < x ₂ < ... < x _2r < x _2r-1 , то разбиение на A _i = {x _i , x _{2 r - i} } для i в 1,..., r удовлетворяет этому условию (и оно уникально).

Для r = 2 теорема Тверберга утверждает, что любые d + 2 точки можно разделить на два подмножества с пересекающимися выпуклыми оболочками. Это известно как теорема Радона . В этом случае для точек общего положения разбиение единственное.

Случай r = 3 и d = 2 означает, что любые семь точек плоскости можно разделить на три подмножества с пересекающимися выпуклыми оболочками. На иллюстрации показан пример, в котором семь точек являются вершинами правильного семиугольника . Как показывает пример, может быть много разных разбиений Тверберга одного и того же набора точек; эти семь точек могут быть разделены семью различными способами, которые отличаются вращением друг друга.

Топологическая теорема Тверберга

Эквивалентная формулировка теоремы Тверберга:

Пусть d , r — положительные целые числа, и пусть N := ( d +1)( r -1). Если ƒ — любая аффинная функция из N -мерного симплекса Δ ^Н в Р ^д, то существует r попарно непересекающихся граней ∆ ^Н чьи изображения под ƒ пересекаются. То есть: существуют грани F ₁ ,...,F _r группы ∆ ^Н такой, что $\forall i,j\in [r]:F_{i}\cap F_{j}=\emptyset$ и $f(F_{1})\cap \cdots \cap f(F_{r})\neq \emptyset$ .

Они эквивалентны, поскольку любая аффинная функция на симплексе однозначно определяется образами его вершин. Формально, пусть ƒ — аффинная функция из ∆ ^Н в Р ^д. Позволять $v_{1},v_{2},\dots ,v_{N+1}$ — вершины ∆ ^Н, и пусть $x_{1},x_{2},\dots ,x_{N+1}$ быть их изображениями под ƒ . По оригинальной формулировке, $x_{1},x_{2},\dots ,x_{N+1}$ можно разделить на r непересекающиеся подмножества, например (( x _i ) _{i in Aj} ) _{j in [r]} с перекрывающейся выпуклой оболочкой. Поскольку f аффинно, выпуклая оболочка ( x _i ) _{i в Aj} представляет собой образ грани, натянутой на вершины ( vi ₎ i в _Aj для всех j в [ r ]. Эти грани попарно непересекающиеся, а их образы под f пересекаются, как утверждает новая формулировка. Топологическая теорема Тверберга обобщает эту формулировку. Это позволяет f быть любой непрерывной функцией, не обязательно аффинной. Но на данный момент это доказано только для случая, когда r — степень простого числа:

Пусть d — целое положительное число, а r — степень простого числа. Пусть N := ( d +1)( r -1). Если ƒ — любая непрерывная функция из N -мерного симплекса ∆ ^Н в Р ^д, то существует r попарно непересекающихся граней ∆ ^Н чьи изображения под ƒ пересекаются. То есть: существуют грани F ₁ ,...,F _r группы ∆ ^Н такой, что $\forall i,j\in [r]:F_{i}\cap F_{j}=\emptyset$ и $f(F_{1})\cap \cdots \cap f(F_{r})\neq \emptyset$ .

Доказательства

Топологическая теорема Тверберга была доказана для простых $r$ Барани, Шлосман и Шуч. ^[2] Матоусек ^[3] представляет доказательство с использованием удаленных объединений .

Теорема была доказана для $r$ первичная власть Озайдина, ^[4] and later by Volovikov ^[5] и Саркария. ^[6]

См. также

Основная гипотеза Роты

Ссылки

^ Тверберг, Х. (1966), «Обобщение теоремы Радона» (PDF) , Журнал Лондонского математического общества , 41 : 123–128, doi : 10.1112/jlms/s1-41.1.123
^ Барань, И.; Шлосман, С.Б.; Сюч, А. (февраль 1981 г.), «О топологическом обобщении теоремы Тверберга» , Журнал Лондонского математического общества , s2-23 (1): 158–164, doi : 10.1112/jlms/s2-23.1.158
^ Матушек, Иржи (2007), Использование теоремы Борсука-Улама : Лекции по топологическим методам в комбинаторике и геометрии (2-е изд.), Берлин-Гейдельберг: Springer-Verlag, ISBN 978-3-540-00362-5 , Написано в сотрудничестве с Андерсом Бьёрнером и Гюнтером М. Циглером. , раздел 4.3, стр. 162-163.
^ Озайдин, Мурад (1987), Эквивариантные карты для симметричной группы (препринт), Университет Висконсин-Мэдисон, hdl : 1793/63829
^ Воловиков, А.Ю. (март 1996 г.), «О топологическом обобщении теоремы Тверберга» , Mathematical Notes , 59 (3): 324–326, doi : 10.1007/BF02308547 , ISSN 1573-8876 , S2CID 122078369
^ Саркария, К.С. (ноябрь 2000 г.), «Разбиения Тверберга и теоремы Борсука – Улама» , Pacific Journal of Mathematics , 196 (1): 231–241, doi : 10.2140/pjm.2000.196.231 , ISSN 0030-8730

Дальнейшее чтение

Ад, Стефан (2006), Теоремы типа Тверберга и свойство дробного гелли (докторская диссертация), Берлинский технический университет, doi : 10.14279/depositonce-1464

[1] Тверберг, Х. (1966), «Обобщение теоремы Радона» (PDF) , Журнал Лондонского математического общества , 41 : 123–128, doi : 10.1112/jlms/s1-41.1.123

[2] Барань, И.; Шлосман, С.Б.; Сюч, А. (февраль 1981 г.), «О топологическом обобщении теоремы Тверберга» , Журнал Лондонского математического общества , s2-23 (1): 158–164, doi : 10.1112/jlms/s2-23.1.158

[:03-3] Матушек, Иржи (2007), Использование теоремы Борсука-Улама : Лекции по топологическим методам в комбинаторике и геометрии (2-е изд.), Берлин-Гейдельберг: Springer-Verlag, ISBN 978-3-540-00362-5 , Написано в сотрудничестве с Андерсом Бьёрнером и Гюнтером М. Циглером. , раздел 4.3, стр. 162-163.

[4] Озайдин, Мурад (1987), Эквивариантные карты для симметричной группы (препринт), Университет Висконсин-Мэдисон, hdl : 1793/63829

[5] Воловиков, А.Ю. (март 1996 г.), «О топологическом обобщении теоремы Тверберга» , Mathematical Notes , 59 (3): 324–326, doi : 10.1007/BF02308547 , ISSN 1573-8876 , S2CID 122078369

[6] Саркария, К.С. (ноябрь 2000 г.), «Разбиения Тверберга и теоремы Борсука – Улама» , Pacific Journal of Mathematics , 196 (1): 231–241, doi : 10.2140/pjm.2000.196.231 , ISSN 0030-8730

[1]

[2]

[3]

[4]

[5]

[6]