Семья Хелли

В комбинаторике семейство Хелли порядка k — это семейство множеств , в котором каждое минимальное подсемейство с пустым пересечением содержит k или меньше множеств. Эквивалентно, каждое конечное подсемейство такое, что каждое k -кратное пересечение непусто, имеет непустое полное пересечение. Свойство k -Helly — это свойство быть семейством Хелли порядка k .

Число k в этих именах часто опускается в случае, когда k = 2 . Таким образом, семейство множеств обладает свойством Хелли , если для каждых n множеств $s_{1},\ldots ,s_{n}$ в семье, если $\forall i,j\in [n]:s_{i}\cap s_{j}\neq \emptyset$, затем $s_{1}\cap \cdots \cap s_{n}\neq \emptyset$.

Эти концепции названы в честь Эдуарда Хелли (1884–1943); Теорема Хелли о выпуклых множествах , породившая это понятие, утверждает, что выпуклые множества в евклидовом пространстве размерности n представляют собой семейство Хелли порядка n + 1 .

Примеры

• В семействе всех подмножеств множества { a , b , c , d } подсемейство {{ a , b , c }, { a , b , d }, { a , c , d }, { b , c , d }} имеет пустое пересечение, но удаление любого множества из этого подсемейства приводит к тому, что оно имеет непустое пересечение. Следовательно, это минимальное подсемейство с пустым пересечением. В нем четыре набора, и это максимально возможное минимальное подсемейство с пустым пересечением, поэтому семейство всех подмножеств набора { a , b , c , d } является семейством Хелли порядка 4.
• Пусть I — конечное множество отрезков вещественной прямой с пустым пересечением. Пусть A — интервал, левый конец которого a как можно больше, и пусть B — интервал, правый конец которого b как можно меньше. Тогда, если бы a было меньше или равно b , все числа в диапазоне [ a , b ] принадлежали бы всем интервалам I , нарушая предположение, что пересечение I пусто, поэтому должно быть так, что a > б . Таким образом, двухинтервальное подсемейство { A , B } имеет пустое пересечение, и семейство I не может быть минимальным, если только I = { A , B }. Следовательно, все минимальные семейства интервалов с пустыми пересечениями содержат два или меньше интервалов, что показывает, что множество всех интервалов является семейством Хелли порядка 2.
• Семейство бесконечных арифметических прогрессий целых чисел также обладает свойством 2-Хелли. То есть всякий раз, когда конечный набор прогрессий обладает свойством, что никакие две из них не являются непересекающимися, тогда существует целое число, принадлежащее всем им; это китайская теорема об остатках .

Формальное определение

Более формально, семейство Хелли порядка k — это система множеств ( V , E ), где E — набор подмножеств V это , такой, что для каждого конечного G ⊆ E с

$\bigcap _{X\in G}X=\varnothing ,$

мы можем найти H ⊆ G такую, что

$\bigcap _{X\in H}X=\varnothing$

и

$\left|H\right|\leq k.$

В некоторых случаях одно и то же определение справедливо для каждой подколлекции G независимо от ее конечности. Однако это более ограничительное условие. Например, открытые интервалы вещественной линии удовлетворяют свойству Хелли для конечных поднаборов, но не для бесконечных поднаборов: интервалы (0,1/ i ) (для i = 0, 1, 2, ...) имеют попарно непустые пересечения, но в целом иметь пустое пересечение.

Хелли-размер

Если семейство множеств является семейством Хелли порядка k , говорят, что это семейство имеет число Хелли k . Размерность Хелли метрического пространства на единицу меньше числа Хелли семейства метрических шаров в этом пространстве; Теорема Хелли подразумевает, что размерность Хелли евклидова пространства равна его размерности как реального векторного пространства .

Размерность Хелли подмножества S евклидова пространства, такого как многогранник, на единицу меньше числа Хелли семейства сдвигов S. Например, размерность Хелли любого гиперкуба равна 1, хотя такая форма может принадлежать евклидову пространству гораздо более высокой размерности.

Хелли-размерность также применялась к другим математическим объектам. Например, Домокос (2007) определяет размерность Хелли группы ( алгебраическую структуру, образованную обратимой и ассоциативной бинарной операцией) на единицу меньше, чем число Хелли семейства левых смежных классов группы.

Недвижимость Хелли

Если семейство непустых множеств имеет пустое пересечение, его число Хелли должно быть не менее двух, поэтому наименьшее значение k , для которого свойство k -Helly нетривиально, равно k = 2. Свойство 2-Helly также известно как свойство Хелли. . Семейство 2-Helly также известно как семейство Хелли .

Выпуклое , метрическое пространство в котором замкнутые шары обладают свойством 2-Хелли (то есть пространство с размерностью Хелли 1 в более сильном варианте размерности Хелли для бесконечных подмножеств), называется инъективным или гипервыпуклым. Существование узкой оболочки позволяет любому метрическому пространству изометрически вкладываться в пространство с размерностью Хелли 1.

Свойство Хелли в гиперграфах

Гиперграф . эквивалентен семейству множеств В терминах гиперграфов гиперграф H = ( V , E ) обладает свойством Хелли , если для каждых n гиперребер $e_{1},\ldots ,e_{n}$ в E , если $\forall i,j\in [n]:e_{i}\cap e_{j}\neq \emptyset$, затем $e_{1}\cap \cdots \cap e_{n}\neq \emptyset$. Для каждого гиперграфа H следующие условия эквивалентны:

• H обладает свойством Хелли, а граф пересечений H (простой граф, в котором вершины — E , а два элемента E связаны тогда и только тогда, когда они пересекаются) — совершенный граф .
• Каждый частичный гиперграф H (т. е. гиперграф, полученный из H путем удаления некоторых гиперребер) обладает свойством Кенига , т. е. его максимальный размер соответствия равен минимальному трансверсальному размеру.
• Каждый частичный гиперграф H обладает тем свойством, что его максимальная степень равна минимальному числу раскраски ребер .