Llevo varios meses trabajando en este problema, pero no he avanzado mucho. Se trata del conjunto de todos los particiones de enteros de n.
Sean los vértices del grafo G=G(n) todas las particiones enteras p(n) de n. Hay una arista entre dos particiones si y sólo si una puede transformarse en otra con sólo mover un punto entre filas en sus representaciones del diagrama de Ferrers.
Así, por ejemplo, las particiones (3,2,1) y (3,3) de 6 están enlazadas porque podemos mover el punto de la última fila a la segunda fila.
OOO OOO
OO -------- OOO
O
Mi pregunta: ¿para qué valores de n tiene G(n) un camino hamiltoniano de (n) a (1,1,...,1)?
Es decir, ¿es posible recorrer, sin repetición, todas las particiones de n simplemente desplazando los puntos en los diagramas de Ferrers?
¿Existe una forma determinada de construir estos caminos?
Sólo he podido construir trayectorias para n = 1 a 6.
n=1 (trivial)
n=2: (2) => (1,1)
n=3:
(3) => (2,1) => (1,1,1)
n=4:
(4) => (3,1) => (2,2) => (2,1,1) => (1,1,1,1)
n=5: (5) => (4,1) => (3,2) => (2,2,1) => (3,1,1) => (2,1,1,1) => (1,1,1,1,1)
n=6: (6) => (5,1) => (4,1,1) => (4,2) => (3,3) => (3,2,1) => (2,2,2) => (2,2,1,1) => (3,1,1,1) => (2,1,1,1,1) => (1,1,1,1,1,1)
Ninguno de los teoremas básicos sobre las trayectorias hamiltonianas me ha ayudado en este caso.