Теорема Хеллиса - Википедия - Hellys theorem

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

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

Заявление

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примечания

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