HPC. Casos extraños de S6, 720 vértices.

Nota. entrada incompleta que iré completando. 

1.1 Una investigación heroica.

Al hilo de la entrada anterior, he estado mirando, dentro de la base de datos con la que he trabajado, los resultados para todos los Dígrafos de Cayley bigenerados no isomorfos de S6, es decir del grupo simétrico de grado 6, con 720 vértices.

Aquí hablamos ya de palabras mayores: imposible la acción manual, hay que automatizar cualquier operación, e incluso automatizando puede no encontrarse la respuesta.  Es lo que les pasó a los investigadores que elaboraron la base de datos.

Por cierto de nuevo les estoy altamente agradecido a los dos investigadores que realizaron este gran trabajo. Una investigación heroica, en mi opinión. Tenga en cuenta el lector de que cualquier resultado nuevo con estos tamaños de input y la complejidad del problema, ya supone sangre sudor y lágrimas. Y trabajaban prácticamente a ciegas en lo teórico.

Para resolver un problema científico, un problema matemático, un problema ingenieril,  se necesita información. Incluso el matemático o ingeniero más competente necesita información para resolver un problema. Éstos no se pueden resolver en el vacío. Las soluciones a los problemas no brotan por generación espontánea. Y para algunos de los problemas que se estudian, como ha sido el caso del problema de encontrar recorridos hamiltonianos en Dígrafos de Cayley bigenerados antes de la investigación de éstos autores, simplemente no hay información suficiente para avanzar.

Y en el caso del problema sobre el que hablamos no la había precisamente, como lo sabe cualquiera que haya trabajado en ello, por la dificultad que hay había en encontrar las soluciones para cualquier caso. Las únicas alternativas disponibles eran o bien estudiar las propiedades ad-hoc del caso y si había suerte utilizarlas para encontrar algún recorrido hamiltoniano lo cual se ha podido hacer en contadas ocasiones o bien aplicar un algoritmo genérico que puede tardar una eternidad ya para casos no demasiado grandes. Ningún enfoque general eficaz y eficiente.

Nota. Creo que esta dificultad en encontrar soluciones que era patente antes de la publicación de mis resultados, y no lo digo yo, lo dice uno de los padres de las ciencias computacionales / informática al que cito  en la solicitud de patente,  no la ha comprendido bien todavía el examinador, pese a que lo explico en la solicitud y se lo he intentado explicar por teléfono en varias ocasiones. O no lo ha comprendido, o no lo quiere comprender.

Como ejemplo de lo que queremos decir, un extracto de una tesis de 2004: Hamilton Cycle Heuristics in Hard Graphs. SHIELDS, IAN BEAUMONT

Abstract. In this thesis, we use computer methods to investigate Hamilton cycles and paths in several families of graphs where general results are incomplete, including Kneser graphs, cubic Cayley graphs and the middle two levels graph. We describe a novel heuristic which has proven useful in finding Hamilton cycles in these families and compare its performance to that of other algorithms and heuristics. We describe methods for handling very large graphs on personal computers. We also explore issues in reducing the possible number of generating sets for cubic Cayley graphs generated by three involutions. 

Extractos.

Sjerve and Cherkassoff [102] also studied Cayley graphs where the group generating set consisted of three involutions. They completely determine those alternating groups An, symmetric groups Sn and projective groups PSL2(q) and PGL2(q) which can be generated by three involutions, two of which commute. They also show, by embedding the graph in a surface, that, for a finite group having this property, the Cayley graph corresponding to the generators has a Hamilton cycle. The question of whether a Cayley graph generated by three involutions no two of which commute is still open. 

We will now turn our attention to cubic Cayley graphs, that is, those where every vertex has degree three. We are particularly interested in the symmetric group, Sn, and its subgroups. Suppose X is a set of generators for a group G ⊆ Sn. If Cay(G : S) is cubic then either X is a set of three involutions or a set consisting of one involution and one element of G that is not an involution. The latter type can be studied as either a directed graph or an undirected graph but our research focuses on the undirected form.

We initially applied our algorithm to find Hamilton cycles in Cayley graphs generated by three involutions. As noted above, Cayley graphs generated by three involutions where two or more of the involutions commute were already known to be Hamiltonian [102]. Accordingly, we focused our attention on the case where no two of the involutions commuted. 

After our success with other types of vertex transitive graphs we were very surprised when we were not able to find results. Our heuristic, even when allowed to try a large number of times with a different random number seed each time, was unable to find Hamilton paths or cycles in Cay(S7, X7) which has only 5,040 vertices.

We decided to run a simple backtrack algorithm with no pruning or other enhancements as a comparison. This eventually ran for over a year on a 300MHz Intel processor without finding a Hamilton cycle. 

¡¡¡ Un año y no encontraron la solución y eso que son grafos y no dígrafos y tienen más generadores !!!. 

Nota. El problema de recorridos hamiltonianos en grafos es más sencillo que en dígrafos, y más si los primeros tienen más generadores. La prueba es que en la investigación sobre la que hablamos, para dígrafos bigenerados se pararon en S7 pero para grafos cúbicos llegaron hasta S7. Fin de nota.

Nosotros estamos proponiendo una serie de tests que para un tipo de dígrafos  y con menos generadores (bigenerados), y por lo tanto más complicados, que pueden ahorrar similar tiempo computacional, y el examinador considera que son meras ideas abstractas, que se agotan en si mismas, sin ningún impacto práctico.  

Siguiendo con la tesis, luego aplican otro algoritmo diferente, también con poco éxito: 

Although we had some success with smaller graphs generated by three involutions, this code was still problematic when graphs contained a couple of thousand vertices.

Finalmente comentan sobre la investigación sobre la que estamos hablando nosotros. 

At about this time Effler and Ruskey [36] started cataloging results for isomorphism and Hamiltonicity of Cayley graphs. They had confirmed that all but two of the cubic Cayley graphs on the alternating group, A7, with generators from S7 were Hamiltonian. They had spent thousands of hours of computer time on one of these using algorithms that had succeeded on similar graphs without finding a Hamilton cycle and were about to embark on an exhaustive search on a supercomputer.

We were invited to try our algorithm on these graphs. The graph A7 has 2520 vertices and the first set of generators was (0)(1)(2)(3, 4)(5, 6) and (0, 1, 2, 3)(4, 5)(6).

Vandegriend [107] had investigated the performance of several different Hamilton cycle algorithms on a variety of graphs with up to 1,000 vertices. One of the algorithms used was a backtrack algorithm which used extensive pruning techniques to reduce the size of the search tree. We modified this code to use dynamically allocated data structures so that we could handle larger graphs than those studied by Vandegriend without needing compiled maximum graph sizes. We also added code based on our existing code to handle generation of permutation groups using three involutions or an involution and another generator and its inverse (por lo tanto son grafos).

We used this modified code to show that several Cayley graphs generated by three involutions, no two of which commuted, were Hamiltonian. Although we had some success with smaller graphs generated by three involutions, this code was still problematic when graphs contained a couple of thousand vertices. Nevertheless, we were able to answer some previously unsolved questions as we shall see in Section 6.2.3

We made further modifications to the Vandegriend code to handle graphs generated by one involution and one non-involution. Using this version of the Vandegriend algorithm we found a Hamilton cycle within a minute or so of computation time.

Effler and Ruskey had also been unable to find a Hamilton cycle in the Cayley graph of A7 generated by (0)(1)(2)(3, 4)(5, 6) and (0, 3)(1, 4, 2, 5)(6). Again, the modified Vandegriend code found a Hamilton cycle within a minute or so of computation time.64

Nevertheless, the Vandegriend algorithm slowed down significantly on larger problems. For example, we did not find a cycle using this algorithm on the graph with 2520 vertices generated by the involution (03)(14)(25)(6) and the element (0)(1)(2)(3456) and its inverse which is result 7.294 in the table of Effler and Ruskey (Section 6.4).

Ciertamente un minuto es bastante notable para estos tamaños incluso tratándose de grafos y con más generadores que con los que trabajamos nosotros, lo cual por tener más grados de libertad hace mucho más sencilla su búsqueda.

Y seguramente son smooth, (lo comprobaré). De confirmarse ésto, repetimos que nosotros con nuestro test de smoothness, que se ha incluido en una de las reclamaciones de la solicitud de patente, podríamos haber confirmado la propiedad de hamiltonicidad, de manera no constructiva, de estos y tamaños mucho mayores mucho más rápidamente que en un minuto (milisegundos). Sin embargo el examinador considera que se trata de un test abstracto al que un diseñador no le va a sacar partido. Un ahorro de un año o  más no es práctico. Para un examinador, claro

Si queremos ser constructivos, los smooth son casos en los que que una adaptación de nuestro algoritmo a una heurística casi greedy puede funcionar correcta y rápidamente.

Y ya que hablamos de eficiencia, aprovechamos para recordar una vez más que la implementación de nuestro método no está optimizada. La programé yo. Era mi primer programa y búscaba más la sencillez de programación que la eficiencia. Por ejemplo utilizamos matrices para representar a los dígrafos, que para más inri son muy sparse. También nos interesaba encontrar los recorridos sí o sí sin posibilidad de errores, con lo cual la versión implementada del algoritmo es superfiable, una versión en la que por ejemplo en cada pasada se comprueban todos los IASes. Esto en realidad no es necesario, incluso manteniendo la condición de determinismo, es decir sin pasar a heurística, hasta que ya hay muchos IASes marcados. Con éstos breves comentarios cualquier experto ya se dará cuenta del recorrido que hay para optimizar nuestro método. Finalmente como señalan para casos de tamaño un poco mayor éste algoritmo de Vandegriend ya falla (ya no es tan eficiente, tarda un tiempo eterno; típico de los  métodos generales).

De cualquier manera ésta tesis de Shield que ya conocía es también muy interesante, así como la tesis de Vandegriend, que también conocía y creo recordar que aplica un algoritmo mucho más general que el nuestro. Su uso en éste contexto entra dentro de la estrategia de aplicar algoritmos genéricos que hemos citado antes.

Actualización. Ya tengo una copia de la tesis de Vandegriend. Confirmo que trata de algoritmos (o de heurísticas) de carácter general. Estoy preparando una entrada sobre algoritmos (heurísticas) genéricos para el problema de recorridos hamiltonianos. Fin actualización.

Finalmente comento que no conocía sin embargo el trabajo de Sjerve y Cherkassoff. Paso a intentar encontrarlo. Estaba precisamente leyendo esta mañana un artículo de Gross titulado Imbeddings of Metacyclic Cayley Graphs. Relacionado del mismo autor: A determination of the toroidal k-metacyclic groups. Realmente estos resultados tienen un interés relativo pues estudian el empotrado en superficies de grafos de Cayley, y les interesa la superficie mínima en la que se pueden empotrar todos los grafos de Cayley: The genus of a graph is the minimum of the genera of the orientable surfaces on which the graph can be embedded; the genus of a finite group the minimum of the genera of the Cayley graphs of the group. (To find the genus of a finite group, it suffices to consider only irredundant Cayley graphs.) The nonorientable genus of a graph or of a group is defined similarly. Por lo tanto son excesivas para nuestras necesidades.

Fin de nota.

Tras el  trabajo de matemática o ingeniería experimental de estos dos autores, que se tuvieron que detener en casos del tamaño de 720 vértices e incluso  en estos tamaños no resolvieron todos los problemas, ya había información suficiente para, utilizando conjuntamente otros resultados, hacer importantes avances en éste problema (como pone de manifiesto nuestra propia investigación; como no solo no lo dice nadie, sino que ni siquiera un examinador de la USPTO al que se supone experto en éstos temas es capaz de valorarlo, no me queda más remedio que decirlo yo; pido disculpas por ello) hasta el punto de que la investigación sobre el problema de recorridos hamiltonianos en Dígrafos de Caley Bigenerados, aunque todavía quedan casos abiertos (al menos para mi), ya está bien encauzada.

1.2. Misma información, resultados dispares.

Cabe preguntarse por qué estos dos autores no fueron más allá en lo teórico teniendo  información experimental suficiente. Espero que el lector no vea en éstas líneas un ejercicio de vanidad sino un intento de explicación del porqué investigadores diferentes que trabajan aproximadamente con la misma información y que son más o menos iguales en competencias (salvo casos extremos, ninguna mente humana es superior a otra), llegan a resultados dispares, en un caso que conozco de primera mano.

En mi modesta opinión ésto obedece al menos a cuatro motivos (al margen de que seguramente tampoco era ésto el objetivo de su investigación) y si los autores leen ésto (no creo, hablan otras lenguas), que me corrijan.

El primer motivo es que investigaron sólo el problema de los ciclos hamiltonianos. Si uno se fija sólo en éste problema y no incluye en su foco el problema de los caminos hamiltonianos, está ya en un enfoque teórico nebuloso, que no le va a permitir ver determinadas cosas. Por determinadas razones a mi me interesaban los recorridos en general,  y nunca he entendido la obsesión de la comunidad de investigadores por los ciclos.

Segundo, desconocían que en todos los casos no abelianos el IAS es siempre regular (regularidad según la definición de la  patente). El concepto de arc-forcing que lleva a la construcción del IAS ya existía para tanto abelianos como para no abelianos (no es evidente pero se llega a él fácilmente en cuanto que cualquiera intenta aplicar un mínimo de lógica al problema y muchos investigadores lo habían utilizado). Pero en el caso de los abelianos el IAS no permite  una descomposición del dígrafo en IASes que  sea visualmente informativa cuando los dígrafos se dibujan fijando el foco en los IASes y DASes y no en otros parámetros.

Tercero, relacionado con los dos anteriores, no conocían (de nuevo especulo, no  me consta, pero el caso es que creo recordar que no los citan) en primer lugar el resultado de los Vértices finales posibles (si les interesaban sólo los ciclos y no los  caminos, no podían conocerlo; lo descubrió y publicó primero un autor, seguramente luego otros y mucho más  tarde el que escribe éstas líneas; la demostración de la primera publicación es algebraica, del tipo de las que no comprende ni el tato, diferente a la mía, que he convertido en paso del método y he incluido en una reclamación de la segunda solicitud de patente) ni la generalización del  teorema de Rankin a caminos hamiltonianos. Esta generalización, que yo redescubrí bastante posteriormente (aunque de manera independiente) de otro autor, era y es, creo, bastante desconocida. Pero su combinación con la regularidad del IAS y lo que tratamos en el siguiente motivo son muy potentes de cara a descubrimientos.

Y cuarto, como el dibujo de los casos no era suficientemente informativo, se centraron casi exclusivamente (y aquí estoy especulando completamente) en métodos computacionales. La base de datos que elaboraron, repito que impresionante, pero conteniendo sólo ciclos, sin dibujos de casos significativos, no era informativa de cara a descubrimientos teóricos, no podía llevarles muy lejos.

Seguramente nunca tendrá la oportunidad, pero me gustaría cambiar impresiones al respecto con éstos dos investigadores. Yo, tras representar gráficamente de manera manual bastantes Dígrafos de Cayley sin tener en cuenta el tema del IAS regular, el resultado de los vértices finales posibles y el teorema de Rankin para caminos, salí de la completa oscuridad, vi la luz, pasé del caos al cosmos, sólo cuando encontré, no recuerdo muy bien como, primero el resultado de los vértices finales posibles en un caso no abeliano de IAS de orden 2, y luego en secuencia vi que se podía generalizar a cualquier tamaño y finalmente vi (es fácil demostrarlo) que todos los no abelianos tienen necesariamente un IAS regular. A partir de ese momento y solo a partir de ese momento es cuando, empecé a dibujar los dígrafos con el enfoque del IAS, a verlos de ésta manera  y a hacer avances.

Y por ser tan informativos para el investigador, he incluido en las reclamaciones la propiedad de regularidad del IAS y el resultado de los vértices finales posibles. El conocerlas es básico y supone un ahorro brutal pues ambas, me repito aportan al investigador informaciones clave. Pero el examinador entiende que son meras ideas abstractas que se agotan en si mismas sin ninguna practicidad. A lo mejor es necesario perder varias tardes representando gráficamente Dígrafos visualmente sin sentido o buscando recorridos hamiltonianos en vértices que no pertenecen al conjunto de vértices posibles en Dígrafos de 120 vértices para darse cuenta del valor informativo de estos dos resultados.   

También cabe preguntarse por los dos autores (me centro en ellos dos pues muchos otros que han estudiado éste problema se interesaban más por grafos que por dígrafos), que aparentemente sí se interesaron por todo tipo de recorridos hamiltonianos (ciclos y caminos) en Dígrafos de Cayley bigenerados, tenían un enfoque más teórico y tenían los avances necesarios (el resultado sobre vértices finales posibles y la generalización del teorema  de Rankin para caminos; no he visto que enunciasen, al menos explícitamente, el resultado de IAS regular para casos no abelianos y abelianos con unos parámetros muy específicos; y creo que los dos conocían a los dos resultados mencionados) para ir más allá. Uno de ellos aparentemente (y lamentablemente pues fue el  primero que encontró el resultado sobre vértices finales posibles conjuntamente con otros resultados, y seguramente hubiese  obtenido más resultados de haber continuado su carrera en este campo; el artículo enlazado es el único publicado por éste autor en éste campo y se centra en una cota superior para contar recorridos hamiltonianos en Dígrafos de Cayley bigenerados: la que divide el orden del grupo por el orden del IAS)  dejó la investigación. El otro investigador siguió, y ha seguido casi hasta hoy, publicando sobre el problema, siguiendo la linea que hemos comentado antes: estudiar las propiedades ad-hoc de determinados casos y si había suerte utilizarlas para encontrar algún recorrido hamiltoniano o algún resultado de existencia, obteniendo resultados notables (insisto que hay muchos otros investigadores que han trabajado éste problema, de diversas comunidades, mateméticos, ingenieros  etc…pero me centro en éstos dos por lo ya explicado). Realmente a falta de trabajos experimentales (y quizás también por el hecho de que a los matemáticos puros les interesa más los resultados de existencia y no utilizan tanto los resultados experimentales) como los que luego realizaron los dos autores cuyo trabajo hemos reseñado, prácticamente ésta era la única vía de ataque. Desconozco si estos dos autores conocían la investigación experimental sobre la que hablamos y si la utilizaron.

¿ Existe en las ciencias formales como la matemática o las ciencias computacionales la misma complementariedad entre experimento y teoría que existe en las ciencias naturales (muy acusada en física) o son dos corrientes que se dan la espalda ? Lo desconozco. Las opiniones de Zeibelger sobre las matemáticas experimentales son bien conocidas. Una entrevista realizada a éste investigador casualmente por un autor que ha trabajado también en el problema sobre el que hablamos.

Extracto.

Experimental mathematics is a rapidly growing field, both explicitly and implicitly.     Explicitly, there is a very good journal by that name, an Institute in Simon Fraser      University, and at the recent annual meeting at New Orleans there was a special      session dedicated to it. This is a good start, but still at its infancy.      However, implicitly, more and more mathematicians, even pure ones, use the      computer daily to formulate and test conjectures, in a mode that George      Andrews calls "pencil with power-steering". However, more often than not,      the computer's often crucial contribution is not mentioned, or grossly understated. Human beings are such ingrates.

Cerramos ésta introducción repitiendo una vez más lo mismo: sin la investigación experimental de esto dos autores, nosotros no hubiésemos avanzado prácticamente nada.

Nota al margen. un artículo reciente (2012) del que no tenía noticia y acabo de encontrar, sobre recorridos hamiltonianos en un tipo específico de Dígrafos de Cayley, los dihédricos. Lo he hojeado y parece que utilizan una técnica algorítmica basada en el IAS (¿ hay otra posibilidad ?). Título: ON HAMILTON CIRCUITS IN CAYLEY DIGRAPHS OVER GENERALIZED DIHEDRAL GROUPS ADRIAN PASTINE AND DANIEL JAUME ´ Abstract. In this paper we prove that given a generalized dihedral group DH and a generating subset S, if S ∩H 6= ∅ then the Cayley digraph → Cay(DH, S) is Hamiltonian. The proof we provide is via a recursive algorithm that produces a Hamilton circuit in the digraph.

Y una tesis reciente 2009, títulada Shift Gray Codes, en la que hablan del problema en el contexto de la generación combinatoria / códigos de Gray. El capítulo introductorio es interesante, así  como la bibliografía. Hablan de the utility of the reflected Gray code and de Bruijn cycles for n-tuples, as well as the Johnson-Trotter-Steinhaus order for permutations.

Fin de nota.

2. En fin, tras ésta larga introducción nos centramos en el tema principal de la entrada. La base de datos hay en total 227 casos de S6. Por grados:

–grado 6, 84.

–grado 8, 140.

–grado 9, sólo 3 (sólo incluían aquellos casos en los que un generador es una involución; aún así parecen pocos).

De todos estos me interesan:

Esta parte se ha actualizado el 1 de diciembre de 2015.

–aquellos en los que han encontrado ciclos hamiltonianos (importante: ellos sólo buscaban ciclos, no caminos) y por lo tanto entiendo que son fáciles, pero son entangled (y por lo tanto potencialmente difíciles) pero no cycle-entangled. A estos los llamo raros en el sentido de que los entangled son potencialmente difíciles. Hay 12 de éstos de grado 6, y he contado unos 22 de grado 8. Mañana los comprobaré.

Caso 1. G6, 123465 (orden 2), 234516 (orden 5). IAS, 6. Este es interesante por tener un generador de orden 2.

Caso 2. G6, 124563 (4), 236541 (4). IAS 6. No sorprende.

Caso 3. G&, 132564 (6), 214635 (4). IAS 6. No sorprende.

Caso 4. G6, 132564 (6), 234651 (5). IAS 6. No sorprende.

Caso 5. G6, 132564 (6), 412653 (5). IAS 6. No sorprende.

Casos 6, 7, 8, 9 son todos similares a los casos 2, 3, 4 o 5 y por lo tanto no sorprendentes.

Caso 10. G6, 124365 (2), 231546 (6). IAS 6. ¿ Smooth ?.

Caso 11. G6, 124365 (2), 341526 (6). IAS 6. ¿ Smooth ? 

Caso 12. G6, 124365 (2), 342561 (6). IAS 6. ¿ Smooth ? 

Continuará….

–aquellos en los que no han encontrado positivamente ciclos hamiltonianos y no entran dentro del teorema de Rankin. Son, si no he contado mal, cinco  casos. 2 se pueden explicar por ser cycle entangled, otros dos según anoté son cycle-entangled (mañana lo volveré a comprobar) y en uno no comprobé ésta propiedad (lo comprobaré mañana). Los interesantes son aquellos que no sean ni rankin ni cycle entangled, si finalmente se confirma que hay alguno (podrían ser 3). Habría que analizar sus propiedades.

Continuará….

–aquellos en los que  no han podido decidir si existen o no existen ciclos hamiltonianos (ellos los califican como unknown). Si no recuerdo mal, la mayoría de éstos caen dentro de la categoría de cycle-entangled y gracias a nuestro resultado se puede determinar si los tienen o no los tienen. Me interesa sobre todo si existiese algún unknown  que no sea cycle entangled. Y confirmo que existe alguno.

Hay 29 unknowns. De estos 18 son cycle-entangled. El resto son todos entangled.

Continuará….

Terms and conditions: 1. Any commenter of this blog agrees to transfer the copy right of his comments to the blogger. 2. RSS readers and / or aggregators that captures the content of this blog (posts or comments) are forbidden. These actions will be subject to the DMCA notice-and-takedown rules and will be legally pursued by the proprietor of the blog.

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s


A %d blogueros les gusta esto: