En combinatoria , una familia Helly de orden k es una familia de conjuntos tal que cualquier subfamilia mínima con una intersección vacía tiene k conjuntos o menos. De manera equivalente, cada subfamilia finita tal que cada-fold intersection is non-empty tiene una intersección total no vacía. [1] La propiedad k - Helly es la propiedad de ser una familia Helly de orden k . [2]
El número k se omite con frecuencia de estos nombres en el caso de que k = 2. Por lo tanto, una familia de conjuntos tiene la propiedad de Helly si para cada n conjuntos en la familia, si , luego .
Estos conceptos llevan el nombre de Eduard Helly (1884-1943); El teorema de Helly sobre conjuntos convexos , que dio lugar a esta noción, establece que los conjuntos convexos en el espacio euclidiano de dimensión n son una familia de Helly de orden n + 1. [1]
Ejemplos de
- En la familia de todos los subconjuntos del conjunto {a, b, c, d}, la subfamilia {{a, b, c}, {a, b, d}, {a, c, d}, {b, c , d}} tiene una intersección vacía, pero eliminar cualquier conjunto de esta subfamilia hace que tenga una intersección no vacía. Por lo tanto, es una subfamilia mínima con una intersección vacía. Tiene cuatro conjuntos y es la subfamilia mínima más grande posible con una intersección vacía, por lo que la familia de todos los subconjuntos del conjunto {a, b, c, d} es una familia Helly de orden 4.
- Sea yo un conjunto finito de intervalos cerrados de la línea real con una intersección vacía. Sea A el intervalo cuyo extremo izquierdo a es lo más grande posible, y sea B el intervalo cuyo extremo derecho b es lo más pequeño posible. Entonces, si a fuera menor o igual que b , todos los números en el rango [ a , b ] pertenecerían a todos los intervalos de I, violando el supuesto de que la intersección de I está vacía, por lo que debe ser el caso que a > b . Por tanto, la subfamilia de dos intervalos {A, B} tiene una intersección vacía y la familia I no puede ser mínima a menos que I = {A, B}. Por lo tanto, todas las familias mínimas de intervalos con intersecciones vacías tienen dos o menos intervalos, lo que muestra que el conjunto de todos los intervalos es una familia Helly de orden 2. [3]
- La familia de progresiones aritméticas infinitas de números enteros también tiene la propiedad 2-Helly. Es decir, siempre que una colección finita de progresiones tiene la propiedad de que no hay dos disjuntas, entonces existe un número entero que pertenece a todas ellas; este es el teorema del resto chino . [2]
Definicion formal
Más formalmente, una familia Helly de orden k es un sistema de conjuntos ( V, E ), con E una colección de subconjuntos de V , tal que, para cada finito G ⊆ E con
podemos encontrar H ⊆ G tal que
y
En algunos casos, la misma definición es válida para cada subcolección G , independientemente de la finitud. Sin embargo, esta es una condición más restrictiva. Por ejemplo, los intervalos abiertos de la línea real satisfacen la propiedad de Helly para subcolecciones finitas, pero no para subcolecciones infinitas: los intervalos (0,1 / i ) (para i = 0, 1, 2, ...) tienen pares no vacíos intersecciones, pero tienen una intersección general vacía.
Dimensión helly
Si una familia de conjuntos es una familia Helly de orden k , se dice que esa familia tiene el número Helly k . La dimensión Helly de un espacio métrico es uno menos que el número Helly de la familia de bolas métricas en ese espacio; El teorema de Helly implica que la dimensión de Helly de un espacio euclidiano es igual a su dimensión como un espacio vectorial real . [4]
La dimensión de Helly de un subconjunto S de un espacio euclidiano, como un poliedro, es uno menos que el número de Helly de la familia de traslados de S. [5] Por ejemplo, la dimensión de Helly de cualquier hipercubo es 1, aunque tal una forma puede pertenecer a un espacio euclidiano de dimensión mucho mayor. [6]
La dimensión Helly también se ha aplicado a otros objetos matemáticos. Por ejemplo, Domokos (2007) define la dimensión Helly de un grupo (una estructura algebraica formada por una operación binaria asociativa e invertible) como uno menos que el número Helly de la familia de clases laterales izquierdas del grupo. [7]
La propiedad Helly
Si una familia de conjuntos no vacíos tiene una intersección vacía, su número de Helly debe ser de al menos dos, por lo que el más pequeño k para el que el k -Helly propiedad es no trivial es decir k = 2. La propiedad 2-Helly también se conoce como la propiedad Helly . Una familia 2-Helly también se conoce como familia Helly . [1] [2]
Un espacio métrico convexo en el que las bolas cerradas tienen la propiedad 2-Helly (es decir, un espacio con dimensión Helly 1, en la variante más fuerte de dimensión Helly para subcolecciones infinitas) se llama inyectivo o hiperconvexo. [8] La existencia del tramo estrecho permite que cualquier espacio métrico se incruste isométricamente en un espacio con dimensión Helly 1. [9]
La propiedad Helly en hipergrafos
Un hipergrafo es equivalente a una familia de conjuntos. En términos de hipergráficos, un hipergráfico H = ( V , E ) tiene la propiedad de Helly si por cada n hiperexpresionesen E , si, luego . [10] : 467 Para cada hipergráfico H, los siguientes son equivalentes: [10] : 470–471
- H tiene la propiedad de Helly, y la gráfica de intersección de H (la gráfica simple en la que los vértices son E y dos elementos de E están vinculados si se cruzan) es una gráfica perfecta .
- Cada hipergrafo parcial de H (es decir, un hipergrafo derivado de H eliminando algunos hipergrafos) tiene la propiedad Konig , es decir, su tamao de coincidencia mximo es igual a su tamao transversal mnimo .
- Todo hipergráfico parcial de H tiene la propiedad de que su grado máximo es igual a su número mínimo de coloración de borde .
Referencias
- ^ a b c d Bollobás, Béla (1986), Combinatoria: sistemas de conjuntos, hipergrafías, familias de vectores y probabilidad combinatoria , Cambridge University Press, p. 82, ISBN 9780521337038.
- ^ a b c Duchet, Pierre (1995), "Hypergraphs", en Graham, RL; Grötschel, M .; Lovász, L. (eds.), Manual de combinatoria, vol. 1, 2 , Amsterdam: Elsevier, págs. 381–432, MR 1373663. Véase en particular la Sección 2.5, "Propiedad de Helly", págs. 393–394 .
- ^ Este es el caso unidimensional del teorema de Helly. Para esencialmente esta prueba, con una redacción colorida que involucra a estudiantes durmiendo, vea Savchev, Svetoslav; Andreescu, Titu (2003), "27 Teorema de Helly para una dimensión", Miniaturas matemáticas , Nueva biblioteca matemática, 43 , Asociación matemática de América, págs. 104-106, ISBN 9780883856451.
- ^ Martini, Horst (1997), Excursiones hacia la geometría combinatoria , Springer, págs. 92–93, ISBN 9783540613411.
- ^ Bezdek, Károly (2010), Temas clásicos en geometría discreta , Springer, p. 27, ISBN 9781441906007.
- ^ Sz.-Nagy, Béla (1954), "Ein Satz über Parallelverschiebungen konvexer Körper" , Acta Universitatis Szegediensis , 15 : 169-177, MR 0065942 , archivado desde el original el 4 de marzo de 2016 , consultado el 10 de septiembre de 2013.
- ^ Domokos, M. (2007), "Invariantes de separación típicos", Grupos de transformación , 12 (1): 49–63, arXiv : math / 0511300 , doi : 10.1007 / s00031-005-1131-4 , MR 2308028.
- ^ Deza, Michel Marie ; Deza, Elena (2012), Enciclopedia de distancias , Springer, p. 19, ISBN 9783642309588
- ^ Isbell, JR (1964), "Seis teoremas sobre espacios métricos inyectivos", Comentario. Matemáticas. Helv. , 39 : 65–76, doi : 10.1007 / BF02566944.
- ^ a b Lovász, László ; Plummer, MD (1986), Teoría de emparejamiento , Annals of Discrete Mathematics, 29 , Holanda Septentrional, ISBN 0-444-87916-1, MR 0859549