Problema de Oberwolfach
Lleva el nombre del Instituto de Investigación Matemática de Oberwolfach, donde el problema fue planteado en 1967 por Gerhard Ringel.
[1] Se sabe que el enunciado es cierto para todos los grafos completos suficientemente grandes.
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
{\displaystyle OP(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,
describe una situación en la que se dispone de tres mesas con cinco asientos.
Esta unión de ciclos es un grafo 2-regular, y todo grafo 2-regular tiene esta forma.
vértices, la pregunta es si el grafo completo
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
, 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
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.
[2] Los únicos casos del problema de Oberwolfach que se sabe que no tienen solución son
[3] 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.
[4][5] Los casos para los que se conoce una solución constructiva incluyen: 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,
también proporcionaría una descomposición del grafo completo en
Sin embargo, no todas las descomposiciones de
en tantos ciclos de cada tamaño se pueden agrupar en ciclos separados que formen copias de
y, por otro lado, no todas las instancias de la conjetura de Alspach involucran conjuntos de ciclos que contienen
