Caminos Hamiltonianos donde los vértices son particiones enteras

Question

Hola,

He estado trabajando en este problema durante varios meses, pero no he hecho muchos progresos. Se trata del conjunto de todos particiones enteras de n.

Dejemos que los vértices del gráfico G=G(n) denoten todas las particiones enteras de p(n) de n. Hay un borde entre dos particiones si y sólo si una puede ser transformada en otra moviendo sólo un punto entre filas en sus representaciones de diagrama de Ferrers.

Así, por ejemplo, las particiones (3,2,1) y (3,3) de 6 están unidas 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 atravesar, sin repetición, todos los tabiques de n simplemente moviendo los puntos de los diagramas de Ferrers?

¿Existe una forma determinada de construir tales caminos?

Sólo he podido construir caminos 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 los caminos Hamiltonianos no me han ayudado aquí.

Answer 1

Lo que quieres se conoce como un código Gray para particiones enteras.

Existe.

Ver C. D. Savage, Secuencias de código gris de las particiones, Revista de Algoritmos 10 (1989) 577-595. Descargo de responsabilidad: En realidad no he leído este periódico. Otras fuentes como este estudio de 1997 de Savage y estos apuntes de clase no digas cuál es la construcción, pero di que es complicada.

Answer 2

Hay dos grandes fuentes generales para los códigos Gray en objetos combinatorios que podrían disfrutar:

1) El libro "Generación Combinatoria" de Frank Ruskey: http://tinyurl.com/yly4pq7

2) "El Arte de la Programación de la Computadora" de Don Knuth, Vol. 4, Fascículo 2-4 (publicado por separado - todos excelentes), ver http://www-cs-faculty.stanford.edu/~uno/taocp.html

Las versiones preliminares de algunos de ellos se pueden descargar del archivo de Internet: http://tinyurl.com/yfo57t4

Answer 3

Parece haber un patrón general indicado por su $n=6$ ejemplo. Aquí hay un camino para $n=7$ :

1.  7
2.  6 + 1
3.  5 + 2
4.  5 + 1 + 1
5.  4 + 1 + 1 + 1
6.  4 + 2 + 1
7.  4 + 3
8.  3 + 3 + 1
9.  3 + 2 + 2
10. 2 + 2 + 2 + 1
11. 3 + 2 + 1 + 1
12. 3 + 1 + 1 + 1 + 1
13. 2 + 2 + 1 + 1 + 1
14. 2 + 1 + 1 + 1 + 1 + 1
15. 1 + 1 + 1 + 1 + 1 + 1 + 1

He escrito esto para que sea obvio que las 15 particiones de 7 están contabilizadas. Fíjese en la décima partición.

Aquí hay uno para $n = 8$ :

1.  8
2.  7 + 1
3.  6 + 2
4.  6 + 1 + 1
5.  5 + 1 + 1 + 1
6.  5 + 2 + 1
7.  5 + 3
8.  4 + 4
9.  4 + 3 + 1
10. 4 + 2 + 2
11. 4 + 2 + 1 + 1
12. 4 + 1 + 1 + 1 + 1
13. 3 + 1 + 1 + 1 + 1 + 1
14. 3 + 2 + 1 + 1 + 1
15. 3 + 3 + 1 + 1
16. 3 + 2 + 2 + 1
17. 3 + 3 + 2
18. 2 + 2 + 2 + 2
19. 2 + 2 + 2 + 1 + 1
20. 2 + 2 + 1 + 1 + 1 + 1
21. 2 + 1 + 1 + 1 + 1 + 1 + 1
22. 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

$n=9$ :

1.  9  
2.  8 + 1   
3.  7 + 2   
4.  7 + 1 + 1    
5.  6 + 1 + 1 + 1    
6.  6 + 2 + 1    
7.  6 + 3   
8.  5 + 4   
9.  5 + 3 + 1    
10. 5 + 2 + 2    
11. 5 + 2 + 1 + 1    
12. 5 + 1 + 1 + 1 + 1    
13. 4 + 1 + 1 + 1 + 1 + 1    
14. 4 + 2 + 1 + 1 + 1    
15. 4 + 2 + 2 + 1    
16. 4 + 3 + 1 + 1    
17. 4 + 4 + 1    
18. 4 + 3 + 2    
19. 3 + 3 + 3    
20. 3 + 3 + 2 + 1    
21. 3 + 2 + 2 + 2    
22. 2 + 2 + 2 + 2 + 1    
23. 3 + 2 + 2 + 1 + 1    
24. 3 + 3 + 1 + 1 + 1    
25. 3 + 2 + 1 + 1 + 1 + 1    
26. 2 + 2 + 2 + 1 + 1 + 1    
27. 3 + 1 + 1 + 1 + 1 + 1 + 1    
28. 2 + 2 + 1 + 1 + 1 + 1 + 1    
29. 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1   
30. 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

Answer 4

Si quieres permitir que cualquier parte baje 1 y que cualquier parte (o 0) suba 1, manteniendo un orden no creciente, entonces el artículo de Carla Savage de 1989 de hecho resuelve tu problema (sin requerir "movimientos dobles" como en la décima partición listada de 7 arriba).

Hay refinamientos de esta operación en la literatura. Si sólo permites que un punto "caiga" en una parte adyacente, es decir, desde $( \ldots , p_i, p_{i+1}, \ldots )$ con $p_i \geq p_{i+1}+2$ a $( \ldots , p_i - 1, p_{i+1}+1, \ldots )$ que se llama la "operación de la pila de arena" o la regla vertical de Brylawski. Hay una regla horizontal de transposición, y las restricciones de estas llamadas $ \theta $ y operaciones de "pila de hielo", respectivamente. Para algunas de estas operaciones, el conjunto de particiones de $n$ no es un gráfico conectado, mucho menos uno con un camino Hamiltoniano. Un artículo de encuesta sobre estas operaciones está disponible en http://www-rp.lip6.fr/~latapy/Publis/tcs04a.pdf