Problema de Oberwolfach

Problema sin resolver en matemáticas

Para qué 2-regular${\displaystyle n}$-grafos de vértices${\displaystyle G}$¿Puede el gráfico completo?${\displaystyle K_{n}}$descomponerse en copias disjuntas por aristas de${\displaystyle G}$¿

Más problemas sin resolver en matemáticas

En matemáticas , el problema de Oberwolfach es un problema abierto que puede formularse como un problema de asignación de asientos para comensales o, de forma más abstracta, como un problema de teoría de grafos , sobre las coberturas de ciclos de aristas de grafos completos . Recibe su nombre del Instituto de Investigación Matemática Oberwolfach , donde Gerhard Ringel lo planteó en 1967. ^{[ 1 ]} Se sabe que es válido 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 en cada comida. El problema de Oberwolfach plantea cómo elaborar un plano de asientos para un conjunto dado de mesas de manera que todas las mesas estén ocupadas en cada comida y todas las parejas de participantes de la conferencia se sienten juntas exactamente una vez. Una instancia del problema se puede denotar como${\displaystyle OP(x,y,z,\dots)}$dónde${\displaystyle x,y,z,\dots }$son los tamaños de tabla dados. Alternativamente, cuando algunos tamaños de tabla se repiten, pueden denotarse utilizando notación exponencial; por ejemplo,${\displaystyle OP(5^{3})}$describe una instancia con tres tablas de tamaño cinco. ^{[ 1 ]}

Formulado como un problema de teoría de grafos, los pares de personas sentadas una al lado de la otra en una misma comida pueden representarse como una unión disjunta de grafos cíclicos.${\displaystyle 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${\displaystyle G}$es este gráfico 2-regular y tiene${\displaystyle n}$vértices, la pregunta es si el gráfico completo${\displaystyle K_{n}}$del orden${\displaystyle n}$puede representarse como una unión disjunta por aristas de copias de${\displaystyle G}$. ^{[ 1 ]}

Para que exista una solución, el número total de participantes en la conferencia (o, equivalentemente, la capacidad total de las mesas, o el número total de vértices de los grafos cíclicos 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${\displaystyle n}$preguntando, por aquellos${\displaystyle n}$, si todas las aristas del grafo completo, excepto un emparejamiento perfecto, pueden ser cubiertas por copias del grafo 2-regular dado. Al igual que el problema del ménage (un problema matemático diferente que involucra la disposición de asientos de comensales y mesas), esta variante del problema puede formularse suponiendo que${\displaystyle n}$Los comensales están dispuestos en${\displaystyle n/2}$parejas casadas, y que la disposición de los asientos debe colocar a cada comensal junto a todos los demás comensales, excepto a su propio cónyuge, exactamente una vez. ^{[ 2 ]}

Glock, Joos, Kim, Kühn y Osthus ^{[ 3 ]} encuentran una solución para todas las instancias del problema de Oberwolfach, excepto un número finito de ellas. Se sabe que para${\displaystyle OP(3^{2})}$,${\displaystyle OP(3^{4})}$,${\displaystyle OP(4,5)}$, y${\displaystyle OP(3,3,5)}$No es posible ninguna solución ^{[ 4 ]} y se cree ampliamente que todos los demás casos tienen una solución.

La solución para un gran número de vértices implica muchos pasos aleatorios. Los casos para los que se conoce una solución constructiva incluyen:

• Todas las instancias${\displaystyle OP(x^{y})}$excepto${\displaystyle OP(3^{2})}$y${\displaystyle OP(3^{4})}$. ^{[ 5 ] [ 6 ] [ 7 ] [ 8 ] [ 2 ]}
• Todos los casos en los que todos los ciclos tienen una longitud par. ^{[ 5 ] [ 9 ]}
• Todas las instancias (aparte de las excepciones conocidas) con${\displaystyle n\leq 60}$. ^{[ 10 ] [ 4 ]}
• Todos los casos para ciertas opciones de${\displaystyle n}$, pertenecientes a subconjuntos infinitos de los números naturales . ^{[ 11 ] [ 12 ]}
• Todas las instancias${\displaystyle OP(x,y)}$salvo las excepciones conocidas${\displaystyle OP(3,3)}$y${\displaystyle OP(4,5)}$. ^{[ 13 ]}

Glock, Kühn y Osthus ^{[ 14 ]} sugirieron una generalización del problema de Oberwolfach para${\displaystyle k}$-hipergrafos uniformes (para grandes${\displaystyle n}$).

Problema sin resolver en matemáticas

Suponer${\displaystyle n}$divide${\displaystyle {\tbinom {n}{k}}}$y dejar${\displaystyle F}$frijol${\displaystyle n}$-grafo de vértices que es una unión disjunta de vértices de ciclos ajustados de longitud al menos${\displaystyle 2k+1}$. Entonces${\displaystyle K_{n}^{(k)}}$es descomponible en copias de${\displaystyle F}$.

Más problemas sin resolver en matemáticas

Más precisamente, para suficientemente grandes${\displaystyle n}$Satisfaciendo condiciones triviales de divisibilidad necesarias, conjeturaron que, dada una colección de ciclos ajustados disjuntos en vértices${\displaystyle F}$cubierta${\displaystyle n}$vértices en total, el completo${\displaystyle k}$Hipergrafo uniforme${\displaystyle K_{n}^{(k)}}$puede descomponerse en copias de${\displaystyle F}$. Este problema es equivalente a pedir un plano de asientos como en la formulación original, pero donde cada conjunto de${\displaystyle k}$Las personas se sientan consecutivamente exactamente una vez durante las cenas. Incluso el caso en el que${\displaystyle F}$Los conciertos en un solo ciclo aún están abiertos .

El problema de las colegialas de Kirkman , que consiste en agrupar a quince colegialas en filas de tres de siete maneras diferentes de modo que cada par de chicas aparezca una vez en cada trío, es un caso especial del problema de Oberwolfach.${\displaystyle OP(3^{5})}$El problema de la descomposición hamiltoniana de un grafo completo${\displaystyle K_{n}}$es otro caso especial,${\displaystyle OP(n)}$. ^{[ 9 ]}

La conjetura de Alspach , sobre la descomposición de un grafo completo en ciclos de tamaños dados, está relacionada con el problema de Oberwolfach, pero ninguno es un caso especial del otro. Si${\displaystyle G}$es un grafo 2-regular con${\displaystyle n}$vértices, formados a partir de una unión disjunta de ciclos de ciertas longitudes, entonces una solución al problema de Oberwolfach para${\displaystyle G}$También proporcionaría una descomposición del gráfico completo en${\displaystyle (n-1)/2}$copias de cada uno de los ciclos de${\displaystyle G}$. Sin embargo, no todas las descomposiciones de${\displaystyle K_{n}}$En esto, muchos ciclos de cada tamaño pueden agruparse en ciclos disjuntos que forman copias de${\displaystyle G}$y por otro lado no todos los casos de la conjetura de Alspach involucran conjuntos de ciclos que tienen${\displaystyle (n-1)/2}$copias de cada ciclo.