Семья Хелли - Helly family

В комбинаторика, а Семейство порядка Хелли k - такое семейство множеств, что любое минимальное подсемейство с пустым пересечением имеет k или меньше наборов в нем. Эквивалентно каждое конечное подсемейство такое, что каждое ${\displaystyle k}$-кратное пересечение непусто, имеет непустое полное пересечение.^[1] В k-Хелли недвижимость это собственность порядочной семьи Хелли k.^[2]

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

Эти концепции названы в честь Эдуард Хелли (1884-1943); Теорема Хелли на выпуклые множества, породившее это понятие, утверждает, что выпуклые множества в Евклидово пространство измерения п семья порядка Хелли п + 1.^[1]

Примеры

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

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

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

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

мы можем найти ЧАС ⊆ г такой, что

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

и

${\displaystyle \left|H\right|\leq k.}$^[1]

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

Измерение Хелли

Если семейство наборов является семейством порядка Хелли k, эта семья, как говорят, Номер Хелли k. В Измерение Хелли из метрическое пространство на единицу меньше числа Хелли семейства метрических шаров в этом пространстве; Теорема Хелли означает, что размерность Хелли евклидова пространства равна его размерности как действительного векторное пространство.^[4]

В Измерение Хелли подмножества S евклидова пространства, такого как многогранник, на единицу меньше числа Хелли семейства переводит С.^[5] Например, измерение Хелли любого гиперкуб равно 1, даже если такая форма может принадлежать евклидову пространству гораздо более высокого измерения.^[6]

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

Свойство Хелли

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

А выпуклый метрическое пространство в котором закрытый мячи обладают свойством 2-Хелли (то есть пространство с размерностью Хелли 1 в более сильном варианте размерности Хелли для бесконечных подколлекций) называется инъективный или гипервыпуклый.^[8] Существование тесный промежуток позволяет изометрически вложить любое метрическое пространство в пространство с размерностью Хелли 1.^[9]

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

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

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

использованная литература

1. Боллобаш, Бела (1986), Комбинаторика: системы множеств, гиперграфы, семейства векторов и комбинаторная вероятность, Cambridge University Press, стр. 82, ISBN  9780521337038.
2. Duchet, Pierre (1995), «Hypergraphs», в Graham, R.L .; Грётшель, М.; Ловас, Л. (ред.), Справочник по комбинаторике, Vol. 1, 2, Амстердам: Elsevier, стр. 381–432, Г-Н  1373663. См., В частности, Раздел 2.5 «Собственность Helly», стр. 393–394.
3. Это одномерный случай теоремы Хелли. По существу это доказательство с красочной формулировкой, включающей спящих студентов, см. Савчев, Святослав; Андрееску, Титу (2003), "27 Теорема Хелли для одномерного измерения", Математические миниатюры, Новая математическая библиотека, 43, Математическая ассоциация Америки, стр. 104–106, ISBN  9780883856451.
4. Мартини, Хорст (1997), Экскурсии в комбинаторную геометрию, Springer, стр. 92–93, ISBN  9783540613411.
5. Бездек, Карой (2010), Классические темы по дискретной геометрии, Springer, стр. 27, ISBN  9781441906007.
6. С.-Надь, Бела (1954), "Ein Satz über Parallelverschiebungen konvexer Körper", Acta Universitatis Szegediensis, 15: 169–177, Г-Н  0065942, заархивировано из оригинал на 2016-03-04, получено 2013-09-10.
7. Домокос, М. (2007), "Типичные разделяющие инварианты", Группы трансформации, 12 (1): 49–63, arXiv:математика / 0511300, Дои:10.1007 / s00031-005-1131-4, Г-Н  2308028.
8. Деза, Мишель Мари; Деза, Елена (2012), Энциклопедия расстояний, Springer, стр. 19, ISBN  9783642309588
9. Исбелл, Дж. Р. (1964), «Шесть теорем об инъективных метрических пространствах», Комментарий. Математика. Helv., 39: 65–76, Дои:10.1007 / BF02566944.
10. Ловас, Ласло; Пламмер, М. (1986), Теория соответствия, Анналы дискретной математики, 29, Северная Голландия, ISBN  0-444-87916-1, Г-Н  0859549