Problema de Oberwolfach

Problemas no resueltos de la matemática: ¿Para qué grafos $G$ 2-regulares de $n$ vértices se puede descomponer el grafo completo $K_{n}$ en copias disjuntas de aristas de $G$?

El problema de Oberwolfach es una cuestión matemática no resuelta que puede formularse en términos de establecer una determinada asignación de asientos para un conjunto de comensales, o más abstractamente, como un problema en teoría de grafos sobre los recubrimientos de ciclos de arista de grafos completos. Lleva el nombre del Instituto de Investigación Matemática de Oberwolfach, donde el problema fue planteado en 1967 por Gerhard Ringel.​ Se sabe que el enunciado es cierto para todos los grafos completos suficientemente grandes.

Formulación

Descomposición del grafo completo $K_{7}$ en tres copias de $C_{3}+C_{4}$, resolviendo el problema de Oberwolfach para el valor $(3,4)$

En las conferencias celebradas en Oberwolfach, es costumbre que los participantes cenen juntos en una sala con mesas circulares, no todas del mismo tamaño, y con asientos asignados que reorganizan a los participantes de una comida a otra. El problema de Oberwolfach pregunta cómo hacer un plano con la distribución de los asientos para un conjunto dado de mesas de modo que todas las mesas estén llenas en cada comida y todos los pares de participantes de la conferencia se sienten uno al lado del otro exactamente una vez. Un planteamiento del problema se puede formular como $OP(x,y,z,\dots )$, donde $x,y,z,\dots$ son los tamaños de mesas dados. Alternativamente, cuando se repiten algunos tamaños de las mesas, se pueden denotar usando notación exponencial; por ejemplo, $OP(5^{3})$ describe una situación en la que se dispone de tres mesas con cinco asientos.​

Formulado como un problema de teoría de grafos, las parejas de personas sentadas una al lado de la otra en una sola comida pueden representarse como unión disjunta de grafos ciclo $C_{x}+C_{y}+C_{z}+\cdots$ de las longitudes especificadas, con un ciclo para cada una de las mesas de comedor. Esta unión de ciclos es un grafo 2-regular, y todo grafo 2-regular tiene esta forma. Si $G$ es este grafo 2-regular y tiene $n$ vértices, la pregunta es si el grafo completo $K_{n}$ de orden $n$ se puede representar como una unión disjunta de aristas de copias de $G$.​

Para que exista una solución, el número total de participantes de la conferencia (o, de manera equivalente, la capacidad total de las mesas o el número total de vértices de los grafos de ciclo dados) debe ser un número impar. Porque, en cada comida, cada participante se sienta junto a dos vecinos, por lo que el número total de vecinos de cada participante debe ser par, y esto solo es posible cuando el número total de participantes es impar. Sin embargo, el problema también se ha extendido a valores pares de $n$ preguntando, para esos $n$, si todos las aristas del grafo completo, excepto emparejamientos perfectos, pueden cubrirse con copias del grafo 2-regular dado. Al igual que el problema del menaje (un problema matemático diferente que involucra la disposición de los asientos de los comensales y las mesas), esta variante del problema se puede formular suponiendo que los $n$ comensales están organizados en $n/2$ parejas casadas, y que la disposición de los asientos debe colocar a cada comensal junto a cada otro comensal excepto su propio cónyuge exactamente una vez.​

Resultados conocidos

Los únicos casos del problema de Oberwolfach que se sabe que no tienen solución son $OP(3^{2})$, $OP(3^{4})$, $OP(4,5)$ y $OP(3,3,5)$.​ Se cree ampliamente que todas los demás supuestos tienen una solución.

Esta conjetura está respaldada por soluciones asintóticas y no constructivas recientes para grandes grafos completos de orden mayor que un límite inferior que, sin embargo, no está cuantificado.​​

Los casos para los que se conoce una solución constructiva incluyen:

• Todas las instancias $OP(x^{y})$ excepto $OP(3^{2})$ y $OP(3^{4})$.​​​​​
• Todos los casos en los que todos los ciclos tienen la misma duración.​​
• Todas las instancias (excepto las excepciones conocidas) con $n\leq 60$.​​
• Todas las instancias para ciertas elecciones de $n$, pertenecientes a infinitos subconjuntos de los números naturales.​​
• Todas las instancias $OP(x,y)$ excepto las excepciones conocidas $OP(3,3)$ y $OP(4,5)$.​

Problemas relacionados

El problema de las colegialas de Kirkman, de agrupar a quince colegialas en filas de tres de siete maneras diferentes para que cada par de niñas aparezca una vez en cada triplete, es un caso especial del problema de Oberwolfach, $OP(3^{5})$. El problema de descomposición hamiltoniana de un grafo completo $K_{n}$ es otro caso especial, $OP(n)$.​

La conjetura de Alspach, sobre la descomposición de un grafo completo en ciclos de tamaños dados, está relacionado con el problema de Oberwolfach, pero ninguno es un caso especial del otro.

Si $G$ es un grafo 2-regular, con $n$ vértices, formado a partir de una unión disjunta de ciclos de ciertas longitudes, entonces una solución al problema de Oberwolfach para $G$ también proporcionaría una descomposición del grafo completo en $(n-1)/2$ copias de cada uno de los ciclos de $G$. Sin embargo, no todas las descomposiciones de $K_{n}$ en tantos ciclos de cada tamaño se pueden agrupar en ciclos separados que formen copias de $G$ y, por otro lado, no todas las instancias de la conjetura de Alspach involucran conjuntos de ciclos que contienen $(n-1)/2$ copias de cada ciclo.

Referencias

• Datos: Q48999401