Из Википедии, бесплатной энциклопедии
  (Перенаправлено из свойства Helly )
Перейти к навигации Перейти к поиску

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

Число k часто опускается в этих именах в случае, когда k  = 2. Таким образом, семейство множеств обладает свойством Helly if для каждого n множеств в семействе, if , then .

Эти концепции названы в честь Эдуарда Хелли (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]

Формальное определение [ править ]

Более формально, А семейство Хелло порядка к является множество системы ( V, Е ) с Й совокупностью подмножеств из V , такие , что для любого конечного G ⊆ E с

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

а также

[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 также известно как свойство Helly . Семья 2-Хелли также известна как семья Хелли . [1] [2]

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

Свойство Helly в гиперграфах [ править ]

Гиперграф эквивалентно множеству-семьи. В терминах гиперграфов гиперграф H = ( V , E ) обладает свойством Хелли, если для каждого n гиперребер в E , если , то . [10] : 467 Для любого гиперграфа H следующие утверждения эквивалентны: [10] : 470–471

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

Ссылки [ править ]

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