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

О разбиениях на пересекающиеся выпуклые оболочки

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

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

${\displaystyle (d+1)(r-1)+1\ }$

точек в d -мерном евклидовом пространстве существует разбиение заданных точек на r подмножеств, выпуклые оболочки которых имеют общую точку; другими словами, существует точка 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 -мерного симплекса Δ ^N в R ^d , то существует r попарно непересекающихся граней Δ ^{N ,} образы которых при ƒ пересекаются. То есть: существуют грани F ₁ ,...,F _r из Δ ^N такие, что и . ${\displaystyle \forall i,j\in [r]:F_{i}\cap F_{j}=\emptyset }$ ${\displaystyle f(F_{1})\cap \cdots \cap f(F_{r})\neq \emptyset }$

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

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

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

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

Теорема была доказана для степени простого числа Озайдином ^[4], а затем Воловиковым ^{[5] и Саркарией [6]} . ${\displaystyle r}$

Смотрите также

• Базисная гипотеза Роты

Ссылки

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
3. Матоушек, Йиржи (2007), Использование теоремы Борсука-Улама : Лекции по топологическим методам в комбинаторике и геометрии (2-е изд.), Берлин-Гейдельберг: Springer-Verlag, ISBN 978-3-540-00362-5, Написано в сотрудничестве с Андерсом Бьёрнером и Гюнтером М. Циглером, Раздел 4.3, стр. 162-163
4. Озайдин, Мурад (1987), Эквивариантные отображения для симметричной группы (препринт), Университет Висконсин-Мэдисон, hdl :1793/63829
5. Воловиков, А. Ю. (март 1996), «Об одном топологическом обобщении теоремы Тверберга», Математические заметки , 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

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

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