Piekielna rodzina

W kombinatoryce rodzina Helly'ego rzędu $k$ to rodzina zbiorów , w której każda minimalna podrodzina z pustym przecięciem ma w sobie $k$ lub mniej zbiorów. Równoważnie, każda skończona podrodzina taka, że każde $k$ -krotne przecięcie jest niepuste, ma niepuste całkowite przecięcie. Własność $k$ -Helly jest własnością rodziny Helly rzędu $k$ .

Liczba $k$ jest często pomijana w tych nazwach w przypadku, gdy $k = 2$ . Zatem rodzina zestawów $jeśli$ , dla $zestawów$ w , ${\ Displaystyle \ forall i, j \ in [n]: s_ {i} \ cap s_ {j} \ neq \ pusty zbiór}, a następnie s 1 ∩ ⋯ ∩ s$ n $\ cdots \cap s_{n}\neq \emptyset}$ .

Koncepcje te zostały nazwane na cześć Eduarda Helly'ego (1884–1943); Twierdzenie Helly'ego o zbiorach wypukłych , które dało początek temu pojęciu, mówi, że zbiory wypukłe w przestrzeni euklidesowej o wymiarze $n$ są rodziną Helly'ego rzędu $n + 1$ .

Przykłady

W rodzinie wszystkich podzbiorów zbioru { a , b , c , d } podrodzina {{ a , b , c }, { a , b , d }, { a , c , d }, { b , c , D }} ma puste przecięcie, ale usunięcie dowolnego zestawu z tej podrodziny powoduje, że ma ono niepuste przecięcie. Jest to więc podrodzina minimalna z pustym przecięciem. Ma w sobie cztery zbiory i jest największą możliwą minimalną podrodziną z pustym przecięciem, więc rodzina wszystkich podzbiorów zbioru { a , b , c , d } jest rodziną Helly'ego rzędu 4.
Niech I będzie skończonym zbiorem domkniętych przedziałów prostej rzeczywistej z pustym przecięciem. Niech A będzie przedziałem, którego lewy koniec a jest jak największy, a B niech będzie przedziałem, którego prawy koniec b jest możliwie najmniejszy. Wtedy, gdyby a było mniejsze lub równe b , wszystkie liczby z przedziału [ a , b ] należałyby do wszystkich przedziałów I , łamiąc założenie, że przecięcie I jest puste, więc musi być tak, że a > b . Zatem podrodzina dwuprzedziałowa { A , B } ma puste przecięcie, a rodzina I nie może być minimalna, chyba że I = { A , B }. Dlatego wszystkie minimalne rodziny przedziałów z pustymi przecięciami mają w sobie dwa lub mniej przedziałów, co pokazuje, że zbiór wszystkich przedziałów jest rodziną Helly'ego rzędu 2.
Rodzina nieskończonych ciągów arytmetycznych liczb całkowitych ma również właściwość 2-Helly. To znaczy, ilekroć skończony zbiór postępów ma tę właściwość, że żadne dwa z nich nie są rozłączne, to istnieje liczba całkowita, która należy do nich wszystkich; to jest chińskie twierdzenie o resztach .

Definicja formalna

Bardziej formalnie, rodzina Helly'ego rzędu k jest systemem zbiorów ( V , E ), gdzie E jest zbiorem podzbiorów V , takim, że dla każdego skończonego G ⊆ E z

{\ Displaystyle \ bigcap _ {X \ w G} X = \ varnothing,}

możemy znaleźć H ⊆ G takie, że

{\ Displaystyle \ bigcap _ {X \ w H} X = \ varnothing}

I

{\ Displaystyle \ lewo | H \ prawo | \ równoważnik k.}

W niektórych przypadkach ta sama definicja obowiązuje dla każdego podzbioru G , niezależnie od skończoności. Jest to jednak warunek bardziej restrykcyjny. Na przykład otwarte przedziały linii rzeczywistej spełniają właściwość Helly'ego dla skończonych podzbiorów, ale nie dla nieskończonych podzbiorów: przedziały (0,1/ i ) (dla i = 0, 1, 2, ...) mają parami niepuste skrzyżowaniach, ale mają puste ogólne skrzyżowanie.

Piekielny wymiar

Jeśli rodzina zbiorów jest rodziną Helly'ego rzędu k , to mówi się, że rodzina ta ma liczbę Helly'ego k . Wymiar Helly przestrzeni metrycznej jest o jeden mniejszy niż liczba Helly rodziny kul metrycznych w tej przestrzeni; Twierdzenie Helly'ego implikuje, że wymiar Helly'ego przestrzeni euklidesowej jest równy jej wymiarowi jako rzeczywistej przestrzeni wektorowej .

Wymiar Helly podzbioru S przestrzeni euklidesowej, takiej jak wielościan, jest o jeden mniejszy niż liczba Helly rodziny translacji S. Na przykład wymiar Helly dowolnego hipersześcianu wynosi 1, mimo że taki kształt może należą do przestrzeni euklidesowej o znacznie wyższym wymiarze.

Wymiar Helly został również zastosowany do innych obiektów matematycznych. Na przykład Domokos (2007) definiuje wymiar Helly'ego grupy (struktury algebraicznej utworzonej przez odwracalną i asocjacyjną operację binarną) jako jeden mniejszy niż liczba Helly'ego rodziny lewych cosetów grupy.

Posiadłość Helly

Jeśli rodzina niepustych zbiorów ma puste przecięcie, jej liczba Helly musi wynosić co najmniej dwa, więc najmniejsze k , dla którego właściwość k -Helly jest nietrywialna, to k = 2. Właściwość 2-Helly jest również znana jako właściwość Helly . Rodzina 2-Helly jest również znana jako rodzina Helly .

Wypukła przestrzeń metryczna , w której zamknięte kule mają właściwość 2-Helly (to znaczy przestrzeń o wymiarze Helly 1, w silniejszym wariancie wymiaru Helly dla nieskończonych podzbiorów) nazywana jest iniekcją lub hiperwypukłą. Istnienie ciasnej rozpiętości pozwala na izometryczne osadzenie dowolnej przestrzeni metrycznej w przestrzeni o wymiarze Helly 1.

Właściwość Helly w hipergrafach

Hipergraf jest odpowiednikiem rodziny zestawów. W kategoriach hipergrafów hipergraf H = ( V , mi ) ma właściwość Helly , jeśli dla każdego n hiperkrawędzi mi ${\ Displaystyle e_ {1}, \ ldots, e_ {n}}$ mi , jeśli $\ cdots \cap e_{n}\neq \emptyset}$ $\ forall i, j \ in [n]: e_ {i} \ cap e_ {j} \ neq \ pusty zestaw} , a następnie mi 1 ∩ ⋯ ∩ mi n$ ≠ . Dla każdego hipergrafu H następujące są równoważne:

H ma właściwość Helly, a graf przecięcia H (prosty graf, w którym wierzchołki to E , a dwa elementy E są połączone, jeśli się przecinają) jest grafem doskonałym .
Każdy hipergraf cząstkowy H (tj. hipergraf wyprowadzony z H przez usunięcie niektórych hipergrafów) ma właściwość Koniga , tj. jego maksymalny rozmiar dopasowania jest równy minimalnemu rozmiarowi poprzecznemu .
Każdy hipergraf cząstkowy H ma tę właściwość, że jego maksymalny stopień jest równy minimalnemu numerowi zabarwienia krawędzi .