Problema de Oberwolfach

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

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.[1]​ Se sabe que el enunciado es cierto para todos los grafos completos suficientemente grandes.

Formulación

editar
 
Descomposición del grafo completo   en tres copias de  , resolviendo el problema de Oberwolfach para el valor  

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  , donde   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.[1]

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   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   es este grafo 2-regular y tiene   vértices, la pregunta es si el grafo completo   de orden   se puede representar como una unión disjunta de aristas de copias de  .[1]

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   preguntando, para esos  , 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   comensales están organizados en   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]

Resultados conocidos

editar

Los únicos casos del problema de Oberwolfach que se sabe que no tienen solución son  ,  ,   y  .[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:

  • Todas las instancias   excepto   y  .[6][7][8][9][2]
  • Todos los casos en los que todos los ciclos tienen la misma duración.[6][10]
  • Todas las instancias (excepto las excepciones conocidas) con  .[11][3]
  • Todas las instancias para ciertas elecciones de  , pertenecientes a infinitos subconjuntos de los números naturales.[12][13]
  • Todas las instancias   excepto las excepciones conocidas   y  .[14]

Problemas relacionados

editar

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,  . El problema de descomposición hamiltoniana de un grafo completo   es otro caso especial,  .[10]

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   es un grafo 2-regular, con   vértices, formado a partir de una unión disjunta de ciclos de ciertas longitudes, entonces una solución al problema de Oberwolfach para   también proporcionaría una descomposición del grafo completo en   copias de cada uno de los ciclos de  . 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   copias de cada ciclo.

Referencias

editar
  1. a b c Lenz, Hanfried; Ringel, Gerhard (1991), «A brief review on Egmont Köhler's mathematical work», Discrete Mathematics 97 (1–3): 3-16, MR 1140782, doi:10.1016/0012-365X(91)90416-Y .
  2. a b Huang, Charlotte; Kotzig, Anton; Rosa, Alexander (1979), «On a variation of the Oberwolfach problem», Discrete Mathematics 27 (3): 261-277, MR 541472, doi:10.1016/0012-365X(79)90162-6 .
  3. a b Salassa, F.; Dragotto, G.; Traetta, T.; Buratti, M.; Della Croce, F. (2019), Merging Combinatorial Design and Optimization: the Oberwolfach Problem, Bibcode:2019arXiv190312112S, arXiv:1903.12112 .
  4. Glock, Stefan; Joos, Felix; Kim, Jaehoon; Kühn, Daniela; Osthus, Deryk (2021), «Resolution of the Oberwolfach problem», Journal of the European Mathematical Society 23 (8): 2511-2547, MR 4269420, arXiv:1806.04644, doi:10.4171/jems/1060 .
  5. Keevash, Peter; Staden, Katherine (2022), «The generalised Oberwolfach problem», Journal of Combinatorial Theory, Series B 152: 281-318, MR 4332743, doi:10.1016/j.jctb.2021.09.007, archivado desde el original el 24 de septiembre de 2020, consultado el 24 de octubre de 2022 .
  6. a b Häggkvist, Roland (1985), «A lemma on cycle decompositions», Cycles in graphs (Burnaby, B.C., 1982), North-Holland Math. Stud. 115, Amsterdam: North-Holland, pp. 227-232, MR 821524, doi:10.1016/S0304-0208(08)73015-9 .
  7. Alspach, Brian; Häggkvist, Roland (1985), «Some observations on the Oberwolfach problem», Journal of Graph Theory 9 (1): 177-187, MR 785659, doi:10.1002/jgt.3190090114 .
  8. Alspach, Brian; Schellenberg, P. J.; Stinson, D. R.; Wagner, David (1989), «The Oberwolfach problem and factors of uniform odd length cycles», Journal of Combinatorial Theory, Series A 52 (1): 20-43, MR 1008157, doi:10.1016/0097-3165(89)90059-9 .
  9. Hoffman, D. G.; Schellenberg, P. J. (1991), «The existence of  -factorizations of  », Discrete Mathematics 97 (1–3): 243-250, MR 1140806, doi:10.1016/0012-365X(91)90440-D .
  10. a b Bryant, Darryn; Danziger, Peter (2011), «On bipartite 2-factorizations of   and the Oberwolfach problem», Journal of Graph Theory 68 (1): 22-37, MR 2833961, doi:10.1002/jgt.20538 .
  11. Deza, A.; Franek, F.; Hua, W.; Meszka, M.; Rosa, A. (2010), «Solutions to the Oberwolfach problem for orders 18 to 40», Journal of Combinatorial Mathematics and Combinatorial Computing 74: 95-102, MR 2675892 .
  12. Bryant, Darryn; Scharaschkin, Victor (2009), «Complete solutions to the Oberwolfach problem for an infinite set of orders», Journal of Combinatorial Theory, Series B 99 (6): 904-918, MR 2558441, doi:10.1016/j.jctb.2009.03.003 .
  13. Alspach, Brian; Bryant, Darryn; Horsley, Daniel; Maenhaut, Barbara; Scharaschkin, Victor (2016), «On factorisations of complete graphs into circulant graphs and the Oberwolfach problem», Ars Mathematica Contemporanea 11 (1): 157-173, MR 3546656, arXiv:1411.6047, doi:10.26493/1855-3974.770.150 .
  14. Traetta, Tommaso (2013), «A complete solution to the two-table Oberwolfach problems», Journal of Combinatorial Theory, Series A 120 (5): 984-997, MR 3033656, doi:10.1016/j.jcta.2013.01.003 .