Семейство Хелли
Семейство Хелли порядка k — это семейство множеств со свойством, что любое минимальное подсемейство с пустым пересечением имеет k или меньше множеств. Эквивалентно, любое конечное подсемейство со свойством, что любое пересечение k множеств не пусто, имеет непустое общее пересечение[1].
Говорят, что семейство k-хеллево, если оно является семейством Хелли порядка k[2]. Понятие получило название по имени математика Эдуарда Хелли (1884—1943). Теорема Хелли о выпуклых множествах, которая и побудила ввести понятие, утверждает, что выпуклые множества в евклидовом пространстве размерности n являются семейством Хелли порядка n + 1[1]. Число k часто опускается, когда обсуждается случай k = 2.
Примеры
- В семействе всех подмножеств множества {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 = { A, B}. Поэтому все минимальные семейства интервалов с пустыми пересечениями имеют два или менее интервалов, что показывает, что множество всех интервалов является семейством Хелли порядка 2[3].
- Семейство бесконечных арифметических прогрессий целых чисел также 2-хеллево. То есть, если конечный набор прогрессий имеет свойство, что любые два из них имеют общий член, то существует целое число, принадлежащее всем прогрессиям семейства. А это как раз китайская теорема об остатках[2].
Формальное определение
Более формально, семейство Хелли порядка k — это семейство множеств (F, E), где F — набор подмножеств из E со свойством, что для любого конечного набора G ⊆ F выполняется
мы можем найти набор H ⊆ G, такой, что
и
В некоторых случаях то же определение рассматривается для любых подколлекций G, не предполагая конечность. Однако такое определение является более сильным ограничивающим определением. Например, открытые интервалы вещественной оси удовлетворяют свойству Хелли для конечных подколлекций, но не для бесконечных — интервалы (0,1/i) (для i = 1, 2, 3, ...) имеют попарное непустое пересечение, но пересечение всех таких интервалов пусто.
Размерность Хелли
Если семейство множеств является семейством Хелли порядка k, то говорят, что семейство имеет число Хелли k. Размерность Хелли метрического пространства на единицу меньше числа Хелли семейства метрических шаров этого пространства. Из теоремы Хелли следует, что размерность Хелли евклидового пространства равна его размерности как вещественного векторного пространства[4].
Размерность Хелли подмножества S евклидового пространства, такого как многогранник, на единицу меньше числа Хелли семейства параллельных переносов S[5]. Например, размерность Хелли любого гиперкуба равна 1, даже если такая фигура находится в евклидовом пространстве очень высокой размерности[6].
Размерность Хелли применима и к другим математическим объектам. Например, Домокос[7] определяет размерность Хелли для группы (алгебраической структуры, образованной обратимой и ассоциативной двуместной операцией) на единицу меньше размерности Хелли семейства левых смежных классов группы[8].
Свойство Хелли
Если семейство непустых множеств имеет пустое пересечение, его число Хелли должно быть не меньше двух, так что наименьшее k, для которого случай не является тривиальным, равно 2. Свойство 2-хеллевости известно также как свойство Хелли. 2-хеллево семейство известно как хеллево семейство[1][2].
Метрическое пространство, в котором замкнутые шары 2-хеллевы (то есть это пространство с размерностью Хелли 1) называется инъективным или гипервыпуклым[9]. Существование плотной оболочки позволяет вложить любое метрическое пространство в пространство с размерностью Хелли 1[10].
Примечания
- Bollobás, 1986, с. 82.
- Duchet, 1995, с. 381–432.
- Это одномерный случай теоремы Хелли. По сути этого доказательства, включая цветастые фразы о спящих студентах, читайте статью Савчева и Андрееску (Savchev, Andreescu 2003, С. 104–106).
- Martini, 1997, с. 92–93.
- Bezdek, 2010, с. 27.
- Sz.-Nagy, 1954, с. 169–177.
- Domokos, 2007.
- Domokos, 2007, с. 49–63.
- M.&E. Deza, 2012, с. 19.
- Isbell, 1964, с. 65–76.
Литература
- Béla Bollobás. Combinatorics: Set Systems, Hypergraphs, Families of Vectors, and Combinatorial Probability. — Cambridge University Press, 1986. — С. 82. — ISBN 9780521337038.
- Pierre Duchet. Hypergraphs // Handbook of combinatorics, Vol. 1, 2 / R. L. Graham, M. Grötschel, L. Lovász,. — Amsterdam: Elsevier, 1995. — С. 381–432.. См., в частности, раздел 2.5, "Helly Property", pp. 393–394
- Svetoslav Savchev, Titu Andreescu. 27 Helly's Theorem for One Dimension // Mathematical Miniatures. — Mathematical Association of America, 2003. — Т. 43. — С. 104–106. — (New Mathematical Library). — ISBN 9780883856451.
- Horst Martini. Excursions Into Combinatorial Geometry. — Springer, 1997. — С. 92–93. — ISBN 9783540613411.
- Károly Bezdek. Classical Topics in Discrete Geometry. — Springer, 2010. — С. 27. — ISBN 9781441906007.
- Béla Sz.-Nagy. Ein Satz über Parallelverschiebungen konvexer Körper // Acta Universitatis Szegediensis. — 1954. — Т. 15. — С. 169–177. Архивировано 4 марта 2016 года.
- M. Domokos. Typical separating invariants // Transformation Groups. — 2007. — Т. 12. — С. 49–63. — doi:10.1007/s00031-005-1131-4. — arXiv:math/0511300.
- John R. Isbell. Six theorems about injective metric spaces // Comment. Math. Helv.. — 1964. — Т. 39. — С. 65–76. — doi:10.1007/BF02566944.
- Michel Marie Deza, Elena Deza. Encyclopedia of Distances. — Springer, 2012. — С. 19. — ISBN 9783642309588.