Теорема Хелли

Теорема Хелли — основной результат дискретной геометрии о пересечении выпуклых множеств . Он был открыт Эдуардом Хелли в 1913 году. ^{[ 1 ]} но не публиковался им до 1923 г., когда альтернативные доказательства Радона (1921) и Кенига (1922) уже появились . Теорема Хелли породила понятие семейства Хелли .

Заявление

Пусть $X 1, ..., X n$ — конечный набор выпуклых подмножеств $R д$ , при этом $n \geq d + 1$ . Если пересечение каждого $d + 1$ из этих множеств непусто, то вся коллекция имеет непустое пересечение; то есть,

\bigcap _{j=1}^{n}X_{j}\neq \varnothing .

Для бесконечных коллекций необходимо предположить компактность:

Пусть ${X α}$ — совокупность компактных выпуклых подмножеств $R д$ , такой, что каждая подколлекция мощности не более $d + 1$ имеет непустое пересечение. Тогда вся коллекция имеет непустое пересечение.

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

Мы доказываем конечную версию, используя теорему Радона , как в доказательстве Радона (1921) . Бесконечная версия затем следует за с помощью свойства конечного пересечения характеристикой компактности : совокупность замкнутых подмножеств компактного пространства имеет непустое пересечение тогда и только тогда, когда каждая конечная подколлекция имеет непустое пересечение (как только вы зафиксируете одно множество, пересечение с ним всех остальных — замкнутые подмножества фиксированного компакта).

Доказательство проводится по индукции :

Базовый случай: пусть $n = d + 2$ . По нашим предположениям, для каждого $j,..., n$ существует точка $xj,$ которая находится в общем пересечении всех $Xi,$ за возможным исключением $Xj .$ = 1 Теперь мы применим теорему Радона к множеству $A = {x 1, ..., x n},$ которая дает нам непересекающиеся подмножества $A 1, A 2$ из $A$ такие, что выпуклая оболочка A $1 пересекает$ выпуклую оболочку $A 2$ . Предположим, что $p$ — точка пересечения этих двух выпуклых оболочек. Мы утверждаем, что

p\in \bigcap _{j=1}^{n}X_{j}.

Действительно, рассмотрим любой $j \in {1,..., n}.$ Мы докажем, $p \in Xj что .$ Обратите внимание, что единственный элемент $A$ , который может отсутствовать в $X j,$ — это $x j$ . Если $x j \in A 1$ , то $x j \notin A 2$ и, следовательно, $X j \supset A 2$ . Поскольку $X j$ выпукло, оно также содержит выпуклую оболочку $A 2$ и, следовательно, также $p \in X j$ . Аналогично, если $x j \notin A 1$ , то $X j \supset A 1$ и по тем же соображениям $p \in X j$ . Поскольку $p$ находится в каждом $X j$ , он также должен находиться в пересечении.

Выше мы предположили, что все точки $x 1, ..., x n$ различны. Если это не так, скажем, $x i = x k$ для некоторого $i \neq k$ , тогда $x i$ находится в каждом из множеств $X j$ , и мы снова заключаем, что пересечение непусто. Это завершает доказательство в случае $n = d + 2$ .

Индуктивный шаг: предположим, что $n > d + 2$ и что утверждение верно для $n -1$ . Приведенный выше аргумент показывает, что любая подколлекция из $d + 2$ множеств будет иметь непустое пересечение. Затем мы можем рассмотреть коллекцию, в которой мы заменим два набора $X n -1$ и $X n$ одним набором $X n -1 \cap X n$ . В этой новой коллекции каждая подколлекция из $d + 1$ множеств будет иметь непустое пересечение. Таким образом, применима индуктивная гипотеза, которая показывает, что эта новая коллекция имеет непустое пересечение. Это означает то же самое и для исходной коллекции и завершает доказательство.

Теорема о красочном Хелли

Красочная теорема Хелли является расширением теоремы Хелли, в которой вместо одного набора имеется d +1 набор выпуклых подмножеств $R. д$ .

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

Образно говоря, можно считать, что коллекции d +1 состоят из d +1 разных цветов. Тогда теорема гласит, что если каждый выбор одного набора для каждого цвета имеет непустое пересечение, то существует цвет такой, что все множества этого цвета имеют непустое пересечение. ^{[ 2 ]}

Дробная теорема Хелли

Для каждого a > 0 существует некоторое b > 0 такое, что если $X 1, ..., X n$ являются n выпуклыми подмножествами $R д$ , и хотя бы a -доля ( d +1)-кортежей множеств имеют общую точку, то часть из по крайней мере b множеств имеет общую точку. ^{[ 2 ]}

См. также

Теорема Каратеодори
Теорема Дуаньона
Теорема Кирхбергера
Лемма Шепли – Фолкмана.
Теорема Крейна – Милмана
Теория Шоке
Теорема Радона и ее обобщение, теорема Тверберга.
Теорема Кантора о пересечении множеств - еще одна теорема о пересечении множеств.

Примечания

^ Данцер, Грюнбаум и Клее (1963) .
^ Jump up to: ^а ^б Калай, Гил (15 марта 2019 г.), «Новости о дробном гелии, цветном гелии и радоне» , Комбинаторика и многое другое , получено 13 июля 2020 г.

Ссылки

Боллобас, Б. (2006), «Задача 29. Пересекающиеся выпуклые множества: теорема Хелли», Искусство математики: время кофе в Мемфисе , Cambridge University Press, стр. 90–91, ISBN 0-521-69395-0 .
Данцер, Л.; Грюнбаум, Б .; Клее, В. (1963), «Теорема Хелли и ее родственники», Выпуклость , Proc. Симп. Чистая математика., вып. 7, Американское математическое общество , стр. 101–180 .
Экхофф, Дж. (1993), «Теоремы типа Хелли, Радона и Каратеодори», Справочник по выпуклой геометрии , том. А, Б, Амстердам: Северная Голландия, стр. 389–448 .
Генрих Гуггенхаймер (1977) Применимая геометрия , стр. 137, Кригер, Хантингтон ISBN 0-88275-368-1 .
Хелли, Э. (1923), «О множествах выпуклых тел с общими точками», Годовой отчет Немецкой математической ассоциации , 32 : 175–176 .
Кениг, Д. (1922), «О выпуклых телах», Mathematical Journal , 14 (1): 208–220, doi : 10.1007/BF01215899 , S2CID 128041360 .
Радон, Дж. (1921), «Наборы выпуклых тел, содержащих общую точку», Mathematical Annals , 83 (1–2): 113–115, doi : 10.1007/BF01464231 , S2CID 121627696 .

[1] Данцер, Грюнбаум и Клее (1963) .

[:0-2] Jump up to: ^а ^б Калай, Гил (15 марта 2019 г.), «Новости о дробном гелии, цветном гелии и радоне» , Комбинаторика и многое другое , получено 13 июля 2020 г.

[ 1 ]

[ 2 ]