Теорема Хелли является основным результатом в дискретной геометрии на пересечении из выпуклых множеств . Он был открыт Эдуардом Хелли в 1913 году [1], но опубликован им только в 1923 году, когда уже появились альтернативные доказательства Радона (1921) и Кенига (1922) . Теорема Хелли дала начало понятию семьи Хелли .
Заявление
Пусть X 1 , ..., X n - конечный набор выпуклых подмножеств в R d , где n > d + 1 . Если пересечение каждого d + 1 из этих множеств непусто, то весь набор имеет непустое пересечение; это,
Для бесконечных коллекций следует предполагать компактность:
Пусть { X α } - набор компактных выпуклых подмножеств в R d , такой, что каждый поднабор мощности не выше d + 1 имеет непустое пересечение. Тогда вся коллекция имеет непустое пересечение.
Доказательство
Мы доказываем конечный вариант, используя теорему Радона, как в доказательстве Радона (1921) . Бесконечная версия затем следует характеристикой компактности конечным свойством пересечения : набор замкнутых подмножеств компактного пространства имеет непустое пересечение тогда и только тогда, когда каждое конечное подмножество имеет непустое пересечение (как только вы зафиксируете один набор, пересечение с ним всех остальных - замкнутые подмножества фиксированного бикомпакта).
Доказательство проводится по индукции :
Базовый случай: пусть n = d + 2 . По нашим предположениям, для каждого j = 1, ..., n существует точка x j, которая находится на общем пересечении всех X i, за исключением, возможно, X j . Теперь применим теорему Радона к множеству А = { х 1 , ..., х п }, которая дает нам непересекающихся подмножеств 1 , 2 из так , что выпуклая оболочка из 1 пересекает выпуклая оболочка A 2 . Предположим, что p - точка пересечения этих двух выпуклых оболочек. Мы утверждаем, что
Действительно, рассмотрим любой j ∈ {1, ..., n }. Докажем, что p ∈ X j . Обратите внимание, что единственный элемент A, который может не входить в X j, - это x j . Если x j ∈ A 1 , то x j ∉ A 2 и, следовательно, X j ⊃ A 2 . Поскольку X j выпукло, тогда оно также содержит выпуклую оболочку A 2 и, следовательно, также p ∈ X j . Аналогично, если x j ∉ A 1 , то X j ⊃ A 1 , и по тем же соображениям p ∈ X j . Поскольку p находится в каждом X j , он также должен быть в пересечении.
Выше мы предполагали, что все точки x 1 , ..., x n различны. Если это не так, скажем, x i = x k для некоторого i ≠ k , тогда x i находится в каждом из множеств X j , и снова мы заключаем, что пересечение непусто. Это завершает доказательство в случае n = d + 2 .
Индуктивный шаг: предположим, что n > d + 2 и что утверждение верно для n −1 . Приведенный выше аргумент показывает, что любая подколлекция из d + 2 множеств будет иметь непустое пересечение. Затем мы можем рассмотреть коллекцию , где мы заменим два множества X п -1 и X п с одной множества X п -1 ∩ X п . В этой новой коллекции каждая подколлекция из d + 1 наборов будет иметь непустое пересечение. Следовательно, индуктивная гипотеза применима и показывает, что этот новый набор имеет непустое пересечение. Это подразумевает то же самое для исходной коллекции и завершает доказательство.
Красочная теорема Хелли
Красочный Helly теорема является продолжением теоремы Хелла , в котором, вместо одной коллекции, есть d + 1 коллекции выпуклых подмножеств R д .
Если для каждого выбора трансверсали - одного набора из каждой коллекции - есть точка, общая для всех выбранных наборов, то по крайней мере для одной из коллекций существует точка, общая для всех наборов в коллекции.
Образно можно считать, что коллекции d +1 имеют d +1 разных цветов. Тогда теорема гласит, что если каждый выбор одного набора для каждого цвета имеет непустое пересечение, то существует такой цвет, что все множества этого цвета имеют непустое пересечение. [2]
Дробная теорема Хелли
Для любого a > 0 существует такое b > 0, что если X 1 , ..., X n являются n выпуклыми подмножествами R d , и по крайней мере a -доля ( d +1) -наборов множеств имеют общую точку, то хотя бы часть из b наборов имеет общую точку. [2]
Смотрите также
Заметки
- ^ Данцер, Грюнбаум & Кли (1963) .
- ^ a b Kalai, Gil (2019-03-15), "Новости о фракционном хелли, красочном хелли и радоне" , комбинаторике и многом другом , получено 13 июля 2020 г.
Рекомендации
- Боллобас, Б. (2006), «Проблема 29, Пересекающиеся выпуклые множества: теорема Хелли», Искусство математики: Время кофе в Мемфисе , Cambridge University Press, стр. 90–91, ISBN 0-521-69395-0.
- Danzer, L .; Грюнбаум, Б .; Клее, В. (1963), "Теорема Хелли и ее родственники", Выпуклость , Proc. Symp. Pure Math., 7 , Американское математическое общество , стр. 101–180..
- Экхофф, Дж. (1993), "Теоремы типа Хелли, Радона и Каратеодори", Справочник по выпуклой геометрии , A, B , Амстердам: Северная Голландия, стр. 389–448..
- Генрих Гуггенхаймер (1977) Применимая геометрия , стр. 137, Кригер, Хантингтон ISBN 0-88275-368-1 .
- Helly, E. (1923), "Uber Mengen konvexer Körper mit gemeinschaftlichen Punkten", Jahresbericht der Deutschen Mathematiker-Vereinigung , 32 : 175–176.
- Кёниг, Д. (1922), "Убер konvexe Körper", Mathematische Zeitschrift , 14 (1): 208-220, DOI : 10.1007 / BF01215899.
- Радон, Дж (1921), "Mengen konvexer Körper, умирают Einen gemeinsamen Punkt enthalten", Mathematische Annalen , 83 (1-2): 113-115, DOI : 10.1007 / BF01464231.