Familia Helly

Familia de conjuntos donde cada subfamilia disjunta tiene k o menos conjuntos

En combinatoria , una familia Helly de orden k es una familia de conjuntos en la que cada subfamilia mínima con una intersección vacía tiene k o menos conjuntos en ella. De manera equivalente, cada subfamilia finita tal que cada intersección k -fold no esté vacía 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 frecuentemente 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 , entonces . ${\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 }$

Estos conceptos reciben su nombre de Eduard Helly (1884-1943); el teorema de Helly sobre conjuntos convexos , que dio origen a esta noción, establece que los conjuntos convexos en el espacio euclidiano de dimensión n son una familia Helly de orden n + 1. [ ^1]

Ejemplos

• 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 al eliminar cualquier conjunto de esta subfamilia, esta tiene 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 I un conjunto finito de intervalos cerrados de la recta 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 de que a  >  b . Por lo 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 en ellas, lo que demuestra que el conjunto de todos los intervalos es una familia de 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 tenga la propiedad de que no haya dos de ellas disjuntas, entonces existe un número entero que pertenece a todas ellas; este es el teorema del resto chino . ^[2]

Definición 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 , tales que, para cada G ⊆ E finito con

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

podemos encontrar H ⊆ G tal que

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

y

${\displaystyle \left|H\right|\leq k.}$^[1]

En algunos casos, la misma definición se cumple para cada subconjunto G , independientemente de su 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 subconjuntos finitos, pero no para subconjuntos infinitos: los intervalos (0,1/ i ) (para i = 0, 1, 2, ...) tienen intersecciones no vacías por pares, pero tienen una intersección global vacía.

Dimensión infernal

Si una familia de conjuntos es una familia de Helly de orden k , se dice que esa familia tiene un número de Helly k . La dimensión de Helly de un espacio métrico es uno menos que el número de 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 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 traslaciones de S. ^[5] Por ejemplo, la dimensión de Helly de cualquier hipercubo es 1, aunque dicha forma pueda 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 invertible y asociativa) 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 al menos dos, por lo que el k más pequeño para el cual la propiedad k -Helly no es trivial es k  = 2. La propiedad 2-Helly también se conoce como 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 lapso estrecho permite que cualquier espacio métrico se incruste isométricamente en un espacio con dimensión Helly 1. ^[9]

La propiedad de Helly en los hipergrafos

Un hipergrafo es equivalente a una familia de conjuntos. En términos de hipergrafos, un hipergrafo H = ( V , E ) tiene la propiedad de Helly si para cada n hiperaristas en E , si , entonces . ^{[10] : 467} Para cada hipergrafo H, los siguientes son equivalentes: ^{[10] : 470–471} ${\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 tiene la propiedad de Helly, y el gráfico de intersección de H (el gráfico simple en el que los vértices son E y dos elementos de E están vinculados si se intersecan) es un gráfico perfecto .
• Cada hipergrafo parcial de H (es decir, un hipergrafo derivado de H al eliminar algunas hiperaristas) tiene la propiedad Konig , es decir, su tamaño máximo coincidente es igual a su tamaño transversal mínimo .
• Cada hipergrafo parcial de H tiene la propiedad de que su grado máximo es igual a su número mínimo de coloración de aristas .

Referencias

1. Bollobás, Béla (1986), Combinatoria: sistemas de conjuntos, hipergrafos, familias de vectores y probabilidad combinatoria, Cambridge University Press, pág. 82, ISBN 9780521337038.
2. Duchet, Pierre (1995), "Hypergraphs", en Graham, RL; Grötschel, M .; Lovász, L. (eds.), Manual de combinatoria, vol. 1, 2 , Ámsterdam: Elsevier, págs. 381–432, SEÑOR  1373663. Véase en particular la Sección 2.5, "Helly Property", págs. 393-394.
3. Este es el caso unidimensional del teorema de Helly. Para una demostración básica, con una redacción pintoresca que involucra a estudiantes dormidos, véase Savchev, Svetoslav; Andreescu, Titu (2003), "27 Helly's Theorem for One Dimension", Mathematical Miniatures, New Mathematical Library, vol. 43, Mathematical Association of America, pp. 104–106, ISBN 9780883856451.
4. Martini, Horst (1997), Excursiones en la geometría combinatoria, Springer, págs. 92-93, ISBN 9783540613411.
5. Bezdek, Károly (2010), Temas clásicos de geometría discreta, Springer, p. 27, ISBN 9781441906007.
6. 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.
7. Domokos, M. (2007), "Invariantes separadores típicos", Transformation Groups , 12 (1): 49–63, arXiv : math/0511300 , doi :10.1007/s00031-005-1131-4, MR  2308028.
8. Deza, Michel Marie ; Deza, Elena (2012), Enciclopedia de Distancias, Springer, p. 19, ISBN 9783642309588
9. Isbell, JR (1964), "Seis teoremas sobre espacios métricos inyectivos", Comment. Math. Helv. , 39 : 65–76, doi :10.1007/BF02566944.
10. Lovász, László ; Plummer, MD (1986), Teoría de correspondencias , Annals of Discrete Mathematics, vol. 29, Holanda Septentrional, ISBN 0-444-87916-1, Sr.  0859549