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

редактировать

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

Число k часто опускается в этих именах в случае, когда k = 2. Таким образом, набор -семейство имеет свойство Helly, если для каждого n задается s 1,…, sn {\ displaystyle s_ {1}, \ ldots, s_ {n}}{\ displaystyle s_ {1}, \ ldots, s_ {n}} в семья, если ∀ я, j ∈ [n]: si ∩ sj ≠ ∅ {\ displaystyle \ forall i, j \ in [n]: s_ {i} \ cap s_ {j} \ neq \ emptyset}{\ displaystyle \ для всех i, j \ in [n]: s_ {i} \ cap s_ {j} \ neq \ em ptyset} , затем s 1 ∩ ⋯ ∩ sn ≠ ∅ {\ displaystyle s_ {1} \ cap \ cdots \ cap s_ {n} \ neq \ emptyset}{\ displaystyle s_ {1} \ cap \ cdots \ cap s_ {n} \ neq \ emptyset} .

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

Содержание
  • 1 Примеры
  • 2 Формальное определение
  • 3 Измерение Helly
  • 4 Свойство Helly
  • 5 Свойство Helly в гиперграфах
  • 6 Ссылки
Примеры
  • В семействе всех подмножеств множества {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-Helly. То есть, всякий раз, когда конечный набор прогрессий обладает тем свойством, что никакие две из них не пересекаются, тогда существует целое число, которое принадлежит всем из них; это китайская теорема об остатке.
Формальное определение

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

⋂ X ∈ GX = ∅, {\ displaystyle \ bigcap _ {X \ in G} X = \ varnothing,}\ bigcap _ {{X \ in G}} X = \ varnothing,

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

⋂ X ∈ HX = ∅ {\ displaystyle \ bigcap _ {X \ in H} X = \ varnothing}\ bigcap _ {{X \ in H} } X = \ varnothing

и

| H | ≤ к. {\ displaystyle \ left | H \ right | \ leq k.}\ left | H \ right | \ leq k.

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

Размерность Хелли

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

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

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

Свойство Helly

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

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

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

A гиперграфе эквивалентно набор-семья. В терминах гиперграфов гиперграф H = (V, E) обладает свойством Хелли, если для каждого n гиперребер e 1,…, en {\ displaystyle e_ {1}, \ ldots, e_ { n}}e_ {1}, \ ldots, e_ {n } в E, если ∀ i, j ∈ [n]: ei ∩ ej ≠ ∅ {\ displaystyle \ forall i, j \ in [n]: e_ {i} \ cap e_ {j} \ neq \ emptyset}{\ displaystyle \ forall i, j \ in [n]: e_ {i} \ cap e_ {j} \ neq \ emptyset} , затем e 1 ∩ ⋯ ∩ en ≠ ∅ {\ displaystyle e_ {1} \ cap \ cdots \ cap e_ {n} \ neq \ emptyset}{\ displaystyle e_ {1} \ cap \ cdots \ cap e_ {n} \ neq \ emptyset} . Для каждого гиперграфа H следующие условия эквивалентны:

  • H обладает свойством Хелли, а граф пересечений H (простой граф, в котором вершинами являются E, а два элемента E связаны, если они пересекаются), является идеальный граф.
  • Каждый частичный гиперграф H (т. е. гиперграф, полученный из H путем удаления некоторых гиперребер) имеет свойство Konig, т. е. его максимальный - соответствующий размер равен его минимальный- поперечный размер.
  • Каждый частичный гиперграф H обладает тем свойством, что его максимальная степень равна его минимальному числу окраски краев.
Ссылки
Последняя правка сделана 2021-05-23 07:56:02
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте