¿Por qué hay 1024 ciclos hamiltonianos en un icosaedro?

Question

Fijar un borde $e$ del gráfico (1-esqueleto) de un icosaedro. Mediante una búsqueda informática, he encontrado que hay 1024 ciclos hamiltonianos que incluyen $e$ . [Pero ver editar más abajo, en relación con lo dirigido y lo no dirigido]. Con los dos extremos de $e$ fijo, hay 10 vértices "libres" en el ciclo. Como $1024=2^{10}$ me hace preguntarme si podría haber un punto de vista combinatorio que hace evidente que hay 1024 ciclos que incluyen una arista fija. Podría ser sólo una coincidencia numérica, pero si alguien ve una idea para un argumento, agradecería escucharla. Gracias.

Por cierto, esta página de MathWorld dice que hay 2560 ciclos hamiltonianos en total (sin la condición de borde fijo). (Gracias a Kristal Cantwell por indicarme esta página).

Editar. Pido disculpas por haber inducido a error. :-/ Cuando miré la salida completa de las rutas con más cuidado, me di cuenta de que inadvertidamente calculé dirigido ciclos, por lo que cada uno se representa dos veces, es decir, ambos $$ \lbrace 2, 7, 6, 11, 8, 9, 4, 10, 12, 5, 3, 1 \rbrace $$ $$ \lbrace 1, 3, 5, 12, 10, 4, 9, 8, 11, 6, 7, 2 \rbrace $$ se incluyen, etc. Así que hay 512 ciclos no dirigidos, 1024 ciclos dirigidos. Los caminos se enumeran aquí: hpaths.html .

Answer 1

He introducido estos ciclos hamiltonianos en Software NAUTY de Brendan McKay . Se clasifican en las siguientes colecciones isomórficas:

• 6 colecciones asimétricas, con 48 ejemplos de cada una
• 3 colecciones con simetría rotacional, con 24 ejemplos de cada una
• 5 colecciones con simetría de reflexión, con 24 ejemplos de cada una
• 2 colecciones con dos simetrías de reflexión, con 12 ejemplos de cada una
• 1 colección con simetría rotacional séxtuple, con 8 ejemplos.

Tiene cierto sentido que un ciclo asimétrico tenga 48 ejemplos: el enlace especificado puede ser cualquiera de los 12 enlaces, en cualquier dirección, y hay una doble simetría en el gráfico una vez que se ha seleccionado un enlace dirigido. Esto da el total correcto (utilizando recuentos no dirigidos):

   6×48 + 3×24 + 5×24 + 2×12 + 1×8 = 512

Por cierto, a continuación encontrará una imagen del último tipo. Este utiliza los mismos números de vértice que en la pregunta original. A partir de la imagen, se puede creer que hay dos clases isomórficas de vértices, exterior e interior -- diferentes, por ejemplo, en que cada vértice exterior está conectado al siguiente vértice exterior en el ciclo. Todos los enlaces son entre un vértice exterior y uno interior, pero hay dos clases isomórficas, y el ciclo alterna entre ellas, ABABABABAB. (Se puede ver que son diferentes comparando el resultado de ABA y BAB -- específicamente, si el final está conectado al inicio).

Tengo imágenes de los otros ciclos simétricos.

De todos modos, la cuestión es que sólo uno de los tipos tiene simetría triple -- como señaló Robin, debe haber al menos uno para que el total sea indivisible por 3. Pero con sólo uno, resultará imposible dividir las colecciones en dos grupos de 256. Esto parece una mala noticia para una explicación en base 2 de 512.