Helly familj

En Helly-familj av ordning k är en familj av uppsättningar med egenskapen att varje minimal underfamilj med tom skärningspunkt har k eller färre uppsättningar. På motsvarande sätt har varje ändlig underfamilj med egenskapen att varje skärning av k -mängder är icke-tom en icke-tom gemensam skärningspunkt [1] .

En familj k sägs vara Helle om det är en Helly-familj av ordning k [2] . Konceptet fick sitt namn efter matematikern Edward Helly (1884-1943). Helly-satsen om konvexa mängder , som föranledde introduktionen av begreppet, säger att konvexa mängder i ett euklidiskt utrymme av dimension n är en Helly-familj av ordningen n  + 1 [1] . Talet k utelämnas ofta när man diskuterar fallet k  = 2.

Exempel

• I familjen av alla delmängder av mängden {a,b,c,d}, underfamiljen {{a,b,c}, {a,b,d}, {a,c,d}, {b,c ,d}} har en tom korsning, men att ta bort en uppsättning från denna underfamilj resulterar i en icke-tom korsning. Därmed är familjen en minimal underfamilj med en tom korsning. Familjen innehåller fyra uppsättningar och är den största möjliga minimala underfamiljen med tom skärningspunkt, så familjen av alla delmängder av mängden {a,b,c,d} är en Helly-familj av ordning 4.
• Låt jag vara en ändlig uppsättning slutna intervall av den reella axeln med tom skärningspunkt. Låt A vara intervallet vars vänstra ändpunkt a är maximum, och B intervallet vars högra ändpunkt b är minimum. Då, om a är mindre än eller lika med b , tillhör alla tal i intervallet [ a , b ] alla intervall i mängden I , vilket motsäger tomhetsvillkoret för skärningen av intervall från I , så att olikheten a  >  b måste hålla . Således har delmängden { A , B } som innehåller två intervall en tom skärningspunkt, och familjen kan inte vara minimal om inte I  = { A , B }. Därför har alla minimala familjer av intervall med tomma skärningspunkter två eller färre intervall, vilket visar att mängden av alla intervall är en Helly-familj av ordningen 2 [3] .
• Familjen av oändliga aritmetiska progressioner av heltal är också 2-Helvete. Det vill säga, om en ändlig uppsättning av progressioner har egenskapen att två av dem har en gemensam term, så finns det ett heltal som tillhör alla progressioner i familjen. Och detta är bara den kinesiska restsatsen [2] .

Formell definition

Mer formellt är en Helly-familj av ordningen k en familj av mängder ( F ,  E ), där F är en mängd delmängder av E med egenskapen att, för varje finit mängd G ⊆ F ,

vi kan hitta en mängd H ⊆ G sådan att

och

I vissa fall övervägs samma definition för alla undersamlingar av G utan att anta ändlighet. En sådan definition är dock en starkare restriktiv definition. Till exempel, öppna intervall för den reella axeln uppfyller Helly-egenskapen för finita delsamlingar, men inte för oändliga - intervallen (0,1/ i ) (för i = 1, 2, 3, ...) har ett parvis icke -tom skärningspunkt, men skärningspunkten för alla sådana intervall är tom.

Helly dimension

Om en familj av mängder är en Helly-familj av ordningen k , sägs familjen ha ett Helly-nummer k . Helly-dimensionen för ett metriskt utrymme är en mindre än Helly-talet för familjen av metriska bollar i detta utrymme. Det följer av Hellys sats att Helly-dimensionen av ett euklidiskt rum är lika med dess dimension som ett verkligt vektorrum [4] .

Helly-dimensionen för en delmängd S av ett euklidiskt utrymme, såsom en polyeder, är en mindre än Helly-talet för familjen av parallella översättningar S [5] . Till exempel är Helly-dimensionen för en hyperkub 1, även om en sådan figur befinner sig i ett mycket högdimensionellt euklidiskt utrymme [6] .

Helly-dimensionen gäller även för andra matematiska objekt. Till exempel, Domokos [7] definierar Helly-dimensionen av en grupp (en algebraisk struktur som bildas av en inverterbar och associativ två-plats-operation) till att vara en mindre än Helly-dimensionen av familjen av vänster cosets i gruppen [8] .

Helly egendom

Om en familj av icke-tomma uppsättningar har en tom skärningspunkt måste dess Helly-nummer vara minst två, så det minsta k för vilket fallet inte är trivialt är 2. Egenskapen 2-Helly är också känd som Helly-egenskapen . En 2-Hell-familj är känd som en helvetesfamilj [1] [2] .

Ett metriskt utrymme där de slutna kulorna är 2-Hell (det vill säga ett utrymme med Helly dimension 1) kallas injektiv eller hyperkonvex [9] . Förekomsten av ett tätt skal tillåter en att bädda in vilket metriskt utrymme som helst i ett utrymme med Helly dimension 1 [10] .

Anteckningar

1. ↑ 1 2 3 4 Bollobás, 1986 , sid. 82.
2. ↑ 1 2 3 Duchet, 1995 , sid. 381–432.
3. ↑ Detta är ett endimensionellt fall av Hellys teorem. För kärnan i detta bevis, inklusive de färgglada fraserna om sovande elever, se artikeln av Savchev och Andreescu ( Savchev, Andreescu 2003 , s. 104–106).
4. ↑ Martini, 1997 , sid. 92–93.
5. ↑ Bezdek, 2010 , sid. 27.
6. ↑ Sz.-Nagy, 1954 , sid. 169–177.
7. ↑ Domokos, 2007 .
8. ↑ Domokos, 2007 , sid. 49–63.
9. ↑ M.&E. Deza, 2012 , sid. 19.
10. ↑ Isbell, 1964 , sid. 65–76.

Litteratur

• Bela Bollobas. Kombinatorik: Setsystem, hypergrafer, vektorfamiljer och kombinatorisk sannolikhet . - Cambridge University Press, 1986. - S. 82. - ISBN 9780521337038 .
• Pierre Duchet. Hypergrafer // Handbook of combinatorics, Vol. 1, 2 / R.L. Graham, M. Grötschel, L. Lovász,. - Amsterdam: Elsevier, 1995. - S. 381-432. . Se särskilt avsnitt 2.5, "Helly Property", s. 393–394
• Svetoslav Savchev, Titu Andreescu. 27 Hellys sats för en dimension // Matematiska miniatyrer . - Mathematical Association of America, 2003. - V. 43. - S. 104-106. - (Nytt matematiskt bibliotek). — ISBN 9780883856451 .
• Horst Martini. Utflykter i kombinatorisk geometri . - Springer, 1997. - S. 92-93. — ISBN 9783540613411 .
• Karoly Bezdek. Klassiska ämnen i diskret geometri . - Springer, 2010. - P. 27. - ISBN 9781441906007 .
• Bela Sz.-Nagy. Ein Satz über Parallelverschiebungen konvexer Körper  // Acta Universitatis Szegediensis. - 1954. - T. 15 . — S. 169–177 . Arkiverad från originalet den 4 mars 2016.
• M. Domokos. Typiska separerande invarianter // Transformationsgrupper. - 2007. - T. 12 . — s. 49–63 . - doi : 10.1007/s00031-005-1131-4 . - arXiv : math/0511300 .
• John R. Isbell. Sex satser om injektiva metriska rum // Kommentar. Matematik. Helv.. - 1964. - T. 39 . — S. 65–76 . - doi : 10.1007/BF02566944 .
• Michel Marie Deza, Elena Deza. Encyclopedia of Distances . - Springer, 2012. - P. 19. - ISBN 9783642309588 .