La conjetura de Tuza

Problema sin resolver en matemáticas

¿Cada grafo no dirigido${\displaystyle G}$¿Existe un conjunto de triángulos que alcancen un tamaño máximo igual al doble del número de triángulos en un empaquetamiento óptimo?

Más problemas sin resolver en matemáticas

La conjetura de Tuza es un problema sin resolver en la teoría de grafos , una rama de las matemáticas, que concierne a los triángulos en grafos no dirigidos .

En cualquier gráfico${\displaystyle G}$Se pueden definir dos cantidades${\displaystyle \nu (G)}$y${\displaystyle \tau (G)}$basado en los triángulos en${\displaystyle G}$. La cantidad${\displaystyle \nu (G)}$es el "número de empaquetamiento de triángulos", el mayor número de triángulos disjuntos por aristas que es posible encontrar en${\displaystyle G}$. ^{[ 1 ]} Se puede calcular en tiempo polinomial como un caso especial del problema de paridad de matroides . ^{[ 2 ]} La cantidad${\displaystyle \tau (G)}$es el tamaño del "conjunto de intersección de triángulos" más pequeño, un conjunto de aristas que toca al menos una arista de cada triángulo. ^{[ 1 ]}

Claramente,${\displaystyle \nu (G)\leq \tau (G)\leq 3\nu (G)}$. Para la primera desigualdad,${\displaystyle \nu (G)\leq \tau (G)}$, cualquier conjunto que toca triángulos debe incluir al menos una arista de cada triángulo del empaquetamiento óptimo, y ninguna de estas aristas puede ser compartida entre dos o más de estos triángulos porque los triángulos son disjuntos. Para la segunda desigualdad,${\displaystyle \tau (G)\leq 3\nu (G)}$, se puede construir un conjunto de triángulos que toquen de tamaño${\displaystyle 3\nu (G)}$eligiendo todos los bordes de los triángulos de un empaquetamiento óptimo. Esto debe tocar todos los triángulos en${\displaystyle G}$, incluso los que no están en el empaque, porque de lo contrario el empaque podría hacerse más grande agregando cualquier triángulo no alcanzado. ^{[ 1 ]}

La conjetura de Tuza afirma que la segunda desigualdad no es ajustada y puede ser reemplazada por${\displaystyle \tau (G)\leq 2\nu (G)}$. Es decir, según esta conjetura no probada, todo grafo no dirigido${\displaystyle G}$tiene un conjunto de intersección de triángulos cuyo tamaño es como máximo el doble del número de triángulos en un empaquetamiento óptimo. ^{[ 1 ]}

Zsolt Tuza formuló la conjetura de Tuza en 1981. ^{[ 1 ] [ 3 ]} Si fuera cierta, sería lo mejor posible: hay infinitos grafos para los cuales${\displaystyle \tau (G)=2\nu (G)}$, incluyendo todos los grafos de bloques cuyos bloques son camarillas de 2, 4 o 5 vértices. ^{[ 1 ]}

Se sabe que la conjetura se cumple para grafos planares , ^{[ 1 ]} y, más generalmente, para grafos dispersos con una degeneración máxima de seis. ^{[ 4 ]} (Los grafos planares tienen una degeneración máxima de cinco). También se sabe que se cumple para grafos con un ancho de árbol máximo de seis, ^{[ 5 ]} para grafos umbral , ^{[ 6 ]} para grafos suficientemente densos y para grafos cordales que no contienen una gran camarilla. ^{[ 1 ]} Para grafos aleatorios en el modelo de Erdős-Rényi-Gilbert , es cierto con alta probabilidad . ^{[ 7 ]}

Aunque la conjetura de Tuza sigue sin probarse, el límite${\displaystyle \tau (G)\leq 3\nu (G)}$se puede mejorar, para todos los gráficos, a ${\displaystyle \tau (G)\leq (3-{\tfrac {3}{23}})\nu (G)\approx 2.8695\nu (G)}$. ^{[ 8 ]}

• Teorema de Mantel
• Lema de eliminación de triángulos

• van der Pol, Jorn (6 de marzo de 2023), "Triángulos, arcos y óvalos" , The Matroid Union