En teoría de grafos , un hipergrafo de intervalo d es un tipo de hipergrafo construido utilizando intervalos de rectas reales . El parámetro d es un entero positivo . Los vértices de un hipergrafo de intervalo d son los puntos de d rectas disjuntas (por lo tanto, hay una cantidad incontable de vértices). Los bordes del grafo son d - tuplas de intervalos, un intervalo en cada recta real. [1]
El caso más simple es d = 1. El conjunto de vértices de un hipergrafo de 1 intervalo es el conjunto de números reales; cada arista en dicho hipergrafo es un intervalo de la línea real. Por ejemplo, el conjunto { [−2, −1], [0, 5], [3, 7] } define un hipergrafo de 1 intervalo. Nótese la diferencia con un grafo de intervalo : en un grafo de intervalo, los vértices son los intervalos (un conjunto finito ); en un hipergrafo de 1 intervalo, los vértices son todos los puntos en la línea real (un conjunto incontable ).
Como otro ejemplo, en un hipergrafo de 2 intervalos, el conjunto de vértices es la unión disjunta de dos líneas reales, y cada arista es una unión de dos intervalos: uno en la línea n.° 1 y otro en la línea n.° 2.
Los dos conceptos siguientes se definen para hipergrafos de intervalo d , al igual que para hipergrafos finitos:
ν ( H ) ≤ τ ( H ) es verdadero para cualquier hipergrafo H .
Tibor Gallai demostró que, en un hipergrafo de 1 intervalo, son iguales: τ ( H ) = ν ( H ) . Esto es análogo al teorema de König para grafos bipartitos .
Gabor Tardos [1] demostró que, en un hipergrafo de 2 intervalos, τ ( H ) ≤ 2 ν ( H ) , y es ajustado (es decir, cada hipergrafo de 2 intervalos con una coincidencia de tamaño m , puede ser cubierto por 2 m puntos).
Kaiser [2] demostró que, en un hipergrafo de intervalo d , τ ( H ) ≤ d ( d – 1) ν ( H ) , y además, cada hipergrafo de intervalo d con una correspondencia de tamaño m , puede ser cubierto por al menos d ( d − 1) m puntos, ( d − 1) m puntos en cada línea.
Frick y Zerbib [3] demostraron una versión colorida (" arco iris ") de este teorema.