Helly-familien - Helly family

I kombinatorikk er en Helly-familie av orden k en familie av sett der hver minimal underfamilie med et tomt skjæringspunkt har k eller færre sett i seg. Tilsvarende har hver endelig underfamilie slik at hvert foldekryss er ikke-tomt, har ikke-tomt kryss. Den k - Helly egenskap er egenskapen av å være en Helly familie av orden k . ${\ displaystyle k}$

Antallet k blir ofte utelatt fra disse navnene i tilfelle k  = 2. Dermed har en settfamilie Helly-egenskapen hvis for hvert n sett i familien, hvis , da . ${\ displaystyle s_ {1}, \ ldots, s_ {n}}$${\ displaystyle \ forall i, j \ in [n]: s_ {i} \ cap s_ {j} \ neq \ emptyset}$${\ displaystyle s_ {1} \ cap \ cdots \ cap s_ {n} \ neq \ emptyset}$

Disse begrepene er oppkalt etter Eduard Helly (1884–1943); Hellys teorem om konvekse sett , som ga opphav til denne forestillingen, sier at konvekse sett i euklidisk rom med dimensjon n er en Helly-familie av orden n  + 1.

Eksempler

• I familien av alle delmengder av settet { a , b , c , d }, underfamilien {{ a , b , c }, { a , b , d }, { a , c , d }, { b , c , d }} har et tomt skjæringspunkt, men når du fjerner et sett fra denne underfamilien, får det et ikke-fritt skjæringspunkt. Derfor er det en minimal underfamilie med et tomt kryss. Den har fire sett i seg, og er den største mulige minimale underfamilien med et tomt skjæringspunkt, så familien til alle delmengder av settet { a , b , c , d } er en Helly-familie av orden 4.
• La meg være et endelig sett med lukkede intervaller av den virkelige linjen med et tomt skjæringspunkt. La A være intervallet hvis venstre endepunkt a er så stort som mulig, og la B være intervallet hvis høyre endepunkt b er så lite som mulig. Så hvis a var mindre enn eller lik b , ville alle tallene i området [ a , b ] tilhøre alle intervallene til I , og bryte antagelsen om at skjæringspunktet til I er tomt, så det må være slik at en  >  b . Dermed har tointervallsfamilien { A , B } et tomt skjæringspunkt, og familien I kan ikke være minimal med mindre jeg  = { A , B }. Derfor har alle minimale familier med intervaller med tomme kryss to eller færre intervaller i seg, og viser at settet med alle intervaller er en Helly-familie av orden 2.
• Familien med uendelige aritmetiske progresjoner av heltall har også 2-Helly-egenskapen. Det vil si at når en endelig samling av progresjoner har den egenskapen at ingen av dem er usammenhengende, eksisterer det et heltall som tilhører dem alle; dette er den kinesiske restsatsen .

Formell definisjon

Mer formelt er en Helly-familie av ordre k et sett system ( V , E ), med E en samling av delmengder av V , slik at for hver endelige G ⊆ E med

${\ displaystyle \ bigcap _ {X \ in G} X = \ varnothing,}$

vi kan finne H ⊆ G slik at

${\ displaystyle \ bigcap _ {X \ in H} X = \ varnothing}$

og

${\ displaystyle \ left | H \ right | \ leq k.}$

I noen tilfeller gjelder den samme definisjonen for hver underkolleksjon G , uavhengig av finitet. Dette er imidlertid en mer restriktiv tilstand. For eksempel tilfredsstiller de åpne intervallene til den virkelige linjen Helly-egenskapen for endelige undersamlinger, men ikke for uendelige undersamlinger: intervallene (0,1 / i ) (for i = 0, 1, 2, ...) har ikke-ugyldige parvis kryss, men har et tomt samlet kryss.

Helly dimensjon

Hvis en familie med sett er en Helly-familie av ordre k , sies det at familien har Helly-nummer k . Den Helly dimensjon av en metrisk rom er én mindre enn antallet Helly av familien av metriske kulene i dette rom; Hellys teorem antyder at Helly-dimensjonen til et euklidisk rom er lik dimensjonen som et reelt vektorrom .

Den Helly dimensjon av en undergruppe S av en euklidsk plass, slik som et polyeder, er én mindre enn antallet Helly av familien av oversettes av S. For eksempel, Helly dimensjon av et hvilket som helst hypercube er 1, selv om en slik form kan tilhører et euklidisk rom med mye høyere dimensjon.

Helly dimensjon har også blitt brukt på andre matematiske objekter. For eksempel definerer Domokos (2007) Helly-dimensjonen til en gruppe (en algebraisk struktur dannet av en inverterbar og assosiativ binær operasjon) til å være en mindre enn Helly-tallet i familien av venstre kosetter i gruppen.

Helly-eiendommen

Hvis en familie med ikke-frie sett har et tomt skjæringspunkt, må Helly-nummeret være minst to, så den minste k som k -Helly-egenskapen ikke er privat er k  = 2. 2-Helly-egenskapen er også kjent som Helly-egenskapen . En 2-Helly-familie er også kjent som en Helly-familie .

Et konvekst metrisk rom der de lukkede kulene har 2-Helly-egenskapen (det vil si et rom med Helly-dimensjon 1, i den sterkere varianten av Helly-dimensjonen for uendelige undersamlinger) kalles injeksjons- eller hyperkonveks. Eksistensen av det stramme spennet gjør at ethvert metrisk rom kan integreres isometrisk i et rom med Helly-dimensjon 1.

Helly-egenskapen i hypergrafer

En hypergraf tilsvarer en settfamilie . I hypergrafiske termer har en hypergraf H = ( V , E ) Helly-egenskapen hvis for hver n hyperkant i E , hvis , da . For hver hypergraf H er følgende ekvivalente: ${\ displaystyle e_ {1}, \ ldots, e_ {n}}$${\ displaystyle \ forall i, j \ in [n]: e_ {i} \ cap e_ {j} \ neq \ emptyset}$${\ displaystyle e_ {1} \ cap \ cdots \ cap e_ {n} \ neq \ emptyset}$

• H har Helly-egenskapen, og skjæringsgrafen til H (den enkle grafen der hjørnene er E og to elementer av E er koblet sammen hvis de krysser hverandre) er en perfekt graf .
• Hvert delvise hypergrafi av H (dvs. et hypergrafi avledet fra H ved å slette noen hyperkanter) har egenskapen Konig , dvs. at den maksimale samsvarende størrelsen er lik den minste tverrgående størrelsen.
• Hvert delvise hypergrafi av H har den egenskapen at den maksimale graden tilsvarer det minste kantfargetallet .

Referanser