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

Теорема о пересечениях d-мерных выпуклых множеств

Теорема Хелли для евклидовой плоскости: если семейство выпуклых множеств имеет непустое пересечение для каждой тройки множеств, то все семейство имеет непустое пересечение.

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

Заявление

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

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

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

Пусть будет набором компактных выпуклых подмножеств , таким, что каждый поднабор мощности не более имеет непустое пересечение. Тогда весь набор имеет непустое пересечение. ${\displaystyle \{X_{\alpha }\}}$ ${\displaystyle \mathbb {R} ^{d}}$ ${\displaystyle d+1}$

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

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

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

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

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

Действительно, рассмотрим любой j ∈ {1, ..., n }. Мы докажем, что p ∈ X _j . Заметим, что единственный элемент A , который может не быть в X _{j ,} это x _j . Если x _j ∈ A ₁ , то x _j ∉ A ₂ , и, следовательно, X _j ⊃ A ₂ . Поскольку X _j выпукло, оно также содержит выпуклую оболочку A _{2 ,} и, следовательно, также p ∈ X _j . Аналогично, если x _j ∉ A ₁ , то X _j ⊃ A ₁ , и по тем же рассуждениям p ∈ X _j . Поскольку p содержится в каждом X _j , оно также должно быть в пересечении.

Выше мы предположили, что точки x ₁ , ..., x _n все различны. Если это не так, скажем, x _i = x _k для некоторого i ≠ k , то x _i есть в каждом из множеств X _j , и мы снова заключаем, что пересечение непусто. Это завершает доказательство в случае n = d  + 2 .

Индуктивный шаг: Предположим, что n  >  d  + 2 и что утверждение верно для n −1 . Приведенное выше рассуждение показывает, что любая подколлекция из d  + 2 множеств будет иметь непустое пересечение. Затем мы можем рассмотреть коллекцию, в которой мы заменяем два множества X _{n −1} и X _n одним множеством X _{n −1} ∩ X _n . В этой новой коллекции каждая подколлекция из d  + 1 множеств будет иметь непустое пересечение. Следовательно, индуктивная гипотеза применима и показывает, что эта новая коллекция имеет непустое пересечение. Это подразумевает то же самое для исходной коллекции и завершает доказательство.

Красочная теорема Хелли

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

Если для каждого выбора трансверсали — одного набора из каждой совокупности — существует общая точка для всех выбранных множеств, то по крайней мере для одного из множеств существует общая точка для всех множеств в совокупности.

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

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

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

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

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

Примечания

1. Данцер, Грюнбаум и Клее (1963).
2. Kalai, Gil (2019-03-15), "Новости о дробном Хелли, красочном Хелли и радоне", Комбинаторика и многое другое , получено 2020-07-13

Ссылки

• Боллобас, Б. (2006), «Задача 29, Пересечение выпуклых множеств: теорема Хелли», Искусство математики: время кофе в Мемфисе , Cambridge University Press, стр. 90–91, ISBN 0-521-69395-0.
• Данцер, Л.; Грюнбаум, Б .; Клее, В. (1963), «Теорема Хелли и ее родственники», Выпуклость , Proc. Symp. Pure Math., т. 7, Американское математическое общество , стр. 101–180.
• Экхофф, Дж. (1993), «Теоремы типа Хелли, Радона и Каратеодори», Справочник по выпуклой геометрии , т. A, B, Амстердам: Северная Голландия, стр. 389–448.
• Генрих Гуггенхаймер (1977) Применимая геометрия , стр. 137, Кригер, Хантингтон ISBN 0-88275-368-1 . 
• Хелли, Э. (1923), «Über Mengen konvexer Körper mit gemeinschaftlichen Punkten», Jahresbericht der Deutschen Mathematiker-Vereinigung , 32 : 175–176.
• Кениг, Д. (1922), «Über konvexe Körper», Mathematische Zeitschrift , 14 (1): 208–220, doi : 10.1007/BF01215899, S2CID  128041360.
• Радон, Дж. (1921), «Mengen konvexer Körper, die einen gemeinsamen Punkt enthalten», Mathematische Annalen , 83 (1–2): 113–115, doi : 10.1007/BF01464231, S2CID  121627696.