Теорема Хеллиса - Hellys theorem

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

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

Заявление

Позволять Икс₁, ..., Икс_п - конечный набор выпуклых подмножеств р^d, с п > d + 1. Если пересечение каждого d + 1 таких множеств непусто, то весь набор имеет непустое пересечение; то есть,

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

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

Позволять {Икс_α} быть собранием компактный выпуклые подмножества р^d, так что каждая подколлекция мощность в большинстве d + 1 имеет непустое пересечение. Тогда вся коллекция имеет непустое пересечение.

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

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

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

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

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

Действительно, рассмотрим любые j ∈ {1, ..., п}. Мы докажем, что п ∈ Икс_j. Обратите внимание, что единственный элемент А этого может не быть в Икс_j является Икс_j. Если Икс_j ∈ А₁, тогда Икс_j ∉ А₂, и поэтому Икс_j ⊃ А₂. С Икс_j выпукла, тогда она также содержит выпуклую оболочку А₂ и поэтому также п ∈ Икс_j. Аналогично, если Икс_j ∉ А₁, тогда Икс_j ⊃ А₁, и по тем же соображениям п ∈ Икс_j. С п есть в каждом Икс_j, он также должен находиться на перекрестке.

Выше мы предположили, что точки Икс₁, ..., Икс_п все разные. Если это не так, скажите Икс_я = Икс_k для некоторых я ≠ k, тогда Икс_я находится в каждом из наборов Икс_j, и снова заключаем, что пересечение непусто. Это завершает доказательство в случае п = d + 2.

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

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

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

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

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

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

Для каждого а > 0 есть некоторые б > 0 такое, что если Икс₁, ..., Икс_п находятся п выпуклые подмножества р^d, и по крайней мере а-доля (d+1) -наборы множеств имеют общую точку, то есть не менее б У наборов есть общая точка.^[2]

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

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

Примечания

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

Рекомендации

• Боллобаш, Б. (2006), "Проблема 29, Пересекающиеся выпуклые множества: теорема Хелли", Искусство математики: время кофе в Мемфисе, Cambridge University Press, стр. 90–91, ISBN  0-521-69395-0.
• Danzer, L .; Грюнбаум, Б.; Клее, В. (1963), «Теорема Хелли и ее родственники», Выпуклость, Proc. Symp. Чистая математика., 7, Американское математическое общество, стр. 101–180.
• Экхофф, Дж. (1993), "Теоремы типа Хелли, Радона и Каратеодори", Справочник по выпуклой геометрии, А, Б, Амстердам: Северная Голландия, стр. 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, Дои:10.1007 / BF01215899.
• Радон, Дж. (1921), "Mengen konvexer Körper, die einen gemeinsamen Punkt enthalten", Mathematische Annalen, 83 (1–2): 113–115, Дои:10.1007 / BF01464231.