HPC MARKET

Al redactar un informe  para mi agente de patentes realizado recientemente he utilizado un argumento y he querido comprobar su validez.

Esto me ha llevado a estudiar un poco los Grafos Vértice Transitivos no Cayley para ver si las técnicas de la  patente eran aplicables a estos.

Se trata de ver si estos grafos, convertidos en digrafos se pueden descomponer IAS regulares (ver patente para la definición de esta herramienta). Para esto en principio es conveniente (no tengo claro de momento que sea necesario)

Pido disculpas con antelación al lector por la mala calidad de los gráficos utilizados (me refiero a los elaborados por el que escribe estas líneas).

1. Grafos vértice transitivos no Cayley y no hamiltonianos (ciclos): las famosas excepciones.

Como es sabido de momento se conocen solo cuatro excepciones no triviales: el famoso Grafo de Petersen,  el menos pero también famoso Grafo de Coxeter. y dos modificaciones de estos. La quinta excepción es trivial.

Las cinco excepciones aparecen  en la imagen siguiente extraída de la correspondiente entrada de Mathworld.

a) Grafo de Petersen.

En la primera de las tres siguientes imágenes,  aparece el  Grafo de Petersen. Se ve fácilmente que se puede «convertir» en un digrafo bigenerado  con un generador de orden 5 y una invoución

Es lo que hacemos en la siguiente  imagen. Ojo, los dos ciclos de 5 combinados se pueden orientar de 4 maneras posibles (entiendo que por simetría en realidad son sólo dos diferentes) y en la imagen siguiente solo aparece una de ellas. Tengo pendiente de comprobar si los resultados obtenidos para esta orientación son los mismos  que para cualquier  otra.

En este caso si se puede comprobar por lo tanto  si este grafo al convertirlo  en digrafo se puede descomponer en IAS regulares. Recordemos las  reglas de construcción del IAS. Se elige de manera arbitraria un vértice identidad y se aplica el inverso de uno de los dos generadores y luego el otro generador y se repite esta operación hasta que se llega  a un vértice por el que ya se haya pasado.  Se repite lo mismo para vertices  por los que no se haya pasado en las construcción del primer IAS hasta que todos los vértices estén en algún IAS. En la siguiente imagen  se han construido dos «IAS» según esta regla, uno en negro y el otro en azul claro. Nótese que en realidad son tres pues el IAS y el DAS de la identidad son idénticos. Ninguno de ellos es regular. Si terminasemos todo el proceso, en esta orientación obtendríamos (si lo he realizado bien)  5 IAS diferentes, ninguno regular y de diferentes tamaños.

Ojo, hay un arco que de acuerdo con la definición del método de construcción descrito no debería de estar marcado en negro.

b) Grafo de Coxeter.

Este es un grafo algo más complejo que el  anterior, que Coxeter descubrió dos veces. La segunda le volvió a parecer que tenía unas propiedades notables y llamó a un colega, Tutte, para ver si ya era conocido. Éste, seguramente medio sorprendido medio divertido, le contestó que sí, que ya era conocido y que se llamaba…¡¡ Grafo de Coxeter !!.

No hay manera de convertir el Grafo de Coxeter, de 28 vértices, en un digrafo bigenerado (o al menos yo no la  he encontrado). La manera más habitual de visualizarlo es como tres ciclos de orden 7 (esto sería  un generador) y luego otros siete vértices que se unen al resto por tres involuciones ¿ diferentes ?. Esto es lo que hacemos en la siguiente imagen.

Aquí hemos llegado a un obstáculo. Una de las  maneras de solucionarlo sería generalizar la regla de construcción de IAS incluyendo  más generadores; otra, tener en cuenta que como no es un grafo de ningún grupo, en realidad no tiene sentido hablar de  involución y podemos abstraernos de  la  restricción de que una involución que parte de un elemento (un vértice) necesariamente sólo  puede llevar a otro elemento y sólo  este otro elemento: es  decir considerar que las tres involuciones son el mismo generador. De esta  manera ya estaríamos  hablando de  un digrafo bigenerado. Nótese que un Digrafo de Cayley n-generado no conmutativo sí se puede descomponer  siempre en IAS o DAS regulares. Una tercera alternativa es encontrar otra manera de  verlo (no la obvia que ya hemos descrito) que sí sea bigenerada directamente sin más artificios (pienso por ejemplo en un generador de orden 14 unidos por otro generador de orden dos).

El Grafo de Coxeter tiene ciclos de 14 como se ve en la siguiente imagen. Sin embargo, este en concreto no nos da la solución a lo que bucamos pues no se puede formar otro ciclo completamente disjunto del anterior, como también se ve fácilmente en la imagen (-:.

Otra alternativa es utilizar ciclos de diferentes tamaños (los que no son involuciones; más adelante se indica como realizar esto con el grafo dodecahedro). Pero el ciclo mínimo (técnicamente cintura o girth en inglés) de este grafo es 7 y por lo tanto las alternativas de descomposición son pocas: (14,14), (7,14,7), (7,13, 8), (7,12,9), (7,11,10), (8,8,12), (8,9,11), (8,10,10), (9,9,10), creo  que la lista ya está completa, y esta solución podría no ser viable en este caso como  si lo ha sido  en el grafo dodecahedro. Nótese que podría no haber ciclos de algunos de los tamaños señalados. En este paper aparece una representación del grafo de Coxeter muy adecuada para estudiar su estructura de ciclos: los hay de 7, 8, 9,…14. En la  imagen siguiente un primer intento, mostrado muy confuso de una descomposición en (7, 14, 7).

Diría que encontrar descomposiciones de este tipo es un problema de interés por si  mismo que no se si se ha identificado por otros investigadores (imagino que si; aquí hablan de un problema más general, encontrar un 2-factor, que por lo visto tiene un algoritmo polinómico). Los primeros pasos de un algoritmo de  fuerza bruta para esto son claros: empezar por un primer ciclo (¿ mejor comienzo el girth?)  y de cada uno de sus vértices hacer partir una involución; construir un nuevo ciclo (que entiendo no necesariamente debe de incluir todos los vértices a los que llevan estas involuciones) y de nuevo construir las involuciones.

Conviene recordar que también podrían ser interesantes  descomposiciones no basadas en involuciones.

c) Con los otros dos  casos de Grafos Vértice transitivos no Cayley y no hamiltonianos, es decir  el Grafo de Petersen triangulado  y el Grafo de Coxeter  triangulado, me da la impresión de  que la cosa se  complica más todavía y no los he analizado  son cúbicos y aparentemente pueden ser vistos como bigenerados, con un generador de orden tres y otro de orden 2.

c1) El Grafo de Petersen triangulado.

En la imagen siguiente aparece el Grafo de Petersen triangulado

que efectivamente, como  se ve  en el gráfico siguiente, se puede describir con 2 generadores, uno orden 2 y el otro de orden 3. Señalemos que en este caso el problema de la  orientación de los ciclos de orden 3 se complica todavía más.

Si construimos  los IAS obtendríamos el siguiente Grafo con un resultado, si he realizado todo bien, realmente extraño: tendría 5 IAS/ DAS según la definición original del método de construcción. Uno de ellos, el marcado con color naranja es regular. Pero los otros tres no. Dos de ellos,  el IAS y el DAS de la  identidad son simétricos el uno del otro y comparten tres arcos, y el último,  el marcado con color amarillo aunque parece regular, no lo es.

El 5º IAS, regular como el naranja aparece en la imagen siguiente, para no aumentar un gráfico ya confuso como el anterior. Este también es bastante confuso, por cierto…Por ello he numerado los arcos que recorre.

[Nota al margen. A medida que  los voy construyendo veo que quizás la definición del método de construcción no sea del todo adecuada para este tipo de digrafos y haya que hacer una definición más general que sirva para estos y para los Digrafos de Cayley no Abelianos que son los analizados en la patente. Por ejemplo una definición que  tenga en cuenta el hecho de  que en el caso del IAS (respectivamente el DAS), deben de estar incluidos el inverso de los  dos generadores. Según esto en realidad el negro, el rosa y el amarillo serían el mismo IAS o DAS. Realmente esto tiene más sentido para aquello para lo que se diseñó el  método, encontrar recorridos hamiltonianos. No tengo claro este tema.

Según esta segunda definición el Grafo de Petersen sería solo de una pieza, es decir tendría sólo un IAS, tal  y como se ve en la imagen siguiente

].

c2) El Grafo de Coxeter triangulado. 

Se muestra en la primera imagen.

Coxeter con generadores.  Como se ve de nuevo este grafo se puede describir como construido  con dos generadores uno de ciclo 2 y otro de ciclo 3. Omito el comentario sobre orientación ya que empiezo a pensar que este tema es irrelevante.

Y en el que sigue mostramos 2 de los varios (todavía no se el número) IAS que contiene este caso. Uno regular de 50 arcos y el otro no (lo mostramos según la segunda definición,es decir empezando y terminando en la identidad, que es el vertice en el centro marcado con 1).

En la imagen siguiente otro IAS. Sólo el indicado en color rosa, de cuarenta arcos. El (intento de) marcado en azul está incorrecto, pero por simetría podemos deducir de momento, antes de construirlo, que es regular y tiene unos 50 arcos.

Si no he contado mal el Grafo Triangulado de Coxeter tiene 164 arcos y como cada arco pertenece a un sólo IAS, la suma total de los arcos contenidos en los cuatro IAS debería de coincidir con la  suma total de arcos. Sin embargo estos suman 180. O el anterior razonamiento está mal o he contado mal  o he construido mal los IAS  o pasa algo raro. Mañana más.

2. Grafos vértice transitivos no Cayley, hamiltonianos. Algunos ejemplos famosos.  

Primero  me ha surgido la  duda, que no  he podido aclarar, sobre si existen Grafos Vértice Transitivos no Cayley conmutativos o abelianos. Viendo la página correspondiente de Mathworld dónde aparecen algunos de ellos parece que no es el caso (seguramente habrá una  demostración de  ello sencilla, como por ejemplo que todos los abelianos tengan un subgrupo del grupo de automorfismos del grupo que  actue de forma regular sobre los vértices del grafo; comento esto como mono de repetición pues ahora mismo no tengo clara la referencia de esta propiedad). Una familia relacionada con esto son los Grafos metacirculantes.Y una presentación reciente (2013) y muy interesante de Alspach dónde hablan de temas relacionados.

Como se puede ver, muchos de los grafos que estamos considerando en este apartado tiene un grado superior a 3 o 4 y por lo  tanto puede ser complicado que  encajen en el tema que estamos tratando, o al menos esto requeriría un estudio mucho  más profundo. Pero algunos sí tienen estos grados y por lo tanto se pueden estudiar dentro de este esquema.

a) Grafo de Desargues. 

Uno de ellos es el también famoso Grafo de Desargues, de grado 3 y similar en estructura al de Petersen: 2 ciclos de orden 10 unidos por una involución.

Si lo convertimos de Digrafo y construimos los IASes obtenemos lo siguiente.

Para mi sorpresa este grafo si se puede descomponer en IAS regulares, concretamente en 2 (en la  imagen marcados en negro y verde). Y entiendo que los métodos de la patente para estos casos son perfectamente aplicables al caso y estaríamos  hablando de uno cycle entangled, que se puede reducir  a uno de menor tamaño con propiedades de hamiltonicidad (ojo, sólo ciclos) equivalente. No he realizado esto todavía.

b) Grafo Dodecahedro.

Este grafo es famoso ya que es el que utilizó Hamilton para su juego que de alguna manera se considera el inicio de este problema matemático (el estudio) que nació como puzzle.

Este grafo se puede ver como un Petersen generalizado GP(10,2).  Y aparentemente no se puede representar con dos generadores.

Otra imagen de mismo.

En base a esto podemos obtener algo parecido a lo que queremos (serían tres generadores: uno de orden 10, uno de orden 5 y uno de orden 2). Pero en realidad como no estamos hablando de grafos construidos en base a grupos, tampoco debemos de obsesionarnos  con la idea de  generadores y simplemente ver si se puede construir algo parecido a los IAS de los  Grafos de Cayley que sea de utilidad para el problema de recorridos hamiltonianos. El resultado se muestra en la imagen siguiente, que OJO, es un dígrafo no vértice transitivo.

[Nota al margen. Para grafos mayores podría haber varias alternativas de hacer esto quizás no equivalentes. Por otra parte, no está claro si identificarlas es un proceso que se puede automatizar de manera eficiente o necesita ojo clínico humano].

La pregunta  que surge ahora es que pasa si identificamos el generador de 10 con los de 5 y construimos los IAS, lo cual parece perfectamente posible. Interesa saber si serán regulares o no. La contestación a esta  pregunta es lo que aparece en la imagen siguiente:

Según la segunda definición, un IAS no regular de una sola pieza, como el Grafo de Petersen. ¿ Patrón sobre los Grafos de Petersen generalizados  ?. De cualquier manera, la hipótesis de la que partíamos (que todos los Grafos VTNC con ciclos hamiltonianso tienen descomposición en IAS regulares) parece no confirmarse.

La segunda pregunta que nos surge es si aplicando las técnicas de la patente se puede encontrar un ciclo hamiltoniano de manera rápida. Me temo  que aquí si puede ser relevante la orientación. Jugamos con ventaja dado que sabemos que si existen Y sabemos mucho más, sabemos que existe uno solo (hablan de equivalencia topológica; esto es lo que hace interesante el juego, dado que si tuviese muchos, debido al limitado número de vértices sería sencillo encontrarlos). En realidad esta es la pregunta clave, pues si ver los Grafos VTNC de esta manera no contribuye a resolver este problema, no hemos avanzado nada.

[Nota al margen. Realmente los métodos se  basan en la conocida técnica arc-forcing subgroup en principio aplicable sólo a digrafos de Cayley. He realizado una breve búsqueda para ver si se había intentado trasladar esta técnica  a Grafos Vértice Transitivos No Cayley y de momento no  he encontrado nada relevante].

En la imagen siguiente la primera prueba eligiendo uno de los dos vértices finales posibles con esta orientación, marcado como VF. Aparece enseguida una contradicción (sin más elecciones) y por lo  tanto esta opción no lleva a un recorrido hamiltoniano.

En el segundo vértice final posible, también emerge una contradicción  sólo con la  primera elección, como se aprecia en la siguiente imagen (aunque estoy completamente desentrenado desde hace años con respecto a la aplicación del método, lo he repetido varias veces dos de ellas con el mismo resultado y por lo tanto no creo que haya sido un despiste).

La conclusión provisional es que o bien la orientación importa a estos efectos o bien hemos llegado a una vía  muerta.   Por otra parte si para aplicar el método hubiese que probar todas las orientaciones, surgen dudas sobre la eficiencia del método (otro tema a estudiar relacionado ya con la complejidad computacional). En la imagen siguiente la primera prueba relacionada con la segunda orientación, que también lleva muy rápidamente a contradicción.

Con el segundo vértice final posible  en esta  orientación, si aplicamos de manera estricta el método, también llevaría a contradicción (indicada en amarillo), cómo se ve  en la imagen siguiente.

Sin embargo si observamos el Grafo en el momento de llegar a la contradicción y en ese momento nos acordamos que en realidad se trata de un Grafo y no un Digrafo, y que por lo tanto podemos circular en las dos direcciones en cualquier arco, entonces si que podemos  obtener el ciclo hamiltoniano en pocos pasos:

–cambiamos la  orientación del arco que llevaría a contradicción y,

–a partir de este momento seguimos aplicando el método,

como se ve en la  siguiente imagen indicado estos pasos a partir de ese momento en rosa y el ciclo hamiltoniano se indica en verde.

Esto por supuesto es hacer unas trampas descomunales y si estuviésemos autorizados a hacer esto, seguramente también hubiese funcionado con la anterior orientación (si se puede cambiar en cualquier momento, no es importante). Sin embargo esto nos indica que a lo mejor es posible incorporar algunos pasos adicionales al algoritmo, es decir convertir el parche oportunista en método, en algoritmo.

3. La famosa conjetura.

Muchas de las publicaciones sobre este tema de las propiedades hamiltonianas de Grafos Vértice transitivos están motivadas por aplicaciones de la vida real muy concretas: las redes de interconexión. Pero muchas otras han estado motivadas por conjeturas puramente matemáticas, concretamente la Conjetura de Lovasz (más relevante esta versión: Every finite connected vertex-transitive graph contains a Hamiltonian cycle except the five known counterexamples) y otras similares que se restringen a los Grafos de Cayley.

Lo indicado en los dos anteriores puntos no es más que el embrión de una investigación. Pero  igual al lector, viendo la  diferencia en cuanto a  la posibilidad de descomposición en IAS entre el Grafo de Petersen y el de Desargues  se le habrá encendido la misma lucecita que a mi…que no se si iluminará  o no este problema.

Sí parece que en todos los casos mostrados, con una excepción de  momento, utilizando el método de los IAS se puede demostrar rápidamente si tienen o no un recorrido hamiltoniano. Y es posible que también se pueda utilizar este método para intentar construir (o quizás, de manera más difícil, demostrar que no se puede construir) el sexto contra-ejemplo (quinto no trivial) a la conjetura de la que hemos hablado. E incluso una familia  infinita. Personalmente notengo criterio y por lo tanto opinión sobre hacía que lado se  orientará la balanza con respecto a esta conjetura.

Como una flor no hace primavera, la aplicación del método de los IAS para los Grafos Vértice transitivos no de Cayley de manera general es un tema a investigar. Un primer paso es identificar más casos o incluso familias de Grafos Vértice Transitivos no Cayley cúbicos hamiltonianos (todos los conocidos menos las excepciones ya señaladas lo son) y analizar si se pueden, como el de Desargues, descomponer en IAS regulares o no. Creo que los cúbicos son los realmente interesantes si lo que se quiere es encontrar algún otro contra-ejemplo, para esta conjetura. Y realmente la dificultad de analizar el Grafo de Coxeter con estos métodos ya es una señal de que este camino posiblemente sea una vía muerta…

Un segundo paso sería contestar a una pregunta muy general: ¿ para todo Grafo VTNC cúbico se puede encontrar una representación que permita la construcción de «IAS» en base a «dos generadores» ?. Ir más allá será complicado, como nos indica el resultado de  Plesnik o su equivalente para grafos…El caso más complicado que hemos encontrado de momento es el Grafo de Coxeter.

El tercer paso sería ver si se puede convertir el parche descrito en un punto anterior en método eficiente.

4. Apéndice. 

Algunos enlaces relevantes sobre estos grafos cúbicos (aparentemente entre 2010 y 2012 hubo un renacido interés en estos grafos). El más relevante es el Foster Census un catálogo con todos los grafos cúbicos simétricos.  Pero el formato que presentan no es de lo más accesible. Lo mejor es trabajar con esta página de Mathworld, titulada precisamente Cubic Symmetric Graph, que presenta una lista completa con imágenes de muchos de ellos.

a) CUBIC VERTEX-TRANSITIVE GRAPHS ON UP TO 1280 VERTICES. 2012. 

Este es  un paper muy interesante. Aparece una tabla dónde indican que hasta 1280 vértices hay un total de 111360 grafos no isomorfos de este tipo. De ellos la mayoría son Cayley. Sólo 1434 no  lo son.  Estos serían los que nos interesan. Confirman que todos ellos menos las excepciones conocidas son hamiltonianos.

b) Cubic Vertex-Transitive Non-Cayley Graphs of Order 8p. 2012. 

A graph is vertex-transitive if its automorphism group acts transitively on its vertices. A vertex-transitive graph is a Cayley graph if its automorphism group contains a subgroup acting regularly on its vertices. In this paper, the cubic vertex-transitive non-Cayley graphs of order 8p are classified for each prime p. It follows from this classification that there are two sporadic and two infinite families of such graphs, of which the sporadic ones have order 56,  one infinite family exists for every prime p>3 and the other family exists if and only if p≡1mod4. For each family there is a unique graph for a given order.

c) On cubic non-Cayley vertex-transitive graphs (2011-2012). 

d) Cubic vertex-transitive graphs of order 2pq. 2010. 

ABSTRACT A graph is vertex-transitive or symmetric if its automorphism group acts transitively on vertices or ordered adjacent pairs of vertices of the graph, respectively. Let G be a finite group and S a subset of G such that 1∉S and S={s-1 | s∈S}. The Cayleygraph Cay(G, S) on G with respect to S is defined as the graph with vertex set G and edge set {{g, sg} | g∈G, s∈S}. Feng and Kwak [J Combin Theory B 97 (2007), 627–646; J Austral Math Soc 81 (2006), 153–164] classified all cubic symmetric graphs of order 4p or 2p2 and in this article we classify all cubic symmetric graphs of order 2pq, where p and q are distinct odd primes. Furthermore, a classification of all cubic vertex-transitive non-Cayley graphs of order 2pq, which were investigated extensively in the literature, is given. As a result, among others, a classification of cubic vertex-transitive graphs of order 2pq can be deduced. © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 285–302, 2010

e1)  A note on vertex-transitive non-Cayley graphs from Cayley graphs generated by involutions. 2009.

Interesante. Todos los de este tipo de grado (aquí lo llaman valencia) superior a 6 son hamiltonianos.

Algunos artículos anteriores a este periodo de interés renacido (en 1989 1990 hubo una primera oleada  de interés),artículos no propiamente dedicados a los cúbicos pero con información relevante al respecto.

f) The Transitive Graphs with at most  26 vertices. 1990.

Contiene al final una interesante tabla (nº1) dónde relacionan orden con grado (pero están mezclados los Cayley y No Cayley). Se ve que los de  grado tres o cuatro, que son los que más nos  interesan,  son escasos.

Interesante también: It turns out that the great majority of transitive graphs are Cayley graphs. In fact, non-Cayley transitive graphs don’t occur for n < 25 except for n E { 10, 15, 16 , 18, 20 ,24 , 26 }.

En la tabla (nº3) de la página 175 sí que distinguen entre Cayley y No Cayley. Concretamente, dan el dato que nos interesa: hay un Grafo cúbico VTNC de 10 vértices, el de Petersen, hay tres Grafos VTNC cúbicos no isomorfos de 20 vértices (estos son los que tenemos que identificar: uno de ellos es el de Desargues y el otro es el grafo del Dodecahedro) y uno de 26 (idem).

g) Constructing the vertex transitive graphs of order 24.

 This paper describes the construction of all the vertex-transitive graphs on 24 vertices, thus extending the currently available catalogues. This construction differs significantly from previous constructions of the vertex-transitive graphs of order up to 23 in that we are forced to use far more sophisticated group-theoretic techniques. We include an analysis of all the symmetric graphs on 24 vertices. 

Es un artículo muy técnico.

h) A construction of vertex-transitive non-Cayley graphs.

En este artículo de 1993 proponen un método de construcción de Grafos VTNC, no necesariamente cúbicos, basándose en cosets.  A estudiar con más detenimiento.

This entry was posted on octubre 3, 2014 at 11:06 am and is filed under Uncategorized. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.