Введение

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

В дискретной геометрии теорема Тверберга, впервые сформулированная Хельге Твербергом в 1966 году, утверждает, что достаточное количество точек в d-мерном евклидовом пространстве можно разбить на подмножества с пересекающимися выпуклыми оболочками. В частности, для любых положительных целых чисел d, r и любого множества из (n*d+1) точек существует разбиение данных точек на r подмножеств, выпуклые оболочки которых все имеют общую точку; другими словами, существует точка x (не обязательно одна из заданных точек), принадлежащая выпуклой оболочке каждого из подмножеств. Разбиение, получаемое в результате этой теоремы, известно как разбиение Тверберга. Частный случай r = 2 был доказан ранее Радоном и известен как теорема Радона.

Примеры

В случае d = 1 утверждается, что любые 2r−1 точек на действительной прямой можно разбить на r подмножеств с пересекающимися выпуклыми оболочками. Действительно, если точки упорядочены как x1 < x2 < … < x2r−1 < x2r, то разбиение на Ai = {xi, x2r−i+1} для i от 1 до r удовлетворяет этому условию (и оно единственно). Для r = 2 теорема Тверберга утверждает, что любые d + 2 точки можно разбить на два подмножества с пересекающимися выпуклыми оболочками. Это известно как теорема Радона. В этом случае, для точек в общем положении, разбиение единственно. В случае r = 3 и d = 2 утверждается, что любые семь точек на плоскости можно разбить на три подмножества с пересекающимися выпуклыми оболочками. На иллюстрации показан пример, в котором семь точек являются вершинами правильного семиугольника. Как показывает пример, может существовать множество различных разбиений Тверберга для одного и того же набора точек; эти семь точек можно разбить семью различными способами, отличающимися друг от друга вращениями.

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

Эквивалентная формулировка теоремы Тверберга: Пусть d и r – положительные целые числа, и пусть N := (d+1)(r-1). Если ƒ – любая аффинная функция от N-мерного симплекса ΔN в Rd, то существуют r попарно непересекающихся граней ΔN, чьи образы под ƒ пересекаются. То есть: существуют грани F1, …, Fr ΔN такие, что и . Они эквивалентны, поскольку любая аффинная функция на симплексе однозначно определяется образами его вершин. Формально, пусть ƒ – аффинная функция от ΔN в Rd. Пусть – вершины ΔN, и пусть – их образы под ƒ. Согласно исходной формулировке, множество можно разбить на r непересекающихся подмножеств, например, ((xi)i ∈ Aj)j ∈ [r] с перекрывающимися выпуклыми оболочками. Поскольку f аффинна, выпуклая оболочка (xi)i ∈ Aj является образом грани, образованной вершинами (vi)i ∈ Aj для всех j ∈ [r]. Эти грани попарно непересекаются, и их образы под f пересекаются, как утверждается в новой формулировке. Топологическая теорема Тверберга обобщает эту формулировку. Она позволяет f быть любой непрерывной функцией, не обязательно аффинной. Но в настоящее время она доказана только для случая, когда r является степенью простого числа: Пусть d – положительное целое число, и пусть r – степень простого числа. Пусть N := (d+1)(r-1). Если ƒ – любая непрерывная функция от N-мерного симплекса ΔN в Rd, то существуют r попарно непересекающихся граней ΔN, чьи образы под ƒ пересекаются. То есть: существуют грани F1, …, Fr ΔN такие, что и .

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

Топологическая теорема Тверберга была доказана для простых чисел Барани, Шлосман и Сюкс. Матушек представляет доказательство, использующее удалённые объединения. Теорема была доказана для простой степени числа Озайдином, а позже Воловиковым и Саркариа.