Семья Хелли

Семейство множеств, где каждое непересекающееся подсемейство имеет k или меньше множеств

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

Число k часто опускается из этих названий в случае, если k = 2. Таким образом, множество-семейство обладает свойством Хелли , если для каждого n множеств в семействе, если , то . ${\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); теорема Хелли о выпуклых множествах , которая привела к появлению этого понятия, утверждает, что выпуклые множества в евклидовом пространстве размерности n являются семейством Хелли порядка n + 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 будет интервалом, левая конечная точка a которого максимально велика, и пусть B будет интервалом, правая конечная точка b которого максимально мала. Тогда, если бы a было меньше или равно b , все числа в диапазоне [ a , b ] принадлежали бы всем интервалам I , нарушая предположение о том, что пересечение I пусто, поэтому должно быть так, что a  >  b . Таким образом, двухинтервальное подсемейство { A , B } имеет пустое пересечение, и семейство I не может быть минимальным, если только I  = { A , B }. Следовательно, все минимальные семейства интервалов с пустыми пересечениями имеют в себе два или меньше интервалов, показывая, что множество всех интервалов является семейством Хелли порядка 2. ^[3]
• Семейство бесконечных арифметических прогрессий целых чисел также обладает свойством 2-Хелли. То есть, всякий раз, когда конечный набор прогрессий обладает свойством, что никакие две из них не являются непересекающимися, то существует целое число, которое принадлежит им всем; это китайская теорема об остатках . ^[2]

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

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

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

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

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

и

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

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

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

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

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

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

Собственность Хелли

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

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

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

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

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

Ссылки

1. Боллобаш, Бела (1986), Комбинаторика: системы множеств, гиперграфы, семейства векторов и комбинаторная вероятность, Cambridge University Press, стр. 82, ISBN 9780521337038.
2. Duchet, Пьер (1995), «Гиперграфы», в Грэме, РЛ; Гретшель, М .; Ловас Л. (ред.), Справочник по комбинаторике, Vol. 1, 2 , Амстердам: Elsevier, стр. 381–432, MR  1373663.. См. в частности раздел 2.5 «Адская собственность», стр. 393–394.
3. Это одномерный случай теоремы Хелли. По существу это доказательство, с красочной формулировкой, включающей спящих студентов, см. Savchev, Svetoslav; Andreescu, Titu (2003), "27 Helly's Theorem for One Dimension", Mathematical Miniatures, New Mathematical Library, т. 43, Mathematical Association of America, стр. 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, MR  0065942, заархивировано из оригинала 04 марта 2016 г. , получено 10 сентября 2013 г..
7. Домокос, М. (2007), «Типичные разделяющие инварианты», Группы преобразований , 12 (1): 49–63, arXiv : math/0511300 , doi :10.1007/s00031-005-1131-4, MR  2308028.
8. Деза, Мишель Мари ; Деза, Елена (2012), Энциклопедия расстояний, Springer, стр. 19, ISBN 9783642309588
9. Isbell, JR (1964), «Шесть теорем об инъективных метрических пространствах», Comment. Math. Helv. , 39 : 65–76, doi :10.1007/BF02566944.
10. Ловас, Ласло ; Пламмер, доктор медицины (1986), Теория соответствия , Анналы дискретной математики, том. 29, Северная Голландия, ISBN 0-444-87916-1, МР  0859549