La conjetura de Ryser

Problema sin resolver en matemáticas

Conjetura:${\displaystyle \tau (H)\leq (r-1)\cdot \nu (H)}$

Más problemas sin resolver en matemáticas

En teoría de grafos , la conjetura de Ryser es una conjetura que relaciona el tamaño máximo de emparejamiento y el tamaño mínimo de transversal en hipergrafos .

Esta conjetura apareció por primera vez en 1971 en la tesis doctoral de JR Henderson, cuyo asesor fue Herbert John Ryser . ^{[ 1 ]}

Un emparejamiento en un hipergrafo es un conjunto de hiperaristas tal que cada vértice aparece como máximo en una de ellas. El tamaño máximo de un emparejamiento en un hipergrafo H se denota por${\displaystyle \nu (H)}$.

Una transversal (o cubierta de vértices ) en un hipergrafo es un conjunto de vértices tal que cada hiperarista contiene al menos uno de ellos. El tamaño más pequeño de una transversal en un hipergrafo H se denota por${\displaystyle \tau (H)}$.

Para cada H ,${\displaystyle \nu (H)\leq \tau (H)}$, puesto que cada cubierta debe contener al menos un punto de cada arista en cualquier emparejamiento.

Si H es r -uniforme (cada hiperarista tiene exactamente r vértices), entonces ${\displaystyle \tau (H)\leq r\cdot \nu (H)}$, ya que la unión de las aristas de cualquier emparejamiento máximo es un conjunto de como máximo vértices rv que se encuentran con cada arista.

La conjetura de Ryser es que, si H no solo es r -uniforme sino también r-partito (es decir, sus vértices se pueden particionar en r conjuntos de manera que cada arista contenga exactamente un elemento de cada conjunto), entonces:

${\displaystyle \tau (H)\leq (r-1)\cdot \nu (H)}$

Es decir, el factor multiplicativo en la desigualdad anterior se puede disminuir en 1. ^{[ 2 ]}

Un hipergrafo extremal a la conjetura de Ryser es un hipergrafo en el que la conjetura se cumple con igualdad, es decir,${\displaystyle \tau (H)=(r-1)\cdot \nu (H)}$La existencia de tales hipergrafos muestra que el factor r -1 es el más pequeño posible.

Un ejemplo de hipergrafo extremal es el plano proyectivo truncado : el plano proyectivo de orden r -1 en el que se elimina un vértice y todas las líneas que lo contienen. ^{[ 3 ]} Se sabe que existe siempre que r -1 sea potencia de un número primo.

Existen otras familias de hipergrafos extremales de este tipo. ^{[ 4 ]}

En el caso r =2, el hipergrafo se convierte en un grafo bipartito y la conjetura se convierte en${\displaystyle \tau (H)\leq \nu (H)}$Esto se sabe que es cierto gracias al teorema de Kőnig .

En el caso r = 3, la conjetura ha sido demostrada por Ron Aharoni . ^{[ 5 ]} La demostración utiliza el teorema de Aharoni-Haxell para el emparejamiento en hipergrafos.

En los casos r =4 y r =5, Penny Haxell y Scott demostraron la siguiente versión más débil : ^{[ 6 ]} existe algún ε > 0 tal que

${\displaystyle \tau (H)\leq (r-\varepsilon )\cdot \nu (H)}$.

Además, en los casos r =4 y r =5, la conjetura de Ryser ha sido demostrada por Tuza (1978) en el caso especial${\displaystyle \nu (H)=1}$, es decir:

${\displaystyle \nu (H)=1\implies \tau (H)\leq r-1}$.

Un emparejamiento fraccional en un hipergrafo es una asignación de un peso a cada hiperarista tal que la suma de los pesos cerca de cada vértice sea como máximo uno. El tamaño más grande de un emparejamiento fraccional en un hipergrafo H se denota por${\displaystyle \nu ^{*}(H)}$.

Una transversal fraccionaria en un hipergrafo es una asignación de un peso a cada vértice tal que la suma de los pesos en cada hiperarista sea al menos uno. El tamaño más pequeño de una transversal fraccionaria en un hipergrafo H se denota por${\displaystyle \tau ^{*}(H)}$La dualidad de la programación lineal implica que${\displaystyle \nu ^{*}(H)=\tau ^{*}(H)}$.

Furedi ha demostrado la siguiente versión fraccionaria de la conjetura de Ryser: Si H es r -partito y r -regular (cada vértice aparece en exactamente r hiperaristas), entonces ^{[ 7 ]}

${\displaystyle \tau ^{*}(H)\leq (r-1)\cdot \nu (H)}$.

Lovasz ha demostrado que ^{[ 8 ]}

${\displaystyle \tau (H)\leq {\frac {r}{2}}\cdot \nu ^{*}(H)}$.