Семья Хелли

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

Число $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$ . ^[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. ^[3]
Семейство бесконечных арифметических прогрессий целых чисел также обладает свойством 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.

^[1]

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

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

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

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

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

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

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

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

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

Гиперграф . эквивалентен семейству множеств В терминах гиперграфов гиперграф 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$ . ^[10]^: 467 Для каждого гиперграфа H следующие условия эквивалентны: ^[10]^{: 470–471}

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

Ссылки

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

[b86-1] Перейти обратно: ^а ^б ^с ^д Боллобас, Бела (1986), Комбинаторика: системы множеств, гиперграфы, семейства векторов и комбинаторная вероятность , Cambridge University Press, стр. 82, ISBN 9780521337038 .

[d95-2] Перейти обратно: ^а ^б ^с Дюше, Пьер (1995), «Гиперграфы», в Грэме, РЛ; Гретшель, М .; Ловас Л. (ред.), Справочник по комбинаторике, Vol. 1, 2 , Амстердам: Elsevier, стр. 381–432, MR 1373663 . См., в частности, раздел 2.5 «Собственность Хелли», стр. 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), «Теорема о параллельных смещениях выпуклых тел» , Acta Universitatis Szegediensis , 15 : 169–177, MR 0065942 , заархивировано из оригинала 04 марта 2016 г. , получено 9 сентября 2013 г. 10 .

[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] Исбелл, Дж. Р. (1964), «Шесть теорем об инъективных метрических пространствах», Комментарий. Математика. Хелв. , 39 : 65–76, doi : 10.1007/BF02566944 .

[lp-10] Перейти обратно: ^а ^б Ловас, Ласло ; Пламмер, доктор медицинских наук (1986), Теория соответствия , Анналы дискретной математики, том. 29, Северная Голландия, ISBN 0-444-87916-1 , МР 0859549

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]