Conjetura de Ryser
En teoría de grafos , la conjetura de Ryser es una conjetura que relaciona el tamaño máximo de coincidencia y el tamaño transversal mínimo en hipergráficos .
Esta conjetura apareció por primera vez en 1971 en el Ph.D. tesis de JR Henderson, cuyo asesor fue Herbert John Ryser . [1]
Una coincidencia en un hipergráfico es un conjunto de hiperrápidos de modo que cada vértice aparece como máximo en uno de ellos. El tamaño más grande de una coincidencia en un hipergráfico H se indica mediante .
Una transversal (o cobertura de vértice ) en un hipergráfico es un conjunto de vértices de manera que cada hipergrafia contiene al menos uno de ellos. El tamaño más pequeño de una transversal en un hipergráfico H se denota por .
Para cada H , ya que cada cobertura debe contener al menos un punto de cada borde en cualquier coincidencia.
Si H es r -uniforme (cada hiperredge tiene exactamente r vértices), entonces , dado que la unión de las aristas de cualquier coincidencia máxima es un conjunto de como máximo rv vértices que se encuentran con todas las aristas.
