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).
In 1983, the second author [D. Marušič, Ars Combinatoria 16B (1983), 297–302] asked for which positive integers n there exists a non-Cayley vertex-transitive graph on n vertices. (The term non-Cayley numbers has later been given to such integers.) Motivated by this problem, Feng [Discrete Math 248 (2002), 265–269] asked to determine the smallest valency ϑ(n) among valencies of non-Cayley vertex-transitive graphs of order n. As cycles are clearly Cayley graphs, ϑ(n)⩾3 for any non-Cayley number n.
In this paper a goal is set to determine those non-Cayley numbers n for which ϑ(n) = 3, and among the latter to determine those for which the generalized Petersen graphs are the only non-Cayley vertex-transitive graphs of order n. It is known that for a prime p every vertex-transitive graph of order p, p2 or p3 is a Cayley graph, and that, with the exception of the Coxeter graph, every cubic non-Cayley vertex-transitive graph of order 2p, 4p or 2p2 is a generalized Petersen graph. In this paper the next natural step is taken by proving that every cubic non-Cayley vertex-transitive graph of order 4p2, p>7 a prime, is a generalized Petersen graph. In addition, cubic non-Cayley vertex-transitive graphs of order 2pk, where p>7 is a prime and k⩽p, are characterized.
© 2011 Wiley Periodicals, Inc. J Graph Theory 69: 77–95, 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.
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.