(Dí)grafos de Cayley. Problema de isomorfismo (6).

Actualización 27 de marzo. 

Veo este artículo en el que hablan de una variación del problema de isomorfismo: el problema de graph similarity.

Fin actualización. 

I. Comentario inicial 21 de marzo 2019. 

Cuando es una entrada de exploración de un tema, se sabe como empieza pero no como termina. Esto es lo que nos ha sucedido en esta, en la que empezábamos con una idea muy clara pero cuyo desarrollo requiere bastante más investigación. Como este tema no es prioritario, lo dejamos a medias.

Como en las otras de la serie el contenido finalmente es irregular y seguramente confuso para cualquier lector (incluso para el que lo ha escrito ). De cualquier manera, gracias a estas entradas de la serie, ya comprendo lo suficiente los problemas de isomorfismo de grafos (input grafo entero) e isomorfismo de grupos (dado por tablas de Cayley) como para dejar de estudiarlos.

Seguramente hagamos unas últimas entradas sobre isomorfismo de grupos de permutaciones (todavía tengo algunas dudas sobre este tema) e isomorfismo de grafos de Cayley. Este último tema es el que ha motivado esta serie de entradas y tenemos algunas lecturas pendientes sobre el.

En cuanto a terminología, como en todo momento hablamos de grafos, dónde hemos escrito arco se debe de leer arista. Transposición es un cambio de dos elementos en una permutación. Involución es un elemento de orden 2 en un grupo, un elemento que es inverso de si mismo. Como las transformaciones de las que hablamos pueden ser transposiciones (1-transformaciones) pero también involuciones de carácter más general (las 2-trasnformaciones son permtuaciones que constan de 2 transposiciones y el resto puntos fijos, las 3-transformaciones son permutaciones que constan de 3 transposiciones y el resto puntos fijos, etc…), utilizamos siempre la palabra involución, pero quedará claro por el contexto cuando nos referimos a transposición. No se si existe un nombre para designar permutaciones de un conjunto de cardinalidad par en la que ningún elemento queda fijo (es decir permutaciones de un conjunto de n elementos cuya expresión por ciclos consta de n/2 transposiciones).

Fin de comentario inicial. 

II. Indice de la entrada.

1.Justificación de la entrada.

2.Método de fuerza bruta para el problema de isomorfismo. 

3.Punto de vista del individuo que tiene que generar los inputs para el problema de isomorfismo: las dos formas de modificar un grafo (matriz binaria), automorfismos e invariantes (1).

3.1 Ahora vamos a analizar con más detalle la primera manera de modificar o desordenar a la matriz inicial M0, para obtener una isomorfa.

3.2 Ahora vemos con detalle la segunda manera de modificar o desordenar M0, obteniendo como resultado una matriz no isomorfa.

3.2. Actualización 19 de marzo de 2019. Aterrizando la idea. 

3.2. Actualización 21 de marzo. Análisis de otro caso y comentarios finales.

3.2 Actualización 22 de marzo. Análisis (ligero) de un caso basado en un grafo de Cayley. 

3.2. Actualización 23 de marzo. 

4.Problemas de isomorfismo. 

4.1. ¿ Que se da como input en el problema de isomorfismo ?.

4.2 ¿ A que se reduce el problema de isomorfismo ?

4.3 El problema de isomorfismo.  Sus dos vías de solución.  

5. Grupo de automorfismos o ¿grupo? de invariantes ¡¡ e ahí el dilema !!. 

5.1 Preliminares.

Segunda redacción (17 de marzo de 2017).

5.2. Fuerza bruta en el análisis del grupo de automorfismos. (incompleto)

5.3. Fuerza bruta en el análisis del ¿grupo? de invariantes (incompleto, ¿incorrecto?). 

6. Conclusiones.

———————————————————————————————————————–

III. Contenido. 

1.Justificación de la entrada.

La sexta de la serie, offshoot de la anterior. Como siempre, unas reflexiones, en principio colaterales que se alargaban demasiado en la anterior entrada, me obligan a iniciar una nueva entrada, puliendo estas reflexiones.

En las anteriores entradas hemos comentado sobre el problema de isomorfismo de muchas estructuras, en general algebraicas. Nuestro interés principal era determinar su complejidad computacional en diferentes representaciones y la idea era compilar enlaces (con extractos) al respecto.

En esta entrada queremos comprender mejor, profundizar (que no intentar resolver) el problema de isomorfismo de grafos, según lo vemos nosotros. Y como se verá en esta ocasión el título viene al pelo. Lo vamos a intentar comprender mejor utilizando el vocabulario que mejor conocemos, el de los dígrafos de Cayley.

Tras todas estas reflexiones y redacciones de las últimas entradas, pensamos que por fin estamos empezando a vislumbrar estos problemas de isomorfismo de una manera más adecuada. Lo cual implica, aunque sea duro admitirlo (ya que llevamos ya varios días y decenas de páginas escritas sobre ello), que en todas las anteriores entradas, estábamos un poco  despistados…No digo que todo lo que aparezca en ellas sea incorrecto. Más bien superficial y en ocasiones no demasiado relevante (ahora no veo que para este problema el pasar de un tamaño normal a uno sucinto sea demasiado importante o informativo). Y no digo que ahora tengamos la visión correcta hasta el último detalle (en este «nuevo» esquema hay detalles muy importantes que todavía se nos escapan) pero si más adecuada que las anteriores.

En esta entrada vamos a ver este problema cambiando la óptica y presentación habitual en varios aspectos:

–nos vamos a centrar en los métodos de fuerza bruta,

–nos vamos a centrar en el input de los grafos como matriz de adyacencia binaria (realmente no creo que esto no sea lo habitual),

–normalmente este problema se describe desde el punto de vista del individuo que tiene que resolverlo. Nos vamos a centrar en los condicionamientos del individuo  que tiene que generar los inputs para entregárselos al individuo que tiene que resolver el problema. Ya adoptamos este mismo punto de vista en otra entrada de esta serie para otro problema. Para mi el verlo desde esta óptica ha sido clave.

—no hay enlaces, extractos ni notas. Ya tengo toda la literatura que necesito. Ahora toca digerirla, ir atando cabos. Ok, hay alguna excepción, sobre todo en cuanto a notas…

2.Método de fuerza bruta para el problema de isomorfismo. 

Aunque realmente tampoco le hemos dedicado tiempo a los problemas de isomorfismo, hasta esta ocasión, he de admitir que nunca lo he comprendido bien del todo. Creo que uno de los motivos es, principalmente, pq nunca he tenido claro cual podría ser un algoritmo de fuerza bruta para resolverlo. 

Esto es así para cualquiera de las vías de ataque que normalmente se siguen para resolverlo, la de canonización-invariantes y, digamos, la de teoría de grupos. Con respecto a la de invariantes, por ejemplo, no tengo nada claro cual podría ser un invariante que sea completo aunque ineficaz para estos problema. Pero en esta entrada nos vamos a centrar en el otro enfoque. ¿ Cual es el método de fuerza bruta correspondientes a la vía de teoría de grupos ? 

Tal y como lo veo, si te dan dan dos matrices binarias de nxn, el método de fuerza bruta de teoría de grupos consiste en: 

–primer paso: hacer una lista de todas las biyecciones posibles entre vértices de los dos grafos. Duda: ¿ que se corresponde a los vértices en la  representación matricial: los vértices de la cabecera de las columnas, los vértices de las cabeceras de las filas, o los dos ?. Este es uno de los detalles que no tenemos claro, pero no es importante de momento para continuar.  

–segundo paso: coges la primera biyección de la lista. Dejas fija una de las dos matrices, y de acuerdo con las reglas de cada biyección en concreto, permutas las columnas y filas de la otra. Cuando has terminado de permutar, si las dos matrices fuesen las mismas podrías colocar una encima de otra y no aparecería ninguna diferencia; si no son las mismas por esta biyección, aparecerán diferencias entre las dos.

–tercer paso: si la matriz es la misma en el paso anterior hemos terminado, los dos grafos son isomorfos; si no es la misma se coge la siguiente biyección de la lista del primer paso y se repiten las intrucciones del segundo paso, dejando fija la misma matriz. Es decir para todas las biyecciones una de las dos matrices (siempre la misma) queda fija, y se permuta la  otra. 

Si has recorridos todas las biyecciones de la lista y con ninguna has obtenido dos matrices iguales, entonces puedes concluir que las dos no son isomorfas. De lo contrario, con alguna de las biyecciones has obtenido dos matrices idénticas.   

3.Punto de vista del individuo que tiene que generar los inputs para el problema de isomorfismo: las dos formas de modificar un grafo (matriz binaria): automorfismos e invariantes (1).

Asumimos que la descripción del método anterior de fuerza bruta (bajo la vía de ataque de teoría de grupos) es más o menos correcta. Esa es la visión desde el punto de vista del individuo que tiene que resolver el problema.

Ahora vemos el tema desde el punto de vista del que tiene que generar los inputs para el problema. No nos interesa de momento conocer como se generan los casos difíciles en la práctica. Este es un problema muy interesante pero no es nuestro objetivo en esta entrada. Nuestro objetivo es ver un método elemental pero general de generar casos para el problema de isomorfismo, que eviten sólo a los invariantes más triviales. En esto nos interesa sobre todo la generalidad.      

Dada una matriz de nxn binaria inicial M0 (el planteamiento valdría para cualquier tipo de matriz, no solo para las binarias), entiendo que hay dos maneras de modificarla, de desordenarla:

–en la primera manera, aplicas a M0 una serie de transformaciones al grafo (a la matriz binaria), pero sin modificarlo, sin cambiar su clase de isomorfismo. Lo desordenas, pero no lo modificas. Digamos que pasas de una matriz M0 a una matriz isomorfa del tipo Miso1.

–en la segunda manera aplicas una serie de transformaciones al grafo (a la matriz binaria) modificándolo, cambiando su clase de isomorfismo. En este caso, vamos a imponer unas condiciones adicionales: interesa modificarlo, pero obteniendo otro que sea muy similar en todos los parámetros (número de vértices, grado de los vértices etc…) al inicial. Digamos que pasas de una matriz M0 a una matriz del tipo Mnoiso1.

3.1 Ahora vamos a analizar con más detalle la primera manera de modificar o desordenar a la matriz inicial M0.

Esto se puede ver en base a dígrafos de Cayley de la siguiente manera. La matriz M0 es un vértice de un dígrafo de Cayley. Y a partir de este vértice se construye el dígrafo utilizando las siguientes transformaciones:

–si la matriz por ejemplo es de 3×3, una transformación que desordena pero no modifica la clase de isomorfismo podría ser permutar la fila 1 por la fila 3, otro permutar fila 1 por fila 2 y otro permutar fila 2 por fila 3.

Nota. El grafo en forma de vértices y arcos y el grafo en forma matricial son objetos equivalentes. El uno es, digamos, la descripción algebraica del otro. Y el otro es la descripción gráfica en el plano del uno. La manera de pasar de uno a otro es muy directa. También está claro que en la forma matricial una permutación de columnas o filas no cambia la clase de isomorfismo. ¿ Pero cual sería el equivalente de estas transformaciones en la representación gráfica ?. Entiendo que sería un movimiento de algunos de los vértices en el plano que alterasen la forma original. El movimiento de vértices en el plano sin reconectar arcos nunca modifica la clase de isomorfismo. En los casos irregulares es fácil encontrar una manera, digamos «canónica», de empotrar los grafos en el plano usando los diferentes grados para ordenarlos. De manera equivalente se pueden reordenar columnas y filas (permutando) en la matriz para obtener algo similar que simule esto. Si te dan dos grafos irregulares, un primer paso es realizar estas reordenaciones. Cuando el grafo es regular, el grado ya no es el criterio que te permite fijar un orden, digamos canónico, entre los vértices para situarlos en el plano. Pero hay otros. Fin de nota.  

–Otras tres transformaciones para permutaciones de columnas.

–Y si aceptamos que en una misma transformación se puedan permutar filas por columnas entonces habrá unas cuantas mas transformaciones que reflejen esto.

–otras transformaciones pueden ser cambios de un uno por una casillas por un cambio de otro 1 en otra casilla. Realmente esta es una transformación posible pero que no desordena.

–y también hay transformaciones de 0 por 1 que no cambian la clase de isomorfismo del grafo.

No se si con este tipo de transformaciones ya hemos agotado todas las posibilidades. Aunque determinar esto es clave, de nuevo no nos interesa aclarar todos los detalles exactos, y dejamos este tema para más adelante. Llamamos a este conjunto de transformaciones que no modifican la clase de isomorfismo de una matriz binaria nxn, T1.   

Lo que está claro y en este momento es más importante, es que estamos construyendo un dígrafo de Cayley aplicando una serie de transformaciones (las indicadas, o si estas son incorrectas o incompletas, las correctas o completas), que son los generadores, a una matriz inicial M0, y que el resultado de aplicar estas transformaciones son matrices isomorfas a la inicial (del tipo MisoX), que son los vértices del dígrafo de Cayley. Cuando termina la construcción los vértices del dígrafo de Cayley (todas las matrices binarias del tipo MisoX) son todos los elementos de un grupo que podemos llamar el grupo GMisoX. 

Como estamos realizando transformaciones biyectivas en un objeto sin modificarlo, está claro que GmisoX es exactamente el Grupo  de Automorfismos de M0.  

3.2 Ahora vemos con detalle la segunda manera de modificar o desordenar M0, obteniendo como resultado una matriz no isomorfa.

Tenemos que encontrar todas las maneras posibles de realizar esto cumpliendo con las condiciones que ya hemos comentado: no modificar el orden del grafo, no modificar el grado de cada vértice etc…

Primero explicamos todo esto en palabras. Luego ilustraremos la idea con un par de imágenes. 

Modificaciones que no son admisibles, de acuerdo con las condiciones:

–no se pueden añadir vértices, ya que en este caso se pasaría de una matriz nxn a una matriz mxm con m>n. Esto sería una modificación del orden fácilmente detectable.

–no se pueden añadir arcos (no se pueden añadir un 1 en la matriz a los que ya hay, cambiandolo por un cero). Esto se corresponde con cambiar el grado de algún vértice.

Nota.

Tras redactar la entrada, y reflexionar un poco me he preguntado si a lo que he llamado condiciones no se le podrían llamar invariantes. Entonces lo mejor sería añadir a la lista cuantos más invariantes conociésemos mejor. Cuántos más invariantes añadamos, entiendo que más complicadas serán las matrices que se obtengan. A este grupo se le puede llamar entonces el «grupo de invariantes».

Mañana tras darle alguna vuelta más, modificaré la entrada y la imagen en este sentido: partiendo de la matriz inicial M0, se pueden entonces construir dos grupos el de automorfismos que dejan al grafo igual, y ¿ el de invariantes que lo modifican pero dejándolo similar ? Ya digo, le tengo que dar otra vuelta a este tema

.  Fin de nota.

–las transformaciones no pueden ser solo del tipo de las consideradas en el punto anterior, en cuyo caso obtendríamos un elemento de MisoX.

Modificaciones admisibles: 

–Una de las posibles maneras de conseguir esto es intercambiando pares de ceros por unos en las casillas de la matriz, de tal manera que no se modifiquen los parámetros o invariantes del grafo. Ejemplos de parámetros o mejor dicho invariantes son: examples of graph invariants are things like max-degree (an isomorphism preserves max degree), chromatic number, number of vertices, number of edges, length of longest path, diameter, edge density, number of connected components, and so forth.   Los invariantes son funciones asignan valores (por ejemplo números enteros) a grafos. Por ejemplo el número de vértices. Lo importante para esto es que cada uno de los elementos del conjunto de invariantes que se impondrán como condición que tienen que cumplir las transformaciones se puedan computar, cada uno de ellos de manera eficiente. Dado un conjunto de invariantes computables de manera eficiente, habrá múltiples (un número finito) transformaciones de este tipo que cambian pares de ceros por unos sin cambiar estos invariantes. Si dos grafos son isomorfos, el valor que tienen que dar al computar todos los invariantes será el mismo. Si no son isomorfos variarán en al menos el valor de un invariante. Como no existe una lista completa de invariantes, actualmente es posible que para dos grafos dados se pueda obtener valores iguales en todos los invariantes conocidos siendo los grafos diferentes. Llamemos al conjunto de transformaciones que cumplen con las condiciones invariantes T2. Estamos dando por supuesto que el conjunto de todas las transformaciones del tipo T2 forman grupo, y pienso que así es, pero realmente habría que demostrarlo. ¿ Pq pienso que es un grupo ? Pq cualquier transformación se puede expresar como una permutación, cualquier par de permutaciones se puede componer, y cualquier conjunto de permutaciones genera un grupo.   

–una vez que has realizado una modificación de las anteriores, que ya has obtenido un grafo de una clase diferente al inicial dado por M0, entonces si se pueden aplicar transformaciones del tipo permutaciones de columnas y filas.

No se si con estos dos tipos de transformaciones estamos siendo exhaustivos. De nuevo, aún siendo esto clave, no queremos cerrar este detalle ahora mismo. Lo que si parece claro es que esta manera de transformar la matriz M0 para obtener una no isomorfa, también se puede expresar por medio de teoría de grupos, por medio de grafos de Cayley.

El vértice inicial para la construcción es el mismo que antes M0, primero se tiene que aplicar una transformación del tipo T2, y obtenemos una matriz del tipo MnoisoX a la cual ya podemos aplicar ya transformaciones de los dos  tipos. Entiendo que aquí no estamos hablando de generar un grupo sino de generar una familia de grupos (de (dí)grafos de Cayley): la familia de grupos que se puede obtener aplicando a la matriz M0 una transformación inicial del tipo cambios de 0 por 1s que no modifican los parámetros y luego transformaciones de los dos tipos (cambios de ceros por uno u permutaciones de filas por columnas. Si no me  equivoco estamos hablando de un grupoide.  

Nota. No está claro que lo que obtenemos sea un grupoide: ¡¡ con el algebra abstracta hemos topado !!. 

Haz clic para acceder a groupoidsurvey.pdf

Seguimos estudiando el tema. 

EXAMPLE 4. Groups occur naturally as automorphism groups, or symmetry groups, of various structures; and this is a fundamental observation behind Klein’s famous Erlangen Programme: study a geometry by means of its group of automorphisms. It has more recently been found fruitful to consider not just one geometry, or one structure, but indexed families E = {Ex}x∈B of structures, often thought of as constituting a ‘bundle’ E over B, with projection p : E → B, and with Ex = p −1 (x). The ‘symmetry’ of such a gadget is appropriately expressed by the groupoid G(E), with object set B, and with elements consisting of all isomorphisms Ex → Ey for all x, y ∈ B. For x in B, the group G(Ex) of
automorphisms of Ex expresses the ‘symmetry’ of Ex. These ‘varying symmetries’ are encompassed in the groupoid G(E). An isomorphism Ex → Ey allows one to define an isomorphism G(Ex) → G(Ey) of groups, and so gives ‘transport of symmetry’. Perhaps G(E) should be called a symmetry groupoid. This idea is at the root of many applications of groupoids pioneered by Ehresmann in differential geometry [54]. If p : E → B is a principal bundle with group H, then G(E) is to consist of the admissible maps Ex → Ey, x, y ∈ B, that is, the homeomorphisms commuting with the action of the group H. If p : E → B is locally trivial, then the trivialisations determine a topology on G(E), or even, in the differentiable case, a differential structure. For references to the literature in this area, see [21, 22, 99].
The use of groupoids for studying order-disorder structures in crystals [48, 59] suggests further
possibilities for the general analysis of ‘variable symmetry’ – see [60] for a recent article.

Parece que para que una familia de grupos sea grupoide  se tienen que considerar a estos como elementos de una estructura algebraica con la que se hacen determinadas operaciones. De momento no es nuestro caso. Simplemente son grupos que se han construido de una manera similar. 

Fin de nota.

Habrá tantos grupos ((dí)grafos de Cayley en esta familia (¿ grupoide ?) como transformaciones del tipo cambios de 0 por 1 haya de la matriz inicial M0. Llamemos a esta familia-¿grupoide? Groidnoiso y a cada uno de los miembros de esta familia-¿grupoide?, GrMnoisoX.

A partir de aquí surgen múltiples dudas:

–¿ Una vez que se tiene la matriz inicial de cada GrMnoisoX como se construye el grupo correspondiente ?. No tengo claro si se debe permitir que la transformación que da vida al grupo (aquella que se ha aplicado a M0 para obtener la matriz inicial de GrMnoiso1, por ejemplo) forme parte de este o no.

Si se permite, entonces la matriz M0 podría volver a aparecer cosa que no creemos conveniente. Entonces, aunque el tema no está claro, asumimos que no se permite. Si no se permite que forme parte, entonces surgen una serie de preguntas a las que no tenemos contestación de momento:

–Una duda es clave, no se puede de un grupo quitar solo un elemento y obtener otro grupo igual al anterior , siendo la única diferencia que en el segundo no exista este elemento. Para esto hay que mirar a la estructura de subgrupos. Entiendo que habría que escoger el mayor subgrupo que no contenga al que no queremos que esté. ¿ Y si hay varios de estos subgrupos que no lo tengan pero que tengan el mismo tamaño ?

–¿ Todos los grupos de esta familia-¿grupoide? de grupos serán isomorfos en abstracto ? Diría que son similares pero no tengo claro que sean isomorfos. ¿ Pueden tener dos GrMnoiso1 y GrMnoiso2 elementos en concreto (matrices) isomorfas ?. Diría que no. Pero no lo tengo 100% claro.

–contiene la familia de grupoides

–Antes hemos vistos que GmisoX es igual al grupo de automorfismos de M0. Que relación tiene cada grupo de la familia-¿ grupoide? con el grupo de automorfismos de la matriz de la que se parte para construirlo ? En este caso no parece que sea de igualdad. Pero entiendo que que el grupo de automorfismos de cada una de estas matrices iniciales si que es un subgrupo de cada uno de estos sugrupos.

Aclarar estas cuestiones y otras es importante, pero de nuevo no nos interesa aclarar hasta el último detalle (aunque este, ya decimos es muy importante) sino llegar hasta el final. Seguimos.  

Vemos todo lo descrito en la siguiente imagen. Ojo, la imagen no es realista, no muestra un ejemplo real. La matriz está mal escogida, las transformaciones que hemos aplicado a las dos primeras matrices no son correctas y no hemos transformado a las otras. Y además no se refleja todo lo que aparece en el texto. Sirva solo como muestra gráfica de lo que tenemos en la cabeza y descrito en el texto.

 

 

Importante: no se debe de considerar esta imagen como la última palabra. Es más bien un estado inicial (tal y como veo ahora el tema) que se irá desarrollando en un sentido o en otro en función de como se aclaren las dudas (y ya solo con respecto a la imagen hay bastantes). Sinceramente es mi visión actual, pero no tengo claro que sea no solo la definitiva sino tampoco la correcta. Y a diferencia de lo que me pasa con los grupos de permutaciones, no tengo ni demasiado conocimiento o intuición con los grupos de matrices.

Nota. Viendo como se generan los inputs de este problema tiene sentido que pueda haber problemas de isomorfismo más sencillos que otros, en función de que la matriz M0 sea más estructurada (por ejemplo sea una tabla de Cayley de un grupo) o menos estructurada (una matriz de un grafo). Esto se tiene que trasladar tanto al grupo de automorfismos como a la familia de grupos, pero todavía no puedo expresar como con claridad. Otra cosa es que estas diferencias se traduzcan en saltos exponenciales o subexponenciales de complejidad. Fin de nota.    

Actualización 19 de marzo de 2019. Aterrizando la idea. 

Es posible que todo lo relativo a este punto haya quedado poco claro. Ilustramos con algunas imágenes una de las posibles implementaciones de la idea que manejamos con el fin de comprender como se utilizan los invariantes para resolver el problema de isomorfismo. Quede claro que no pretendemos en esta entrada desarrollar plenamente este tema. Lo que sigue por lo tanto no es más que un esbozo de desarrollo de una de las posibles implementaciones o aterrizajes de la idea. Como veremos esta implementación podría ser un aterrizaje forzoso, y por lo tanto no la más adecuada. Para cualquier desarrollo más completo de este tema tendríamos que invertir un tiempo del que no disponemos. Queremos (tenemos que) estar bien informados sobre los problemas de isomorfismos, pero trabajar en ellos no  es para nada prioritario.

 

 

La imagen anterior presupone que se ha aplicado antes para este grafo el método con el invariante de conexión y de número de vértices. Analiza la situación para el invariante grado de los vértices. Lo importante en este invariante no es que  un vértice en concreto mantenga su grado si no que al final el «vector» de grados de los vértices sea el mismo sin importar el orden.

Para modificar los grafos utilizamos una transformación que llamamos reconexión de un arco. El arco que se reconecta tiene que mantener el contacto con al menos uno de los dos vértices con los  que ya estaba en contacto. Se desconecta de uno de estos dos vértices y se conecta con cualquier otro vértice del grafo.

Si definimos así el concepto de reconexión cada arco se puede reconectar de múltiples maneras: si excluimos loops de (v-2) maneras (con v el número de vértices). Algunas de estas reconexiones no serán válidas pues generarán arcos múltiples. O no  cumplirán con todas las restricciones que imponen la lista de invariantes.

A cada reconexión de un arco de la manera indicada, le corresponde una serie de intercambios de ceros por unos en la matriz de adyacencia correspondiente.

Lo importante es que:

–primero, con las transformaciones de reconexión que conservan el valor de los invariantes en ocasiones obtenemos grafos isomorfos al inicial (y entonces,¿¿ debe de considerarse esta transformación un automorfismo, dado que hay una serie de permutaciones de filas y columnas que permitirían obtener esta misma matriz ??) y grafos no isomorfos al inicial (estas son las transformaciones que  forman parte de lo que hemos llamado el grupo de invariantes, pero esto se tiene que demostrar: igual ni forman un grupo). Entonces ¿¿ con este tipo de transformaciones podemos ir generando tanto  el grupo de isomorfismos como el grupo de invariantes ??.

–segundo, el invariante que estamos considerando (grado de los vértices) no es completo para este grafo (que por cierto es irregular) dado que hay grafos no isomorfos que lo cumplen (de manera equivalente el grupo de invariancia o  de invariantes no es el trivial). Ya la mera observación de las diferencias entre los grafos no isomorfos sugiere cual podría ser el próximo invariante a utilizar: tiene que tener que ver con los  ciclos a los  que pertenecen los vértices. Este nuevo invariante será un nueva restricción que se añade a la lista.

Falta comprobar que las transformaciones de lo que hemos llamado grupo de invariantes forman realmente grupo. Para ello habría que considerar que cada transformación de las consideradas son un elemento del grupo, cada uno de estos elementos tiene que tener un inverso y todo par de transformaciones se tienen que poder componer y obtener otro elemento del grupo.

Tampoco es que nos interese especialmente desarrollar este tema hasta el final (y quizás tampoco sea importante que las transformaciones por reconexión formen grupo) pero al menos hay al menos he visto una manera de hacer esto (seguramente un poco forzada y no se si correcta del todo). En la imagen aparecen tres Transformaciones T1, T2 y T3 que serían los elementos reconectar c, reconectar a y reconectar b. Sus inversos son ellos mismos (son involuciones) e invierten la reconexión de cada uno. Hay que añadir la identidad TI que sería no reconectar nada. La idea es que cualquier composición de elementos dejen la figura inicial inalterada (y por lo tanto se cumpla la condición invariante).

Partimos por lo tanto de la figura de un ciclo de 4 y al aplicar reconexiones aplicando las transformaciones del grupo obtenemos la misma figura. ¿ Sería por lo tanto un grupo de automorfismos de la figura inicial (que es la que tiene un ciclo de 3) modificada (a la del ciclo de 4) ?. Normalmente los grupos de automorfismos no se construyen en base a reconexiones sino a movimientos de figuras que precisamente evitan las reconexiones. El grupo de automorfismos de la figura que tiene un ciclo de 4 construido como se hace habitualmente, aunque no es el trivial, no tiene 4 elementos, como el que consideramos nosotros, sino 2. Por lo tanto es dudoso que se pueda hablar de grupo de automorfismos. De cualquier manera, el lector puede intentar construir una tabla de multiplicación y ver que esta se puede construir, en el sentido de que con toda composición de las reconexiones indicadas se obtiene siempre la figura de ciclo  4. Ojo, no se podría construir si utilizásemos la otra reconexión de b (según la imagen). En ese caso al componer b con a no se obtiene el grafo inicial (el del ciclo 4) sino el de ciclo de 3 que no conserva el valor del invariante. En fin a todo esto le falta todavía algo importante. No nos satisface del todo. Y además, como en entradas anteriores estamos trabajando con un solo caso de grafo y muy pequeño, que consta de pocos elementos (vértices y arcos) y la variedad que se genera con estos elementos es mínima (unos 5 grafos no isomorfos: el ciclo de 5 vértices, el de ciclo de 3 inicial, otro ciclo de 3 vértices pero con una distribución de grados diferente del inicial: 1,1,3,3,2 y el ciclo de 4 con una rama) lo cual en teoría de grafos no es indicativo de nada.

En la idea original el ¿grupo? de invariantes sería el conjunto de transformaciones que generan matrices no isomorfas a la original (que en este caso sería la de ciclo 3) y que cumplen con el invariante considerado (en este caso el invariante de distribución de grados). Y por lo tanto no sería un grupo de automorfismos. En este caso pequeño con el que estamos trabajando, de todos los grafos posibles que se pueden construir con estos elementos (que hemos listado  en el párrafo anterior), solo hay un grafo que no es isomorfo al original y cumple con el invariante de distribución de grados: es el de un ciclo de 4 vértices con una rama. Es posible  que por ello el «grupo» que hemos obtenido sea un «grupo de automorfismos». Pero en general no tendría que ser así. En conclusión, habría que mirar todos esto para casos más grandes.

Obviamente tras esta ilustración de una de las posibles implementaciones de la idea que tampoco está rematada del todo, surgen múltiples interrogantes:

–si esta implementación de la idea es prometedora ¿ sería posible generar todo el grupo  de automorfismos y todo el ¿grupo?  de invariancia con este tipo de transformaciones de reconexión de solo un arco ?. Parece obvio que no es así. Seguramente al final se tendrán que considerar reconexiones de un solo arco más generales, reconexiones de dos arcos, de tres arcos, etc…Por reconexiones mas generales entendemos por ejemplo una defiinición de reconexión de arcos que permita incluso desconectar completamente un arco y reconectarlo completamente. Si así es (si tenemos que utilizar reconexiones de 2, 3 …arcos), todo esto nos indica que este método sería exponencial, lo cual en esta entrada no nos importa.

–¿ es posible que el estudiar los grafos no isomorfos al original que conservan el valor de un invariante nos pueda indicar en cada iteración cual es el siguiente invariante a tener en cuenta, tal y como el caso estudiado sugiere ? De confirmarse, esto sería muy interesante, pues permitiría de alguna manera automatizar el proceso  que estamos considerando.

Está claro que habrá familias de grafos para las que lleguemos a tener una lista de invariantes completa de tamaño constante (una lista de restricciones). Por ejemplo los disconexos, los irregulares, los regulares de un determinando tipo….Pero ya dentro de todos estos hay familias en los que esto no existe de momento. Al parecer la familia más compleja para pasar de un algoritmo subexponencial a otro cuasi-polinómico fue un tipo de grafos vértice transitivos, los grafos de Johnson. Nótese que un grafo disconexo, uno irregular…pueden ser complicado de resolver siempre y cuando estén compuestos de una parte digamos disconexa, irregular…sencilla y una parte que sea isomorfa a un grafo de Johnson y que, antes del resultado de Babai, fuese compleja de resolver. Para simplificar nos olvidamos  del resto y nos concentramos en la parte más compleja. Por esto se dijo que el problema de isomorfismo se reduciía a resolver los grafos de Johnson.

Todo indica (mi intuición en base a las lecturas de los últimos días así me lo indica) que dentro de los grafos vértice transitivos la siguiente familia que va a ser el obstáculo para que este problema pase de QP (tiempo cuasipolinómico) a P (tiempo polinómico) va a ser una familia de grafos de Cayley: los grafos de Cayley de  grupos nilpotentes o más concretamente los p-groups of class 2 and exponent p are widely believed to be the hardest case of Group Isomorphism (p>2), fuente: https://cstheory.stackexchange.com/questions/42537/what-is-the-hardest-instance-for-the-group-isomorphism-problem. Aunque en la entrada hablan de grupos y no de grafos, tal y como venimos comentando en anteriores entradas, también para grafos parece que al final el último escalón va a ser esta familia de grafos de Cayley.

Nótese que entre la mayoría de las familias de grafos sobre las que hemos hablado se puede construir unas relaciones de contención estrictas:

disconexos > conexos > regulares > vértice transitivos > Cayley >Nilpotentes > p-grupos de clase 2.

Esto es matizable ya que según como se definan, entiendo que puede haber regulares disconexos.

Sin embargo no se da este tipo de relación entre Johnson y Cayley. Si no estoy equivocado, algunos de los grafos de Johnson son Cayley, pero la mayoría no. Y viceversa.

El lector se preguntará si nuestros métodos estructurales sobre dígrafos de Cayley no serán aplicables al problema de isomorfismo de grafos de Cayley. La respuesta es si y no. Si a algunos no a otros (por ejemplo a los de grupos cíclicos). ¿ Y a grafos de Cayley de p-grupos de clase 2 ?. Es un tema que tenemos pendientes de estudiar.

Fin de actualización.

Actualización 21 de marzo. Análisis de otro caso y comentarios finales. 

En esta actualización vamos a seguir explorando la ilustración de la actualización anterior justo  con un grafo un poco más complicado. De nuevo, solo con el caso anterior y este caso van a ser muy pocos los datos para llegar a conclusiones. Pero quiero hacer un par de comprobaciones muy concretas.

Como se ve en este caso con los mismos elementos que el grafo inicial, podemos construir 6 grafos conexos simples no isomorfos. En la imagen aparecer el correspondiente valor del invariante que estamos considerando. Lo  interesante es que en este caso hay 2 grafos no isomorfos al inicial que conservan el invariante. Esto difiere de la situación anterior en la que solo había 1.

En lo que sigue vamos a estudiar las reconexiones más sencillas (1 solo arco y tiene que mantener el contacto con uno de los dos vértices con los que está en contacto en el grafo inicial). Algunas preguntas que nos interesa contestar son:

–¿ podemos obtener todos los grafos no isomorfos sólo con este tipo de reconexiones ?

–¿ puede construirse algo parecido al «grupo» que hemos obtenido en el ejemplo anterior ?.

Veamos las reconexiones de todos los arcos:

Para el tipo de grafos que estamos considerando (que se pueden considerar modificaciones de un ciclo de n arcos y n vértices) las reconexiones que estamos considerando son bastante potentes: reconectando un solo arco (el a) se pueden obtener todos casi todas las clases de isomorfismo. Reconectando dos arcos (por ejemplo a y b) se pueden obtener todas las clases de isomorfismo. Reconectando solo un arco (por ejemplo a) se pueden obtener todas las clases de isomorfismo que conservan el valor del invariante que consideramos.

Todo esto, con estos dos ejemplos, todavía sigue siendo demasiado elemental para que sea interesante. Consideremos ahora el tipo de grafos más sencillos por encima de los que hemos estado considerando: un grafo de un ciclo más un arco adicional. El ciclo de 4 + 1 arco y el ciclo de 5 + 1 arco no llevan a nada interesante.

Veamos el ciclo de 6 más un arco. Con este pequeño salto la cosa ya pasa a ser bastante complicada. Solo determinar cuantos grafos conexos simples no isomorfos podemos generar con estos elementos ya puede llevar su tiempo. Y se ve claramente que una sola reconexión pierde su potencia. Hay clases de isomorfismo que para llegar a ellas ya se va a necesitar reconexiones de más de dos arcos. Por ejemplo para obtener un  grafo con el valor para el invariante distribución de grado I(G)= (1,1,2,2,3,5), partiendo del ciclo de 6 con un arco adicional, se necesita reconectar al menos 3 arcos. Esto de alguna manera contesta a la primera pregunta.

Con respecto a la segunda pregunta:

También en esto a medida que el grafo es más complejo cambia la cosa con respecto al tema que estamos considerando. Ahora tenemos ya tres grafos no isomorfos al inicial y no isomorfos entre ellos que conservan el valor del invariante que estamos considerando. A los tres se puede llegar desde el inicial por la reconexión de solo dos arcos, el c y el e.

Si se quisiese construir un grupo en base a todos esto sigue sin estar nada claro que se debería de considerar transformación. Está claro que tiene que ser una reconexión de un arco que conserve el invariante. Pero en este caso  reconectando sólo c (de manera alternativa por simetria solo e) ya dos varias reconexiones diferentes que conservan el invariante y de que las que además se obtiene el mismo grafo. ¿ Transformación es cualquier reconexión de c (de manera alternativa de e) ? ¿ O es cada una de las dos ?. ¿ Y se pueden considerar reconexiones de dos arcos como partes de una transformación única, aplicando las dos reconexiones a la vez ?. Todavía hay poca casuística. La guía tiene que ser el cambio mínimo de ceros y uno que se refleje en la correspondiente matriz. Si una reconexión de un solo arco es conservativa y se obtiene un grafo no isomorfo cuenta como transformación por si misma. ¿ Y si otra reconexión del mismo arco es conservativa y se obtiene el mismo grafo que el anterior ?.

Recordemos la motivación inicial de este punto. En una visión muy general de esta motivación, estamos explorando formas de generar grafos similares a un grafo dado pero no isomorfos a éste. Consideramos que serán similares aquellos a los que se les haya realizado alguna modificación (por ejemplo reconectar uno o varios arcos) de tal manera que no altere el valor de los invariantes conocidos. Es decir que pese a la modificación, los dos grafos tengan el mismo valor en todos los invariantes conocidos. En base a esta motivación hemos estudiado un modelo sencillo en el que los grafos dados son muy sencillos (así han sido en los tres casos), el invariante considerado que se tiene que conservar es de los más básicos (la distribución de grados) y los tipos de reconexión aceptables son también de los más sencillos.

En base a este modelo hemos estudiado para tres casos (seguramente muy poco representativos) los dos siguiente problemas: en primer lugar, dado un grafo, un tipo de invariante cuyos valores se deben de conservar, y unas reglas de modificación (el tipo de reconexión), encontrar con el menor coste posible (que lo deseable es que fuese en tiempo polinómico) todos los grafos que modificados de acuerdo con las reglas, conserven el invariante pero no sean isomorfos al dado. En segundo lugar determinar si el conjunto de reconexiones que permite obtener estos grafos conservativos no isomorfos forman algún tipo de estructura algebraica, concretamente un grupo.

Ciertamente el primer punto es un poco como la pescadilla que se muerde la cola: para resolverlo tendrías que poder resolver rápidamente el problema de no isomorfismo. Con el matiz de que el problema es más restringido que el problema de no isomorfismo: el input no son dos grafos cualesquiera de los que tienes que demostrar no isomorfismo sino un grafo, un invariante cuyo valor hay que conservar, y unas reglas de modificación. Con estas restricciones y reglas se obtienen grafos cuyo problema de no isomorfismo con el inicial puede no ser tan complicado como el general. Además de esto, en todos los casos que llevamos analizados (cierto, 3 y pequeños; muy poco, mínimo) aparece otro invariante que es muy aparente (el tamaño de los ciclos) y nos permite determinar el no isomorfismo.

Con estos tres casos analizados, es suficiente para ver un poco como se pueden generar, dado un grafo y un invariante, otros grafos para el problema de isomorfismo / no isomorfismo: parece claro que si mantenemos fijo el invariante, a medida que los grafos dados como input sean más complejos se necesitarán más y más reconexiones de arcos para poder obtener todas las clases de isomorfismo conservativas que se pueden obtener del grafo inicial. Es decir no todos los grafos conservativos del invariante no isomorfos estarán a tiro de una reconexión. A este respecto creo que una pregunta interesante es determinar cual es el mínimo número de reconexiones de arcos (por ejemplo, en los dos primeros casos, este número mínimo sería 1, y en el último caso analizado serían 2) que se necesitan para generar todos los grafos conservativos de un grafo e invariantes dados. ¿ Es posible que los casos más difíciles sean los que necesitan más reconexiones, los que estén más lejos del inicial ?. Recordamos que nuestra idea inicial era centrarnos en el conjunto de transformaciones que implicaban una sola reconexión. A la vista de lo comentado esto es claramente insuficiente.

Con respecto a si el conjunto de reconexiones de arcos (del tipo de las consideradas) de un grafo dado, que generan este conjunto de grafos conservativos (del invariante dado) no isomorfos, puede formar de alguna manera un grupo, no tengo nada nada claro el tema. Ni siquiera como abordarlo de momento. Parece que estamos intentando estudiar la acción de una estructura algebraica sobre un objeto (un grafo). Me temo que las acciones de grupos en estructuras (conjuntos, grupos etc..,) es otra manera de estudiar el grupo de automorfismos de estas estructuras.

En fin, como se ve, todo esto requiere más investigación. Como no es prioritario, aquí lo dejamos.

Fin de actualización. 

Actualización 22 de marzo. Análisis (ligero) de un caso basado en un grafo de Cayley. 

No queríamos despedirnos de este tema sin ver como se traslada todo lo que hemos visto sobre reconexiones, conservación de invariantes a un caso que sea un grafo de Cayley. Lo vemos muy rápida y ligeramente.

La imagen está extraída de la web. La hemos reprocesado cambiando las etiquetas de los vértices que estaban en notación cíclica de permutaciones por notación lineal. El grafo inicial es semántico. Pero al reconectarlo pierde esta semántica. Hemos añadido también etiquetas a los arcos. Toda esta información se pierde cuando lo empequeñecemos.

El analizar este caso es informativo. Es más realista ya que los grafos a los que normalmente se enfrentan los algoritmos  de resolución del problema de isomorfismo son regulares. Y ya podemos sacar algunas primeras conclusiones sobre grafos regulares: no admiten reconexiones de un solo arco. No serán conservativas del invariante de grado. Esto nos ayuda a pulir la definición de transformaciones. Una 1-transformación es aquella que implica la reconexión conservativa de un solo arco. Hay grafos (todos los regulares) en los que no existe este tipo de 1-transformaciones. En estos existen 2-transformaciones, que son aquellas que implican la reconexión conservativa (del grado) de 2 arcos. Habrá casos en los que con conjuntos de 2-transformaciones se generen todas las clases de isomorfismo del grafo dado. En otras ocasiones serán necesarias 3-transformaciones (en las que se requieren necesariamente la reconexión de 3 arcos) etc….

¿ Cuantos grafos no isomorfos pueden obtenerse mediante 2-transformaciones en este caso ? Esto se puede acotar rápidamente. Vamos a ver: cada arco, si lo fijamos por un extremos a un vértice, se puede reconectar a (v-2) vértices. V aquí es el número de vértices. Se resta dos dado que si está fijado a un vértice, no se podrá reconectar a aquellos vértices con los que este vértice está en contacto directo. Como el grado es 3, este número es 2. Cualquier reconexión que se haga con un vértice quitando estos dos, origina que el arco al que este vértice estaba conectado tenga que conectarse con el vértice que el primer arco deja libre. Todo esto para conservar el invariante de grados. Por lo tanto lo que haga el segundo arco de la 2-transformación está completamente determinado. No cuenta. Como 1 arco se puede fijar a dos vértices, tenemos 2(v-2), que en este caso es 20. Podemos acotar más esta cota superior. Algunos datos:

–¿ La vértice transitividad garantiza que no tengamos que repetir lo mismo para cada arco ?. ¿ Con que lo hagamos con uno ya es suficiente ?. Esto no es correcto:  el grafo es vértice transitivo pero no arco transitivo. Pero tampoco hay que probar para todos los arcos pues aunque no todos los arcos son equivalentes a estos efectos, algunos si lo son. Lo que diferencia a los arcos es, quizás entre otras cosas, su relación con los ciclos: algunos hacen frontera de un ciclo de 6 con uno de tres, algunos un ciclo de 6 con otro de 6 y otros son  borde de un ciclo de 3 y otros son borde de un ciclo de 6. Tenemos por lo tanto como poco 4 tipos de arcos. Quizás no todos estos tipos sean diferentes, en el sentido de que no se manifiesten de diferente manera. Seguramente la frontera con el exterior no existe y es solo efecto del dibujo. Entonces los tipos se reducirían a 2.

–cuando en una 2-transformación intervienen dos arcos del tipo que dividen dos ciclos de 6 y pertenecen al mismo ciclo de 6, o una combinación de estos con uno borde entre un ciclo de 6 y el exterior, se obtiene siempre un grafo isomorfo al inicial (así ocurre experimentalmente y habría que demostrar pq pasa esto; no parece complicado).

Habría que incorporar toda esta información a la cota. De momento vamos a ver algunas reconexiones. Lo vemos en la imagen siguiente. En ella ya se han identificado algunas clases de isomorfismo que se obtienen por modificación por 2-transformaciones. La lista no es exhaustiva pero no deben de quedar muchas más. Ni de lejos llega hasta la cota superior que hemos dado. Y en la lista hay casos en los que es fácil determinar que no son isomorfos al inicial pero no es tan sencillo determinar visualmente con un análisis superficial del invariante ciclos si lo son entre ellos. ¿ Podemos especular que estos son los que son complicados para los algoritmos de isomorfismo ?. Si es por especular, podemos, pero tampoco lo se.

Reconectar un arco del tipo 1 con otro del tipo 3 que no pertenezcan al mismo ciclo se puede hacer de varias maneras (diría que dos). Dos de ellas (o las dos) generan un mismo grafo diferente al inicial. Esta es una de las clases de isomorfismo. El representante de esta nueva clase de isomorfismo pierde la vértice transitividad, pero no se obtiene cualquier cosa, se obtiene una «figura» regular y geométricamente descriptible: una especie de octágono, con triángulos en cuatro de sus lados opuestos y dos cuadrados en dos lados opuestos. Sería interesante estudiar el grupo de automorfismos de este nuevo grafo y su relación con el del grafo del que se ha transformado. No obstante como se ve en la imagen no es lo más general.

Parece claro que hay grafos modificados que se pueden obtener con tres reconexiones y no con dos. Lo vemos en la siguiente imagen: hay algunas clases nuevas, que efectivamente no se pueden obtener con pares de reconexiones. Pero no tantas. Como se ve ocurre el mismo fenómeno que con dos para los arcos que pertenecen a un ciclo de 6, que si se combinan en una 3-transformación se obtiene el inicial. También hay 3-transformaciones que dan grafos que se pueden obtener con 2-transformaciones. Lo vemos en la imagen siguiente en la que el análisis no ha sido para nada exhaustivo, pero si ilustrativo. Me pregunto si hay 4-transformaciones que generan algo nuevo.

Fin de actualización.

Actualización 23 de marzo. Sobre el ¿ grupo de reconexión conservativa?. Y análisis de un caso de un grafo simétrico (vértice transitivo y arco transitivo). 

En esta actualización hacemos primero algunos comentarios sobre la construcción del «grupo» que en otros puntos hemos llamado de invarianza pero pensamos que el nombre más adecuado es el de «grupo» de reconexión conservativa para un invariante dado y luego para rematar la faena analizamos un caso de los llamados grafos simétricos (vértice transitivos y arco transitivos).

a) Grupo de reconexión conservativa. 

Grupos de permutaciones: Veamos primero como se genera un grupo de permutaciones. Se parte de una identidad (que por convención se elige la permutación que ordena el conjunto por orden lexicográfico, por ejemplo 12345, pero podría ser cualquier otra). A esta identidad se le aplica una transformación (que es una permutación) y se obtiene otro elemento (que también es una permutación. Esto es un poco confuso en los grupos de permutaciones, pues se utiliza el mismo nombre tanto para las transformaciones como para los elementos. Entonces partimos  de la elemento-permutación identidad y de un conjunto de transformaciones-permutaciones. Es importante señalar que no todo conjunto de transformaciones-permutaciones forma un grupo. Pero si se puede considerar a todo conjunto de transformaciones-permutaciones un generador de un grupo. ¿ Como es esto ? A la elemento-permutación identidad se le aplica una serie de transformaciones-permutación para obtener otros elementos-permutación. Se repite este proceso hasta que ya no se obtiene ningún elemento-permutación nuevo. En este caso todos los elementos nuevos que hayamos obtenido forman un grupo por la operación de composición de permutaciones.

Construcción del grupo. Lo que está claro: matriz y reconexión como elemento-permutación y las reconexiones como transformaciones-permutaciones. Si etiquetamos a cada casilla de la matriz por sus correspondientes (i,j), y vamos convirtiendo cada columna en fila y concatenamos todas estas columnas en forma de una fila y luego concatenamos con esta fila de n^2 elementos todas las filas de la matriz obtenemos, digamos, un vector fila de 2*n^2 posiciones que representa a la matriz. Llamemos a este vector el vector-matriz. Aplicar transformaciones de reconexión es equivalente a considerar transformaciones-permutaciones sobre de un conjunto de tamaño 2*n^2.

Cuando representamos un grafo en forma de matriz de adyacencia, al hacer una reconexión de las que estamos considerando, hay que hacer cambios en filas y en columnas. Por lo tanto cuando operemos con el vector-matriz tenemos que tener en cuenta y para a reconexión  le tienen que corresponder en el vector-matriz cambios en las columnas y filas. Si tenemos todo esto en cuenta, al igual que el vector-matriz es equivalente al conjunto sobre el que se aplican las transformaciones-permutaciones, las reconexiones se pueden considerar transformaciones-permutaciones. Si no me equivoco, todas las reconexiones, sean 1-transformaciones, 2-transformaciones,….serán siempre involuciones. Si se puede construir un grupo con las reconexiones será un subgrupo de S(2n^2) el grupos simétrico  de 2*(n^2) elementos, construido con involuciones.

Entonces al igual que partiendo de un elemento-permutación identidad, aplicando transformciones-permutaciones, podemos obtener un grupo, la pregunta es si no ocurrirá lo mismo si partiendo de un vector-matriz, al aplicar un conjunto de transformaciones-reconexiones-permutaciones dado, se obtienen otros vectores-matriz diferentes al inicial, y si iterarando este proceso no obtenemos una serie de vectores-matriz que forman un grupo.

Construcción del grupo: lo que no está claro.

Creo que la idea de pq pensamos que lo que tenemos en la cabeza pueda ser un grupo está clara. Lo que no está claro es de todas las reconexiones que se pueden realizar, cuales debemos de incluir en el conjunto de reconexiones que se utilizará para obtener los elementos vector-matriz (que son grafos diferentes al inicial):

–ya vimos  ayer que una reconexión se debe de tener en cuenta si es conservativa del invariante y si el elemento-vector-matriz que se obtiene no se puede obtener mediante otras reconexiones más sencillas. Es decir si al aplicar una 2-transformación el vector-matriz que se obtiene se puede obtener de una 1-transformación, esta 2-transformación no formará parte del conjunto inicial.

–¿ las 2-transformaciones no pueden contener 1-transformaciones y además no puden tener ellas ningún arco en común con otras 2-transformaciones ?. Es decir supongamos que tenemos ya una lista de 1-transformaciones que implican a los arcos 1,2 y 3. Entonces ¿ cualquier 2-transformación no puede contener a estos  arcos ?. ¿ Serían entonces 2-transformaciones posibles (4, 5), (6,7), pero no serían posibles (1,5), ni si (4,5) y (6,7) lo son (4,7) ?

–¿ que hacer con las reconexiones que son automorfismos, es decir tal que al aplicarlas al elemento-vector-matriz inicial dan como elemento-vector-matriz a este mismo elemento ?. Quizás la solución a esta duda sea considerar que el grupo que tenemos en mente, el grupo de reconexiones es un grupo que contiene como subgrupo al grupo de automorfismos, además de a otros grafos que no son isomorfos al inicial. En este caso se tiene que demostrar que todo automorfismo de todo grafo se puede expresar como una reconexión del tipo de las que estamos considerando.

–está claro que si se consiguiese un grupo de esta manera, al traducirlo al lenguaje de grupos de permutaciones, tendríamos la representación de un grupo de permutaciones por un permutaciones de un grado mucho mayor del necesario.

Un par de temas más:

–es posible que una vez obtenidos, digamos, los generadores (es decir un conjunto de transformaciones tal que cada una de ellas genere un grafo no isomorfo conservativo) al multiplicarlos unos por otros hasta que no se genera ningún elemento nuevo, obtengamos elementos indeseables (automorfismos, grafos no isomorfos conservativos que ya están en la lista de generadores…). Es posible que esto sea inevitable.

–ya hemos comentado que parece que todas las reconexiones de arcos que generan grafos no isomorfos (en realidad todas en general) son involuciones. Entonces podemos pensar que nuestro buscado grupo pueda estar en una de las dos siguientes posibilidades: es un grupo cuyos generadores son todos involuciones de este tipo pero cuyos elementos no son todos involuciones. Un ejemplo de este tipo de grupos son los Grupos de Coxeter (no necesariamente finitos): https://en.wikipedia.org/wiki/Coxeter_group  . Y si no solo los generadores sino todos los elementos son involuciones entonces estamos hablando de Grupos Booleanos. De nuevo no tiene mucho sentido preguntarse de momento si el grupo que buscamos es de tipo Coxeter o de tipo Booleano, ya que antes habría que aterrizar el tema. Quizás lo que buscamos ni exista. Pero así son las matemáticas: ¡¡ permiten conocer propiedades de objetos que no se saben si existen !!. Sobre grupos booleanos:

—In group theory, an elementary abelian group (or elementary abelian p-group) is an abelian group in which every nontrivial element has order p. The number p must be prime, and the elementary abelian groups are a particular kind of p-group.^[1][2] The case where p = 2, i.e., an elementary abelian 2-group, is sometimes called a Boolean group

https://en.wikipedia.org/wiki/Elementary_abelian_group

–finite Boolean groups are isomorphic to (Z/2Z)^n

https://math.stackexchange.com/questions/2934983/prove-that-finite-boolean-groups-are-isomorphic-to-mathbbz-2-mathbbzn

Here, Z/pZdenotes the cyclic group of order p (or equivalently the integers mod p), and the superscript notation means the n-fold direct product of groups.^[2]

–también interesante:

FINITE GROUPS WITH MANY INVOLUTIONS
ALLAN L. EDMONDS AND ZACHARY B. NORWOOD
Abstract. It is shown that a finite group in which more than 3/4 of the elements are involutions must be an elementary abelian 2-group. A group in which exactly 3/4 of the elements are involutions is characterized as the direct product of the dihedral group of order 8 with an elementary abelian 2-group. 

Haz clic para acceder a 0911.1154.pdf

Y si finalmente se consiguiese un grupo, cabría preguntarse que tal es este grupo como invariante del grafo inicial. ¿ Lo identifica plenamente o no ?. Esta pregunta es por supuesto prematura y además hay que desarrollarla mucho. Es posible que aun que el grupo que buscamos se pueda construir, el utilizarlo como invariante pueda ser ineficiente y/o ineficaz. Si finalmente contiene al grupo de automorfismos, tan eficaz y eficiente como invariante como pueda serlo el grupo de automorfismos….

En fin, aunque se ha desbrozado algo el camino, seguimos con muchas dudas sobre este tema.

b) Grafo simétrico.

Vamos a hacer un análisis rápido del tema de reconexiones a un caso de grafo simétrico (vértice transitivo y arco transitivo). El grafo original es el grafo cuboctaedro. Como se ve que sea arco transitivo quiere decir que todos los arcos son intercambiables, ya que, entre otras cosas, todos ellos se encuentran entre un ciclo de 3 y uno de 4. Hay grafos todavía más simétricos y seguramente más escasos todavía, que son aquellos en los que todos los ciclos son de un mismo tamaño. Conozco alguno de Cayley que tiene estos rasgos.

http://mathworld.wolfram.com/SymmetricGraph.html

Hemos realizado algunas reconexiones de este grafo, que aparecen en la imagen siguiente. De nuevo somos para nada exhaustivos. Sin mayor análisis, en este caso en general, tras una reconexión sigue siendo relativamente sencillo encontrar la diferencia con el inicial (por ejemplo contando los ciclos de 3) pero encontrar diferencias entre los diferentes transformados ya es más complicado. Diría que imposible visualmente. Yo mirando la imagen no sabría decir cuantas nuevas clases de isomorfismo existen.

Fin de actualización.

 

4.Problemas de isomorfismo. 

4.1. ¿ Que se da como input en el problema de isomorfismo ?.

En general el input para el problema de isomorfismo son dos matrices nxn.

En el punto anterior hemos visto todas las maneras posibles de generar variantes de inputs para el problema de ismorfismo de grupos en forma de matrices nxn. Como resultado tenemos todas las matrices que son elementos de GmisoX y de los diferente grupos de la familia-¿grupoide?. En principio, para obtener un input para el problema de isomorfismo, podemos escoger 2 matrices cualesquiera de entre todas estas.    

Según esto, los inputs para el problema de isomorfismo pueden ser de varios tipos:

Caso 1. dos matrices elementos de GmisoX.

Caso 2. una matriz elemento de GmisoX y otra de cualquiera de los grupos miembros de Groidnoiso.

Caso 3. dos matrices miembros de un mismo GrMnoiso, por ejemplo de GrMnoiso 1.

Caso 4. dos matrices elementos cada una de dos miembros diferentes de Groidnoiso.

Creo que hemos agotado todas las posibilidades. Pero tampoco nos interesa pulir este detalle, pues como vamos a ver en el punto siguiente, no es un tema relevante.

4.2 ¿ A que se reduce el problema de isomorfismo ?

a) Supongamos que nos dan dos matrices de GmisoX, que nos dan los generadores de este dígrafo o grupo, y lo que nos piden es una demostración (un certificado) de este hecho (que los dos vértices son de este dígrafo de Cayley). Ojo esto no es el problema de isomorfismo, en el que no te van a dar los  generadores ni te van a dar una pista sobre si las dos matrices son isomorfas o no. Es una variante del problema de isomorfismo en el Caso1.

En este caso la manera de resolver el problema es encontrar un camino en el dígrafo de Cayley de GmisoX que una a los dos elementos (a las dos matrices dadas como input del problema de isomorfismo). El camino es el certificado.

Concretando mas el método, cogemos una de las dos matrices que nos dan como input y empezamos a generar el dígrafo de Cayley aplicando los generadores y controlando si aparece o no la otra matriz dada como input. Si la promesa que nos han hecho es verdadera, tiene que aparecer en algún momento. Del árbol que se ha ido generando nos quedamos con el camino que une estos dos nodos y este es el certificado. 

Nota. Nótese que el problema de, dados los generadores de un dígrafo de Cayley ¿ en forma de permutaciones ?, encontrar el camino más corto es en general Pspace-complete. Esto no es relevante para el problema de isomorfismo pues: primero, no nos están pidiendo el camino más corto (no nos están pidiendo el certificado más corto), sino uno cualquiera de todos los posibles; segundo, en el problema de isomorfismo real, no nos dan los generadores. Cuando los tenemos, el problema se puede considerar resuelto. Fin de nota.   

Está claro que este método encontraría un isomorfismo siempre que las dos matrices del input fuesen isomorfas (por ejemplo en los casos 1 y 3 del punto anterior).

b) Ahora supongamos que nos dan dos matrices que nos confirman que no isomorfas, y nos dan dos conjuntos de generadores (¿¿¿que forma tienen los generadores ???) y nos dicen que cada uno de estos conjuntos de generadores genera el grupo del que se ha extraído cada uno de estos dos elementos, sin decirnos cual es de cual. De nuevo, nos piden una demostración de que no son isomorfas (un certificado de no isomorfismo). ¿ Como obtenemos este certificado ?. 

En este caso hay varias maneras. Una de ellas puede ser la siguiente: cogemos una matriz y uno de los conjuntos generadores y construimos el (dí)grafo de Cayley correspondiente. Como no son isomorfas, la otra no aparecerá. Ahora cogemos esa misma matriz y le aplicamos el otro conjunto de generadores. De nuevo como no son isomorfas, la otra no aparecerá. Los dos árboles son el certificado. Se  podría obtener exactamente lo mismo  escogiendo la otra matriz.

Podemos con la información de que se dispone determinar a que conjunto de generadores se corresponde cada matriz. Entiendo que no, para ello habría que generar los correspondientes grupos de automorfismos.

4.3 El problema de isomorfismo.  Sus dos vías de solución.  

En base a lo anterior está claro que si nos dan los generadores, hay métodos para resolver el problema. Pero en el problema de isomorfismo no es un dato que te den.

Por lo tanto si queremos recurrir a los métodos descritos en el punto anterior, no hay más remedio que resolver antes el problema de automorfismo, que te proporciona los generadores.

O esto o utilizar métodos que sólo utilicen la información que aparece en los elementos de los grupos, que te dan como input, es decir las matrices, eso si coniderándolos como grafos. Esto lo que intentan la otra clase de métodos, los así llamados de canonización.

5. Grupo de automorfismos o ¿grupo? de invariantes ¡¡ e ahí el dilema !!. 

5.1 Preliminares.

Segunda redacción (17 de marzo de 2017).

Cualquiera que haya leído con detenimiento todo lo anterior y que conozca cuales son los métodos utilizados para resolver el problema de isomorfismo de grafos casi desde sus inicios habrá caído en la cuenta de lo siguiente:

–los que trabajan con métodos, digamos, de teoría de grupos, lo que hacen es estudiar el grupo de automorfismos y diseñar métodos que encuentren lo más rápidamente posible el grupo de automorfismos de un grafo dado.

–los que trabajan con los métodos, digamos, de canonización, lo que hacen es estudiar el grupo de invariantes o de invarianza y diseñar métodos que demuestren que para todo grafo este grupo no existe (es igual a la identidad).

Vemos con más detalle esto en los dos puntos siguientes.

Pimera redacción. A continuación la primera redacción que hicimos de esta parte, en el momento de redactar la entrada, antes de reflexionar más sobre el tema, lo que nos llevó a la segunda redacción. Pensamos que es interesante dejar esta primera redacción.

Sobre estos dos métodos, sobre estas dos vías de solución que ya se han descubierto desde hace décadas y que se utilizan con éxito, en la teoría algunos y en la práctica otros hay múltiples preguntas. ¿ Por ejemplo es posible que puedan tener diferente complejidad ?. Así, a priori, sin tener más que un conocimiento superficial de los métodos de canonización ni tampoco muy profundo (aunque si lo conozco algo mejor) me sorprende que los métodos de canonización funcionen mejor (sólo en la práctica; en la teoría son mas eficientes los de automorfismo) que los de automorfismos. No sabría decir pq, pero me ha sorprendido conocer esto.

En el fondo en los dos casos se trata de extraer información de un mismo objeto, una matriz binaria nxn para grafos. En el caso de automorfismos lo que se intenta extraer está claro: un conjunto de generadores. En el caso de canonización, ¿ un invariante completo (y eficiente) ?. Fin primera redacción.

Ahora vamos a ver cuales son métodos de fuerza bruta en las dos vías. 

5.2. Fuerza bruta en el análisis del grupo de automorfismos. 

PDTE DESCRIPCION DE FUERZA BRUTA AUTOMORFISMOS.

Me da la impresión de que para evitar la fuerza bruta no queda más remedio que encontrar simetrías en una lista de ¿ ?. PDTE DESARROLLAR. Ya hemos hablado de métodos que evitan la fuerza bruta, gracias a los cuales se ha conseguido ir reduciendo la complejidad de este problema.

Nota. En este caso cabe preguntarse si no sería conveniente estudiar el comportamiento asíntotico de los grupos de automorfismos asociados a grafos. Es lo primero que me pregunté tras realizar todas estas reflexiones: ¿ por qué no estudiar este comportamiento ?. Igual los grupos de automorfismos de grafos son muy específicos, tienen propiedades muy específicas que no tienen otros y conocer las propiedades de la familia infinita puede ser de ayuda para encontrar los grupos de automorfismo de miembros de ella.

Pero el caso es que recordé haber re-leído (ya lo conocía) que los grafos son una de las estructuras universales (universal en en este contexto es una palabra técnica): todo grupo se puede construir como el grupo de automorfismos de un grafo. Por lo tanto, entiendo (y tengo que volver a mirar el tema para reconfirmarlo), que estudiar esto es equivalente a estudiar el comportamiento asíntotico…¡¡¡ de todos los grupos !!!

Extracto del artículo enlazado.

5 Abstract groups. 

If we consider groups as abstract algebraic objects rather than as concrete permutation groups, a clear-cut result is possible. Frucht [20] proved:

Theorem 5.1 Every group is the automorphism group of a graph. If the group is finite, the graph can be taken to be finite. Subsequently, Frucht [21] showed that every group is the automorphism group of a trivalent graph. This has inspired a large number of similar results. We call a class C of structures universal if every finite group is the automorphism group of a structure in C.

The combined results of Frucht, Sabidussi, Mendelsohn, Babai, Kantor, and others show that the following types of graph or other structures are universal: graphs of valency k for any fixed k > 2; bipartite graphs; strongly regular graphs; Hamiltonian graphs; k-connected graphs, for k > 0; k-chromatic graphs, for k > 1; switching
classes of graphs; lattices; projective planes (possibly infinite); Steiner triple systems; symmetric designs (BIBDs).

Hay un matiz importante: el teorema habla de grupos abstractos. Luego quizás no sea aplicable para grupos de permutaciones o de matrices….Igual no está todo perdido en este sentido. Hay que darle otra vuelta a este tema.

. Fin de nota.

5.3. Fuerza bruta en el análisis del grupo de invariantes. 

Diría que nadie piensa que, para este problema, el conjunto de invariantes pueda ser constante. Es decir que haya una lista de invariantes de tamaño digamos 100 (100 invariantes) que pueda servir para determinar si dos grafos son isomorfos, para todos los pares de grafos posibles. ¿ Quiere esto decir entonces que este problema no puede estar en P ?. No lo creo. Nadie piensa tampoco que para todo par de grafos el grupo de automorfismos puede ser constante, es decir el mismo para todos los grafos.

Como  podría ser el problema polinómico, con una lista de invariantes variable. Pensamos que se tienen que dar tres condiciones:

–primero, para todo grafo, la propia lista de invariantes tiene que poder generarse en tiempo polinómico en función del tamaño del input, del tamaño  del grafo. No la conoces de antemano (o solo algunos invariantes, aquellos que hayan servido para todos los grafos anteriores de menor tamaño).

–segundo, relacionado con lo anterior (pero no equivalente: podría ser el caso de que la  lista fuese polinómica pero necesitase un tiempo superpolinómico para ser generada). Para todo grafo, el número de invariantes, la cantidad de invariantes que aparezcan en la lista, tiene que ser polinómico en función del tamaño del input, del tamaño del grafo (digamos en función del número de vértices).

–tercero, cada invariante se tiene que poder computar en tiempo polinómico, en función del tamaño del input, del tamaño  del grafo.

Entonces el problema de isomorfismo sería polinómico si hubiese un método, un algoritmo, tal que dado un grafo 1 cualquiera como input, te permita encontrar una lista de invariantes (o de condiciones) que cumpla con estas tres condiciones y ¿ que no tenga solución (es decir que no haya ninguna transformación que cumpla esta lista de condiciones salvo quizás la identidad) ?. Si tienes una lista que cumpla con esto, y la aplicas a otro grafo, el grafo 2, y se encuentra algún valor diferente en la lista para algún invariante, entonces puedes concluir que los grafos son diferentes; pero si se encuentra que tienen los mismos valores para todos los invariantes, puedes concluir que el grafo 1 y el grafo 2 son isomorfos.

Por utilizar una metáfora: el método es como un programa lineal, que en principio tiene soluciones (en nuestro caso, las soluciones no son números sino transformaciones que cumplen con las restricciones) y al que vas añadiendo restricciones hasta que ya no tiene soluciones. La lista de invariantes es como la lista de restricciones. Entiendo que  hay muchas listas de restricciones diferentes que hagan que un programa lineal no tenga soluciones. Es posible que los mismo suceda con la lista de invariantes. Nos interesan aquellos de menor tamaño…

Pero no sabemos si este método polinómico de generación de invariantes existe. Podría ser el caso de que el mejor  método posible no fuese polinómico, sino cuasipolinómico, ¿ subexponencial o incluso exponencial?.

Hemos puesto interrogantes en «subexponencial o incluso exponencial» por un motivo muy concreto: ¿ que relación tienen la complejidad de encontrar el grupo de automorfismos con la complejidad de encontrar una lista de invariantes que cumpla con las condiciones indicadas ?. Tenemos una cota superior cuasi-polinómica para encontrar el grupo de automorfismos de cualquier grafo. ¿ Es posible que encontrar la lista de invariantes pueda tener una cota inferior superior a esta otra cota, por ejemplo una cota subexponencial ?  Ahora mismo no tengo ni idea. La intuición me dice que posiblemente no, que tienen que tener la misma cota. Pero de momento no puedo argumentarlo y por lo tanto la intuición podría estar equivocada.

Todo esto es muy complicado. Incluso solo explicar la idea que tengo en la cabeza lo es. No se si lo he conseguido.

6. Conclusiones. 

a) Dado un grafo este se puede modificar de diferentes maneras. Algunas modificaciones no suponen ni  reconexiones de arcos ni modificación en el número de elementos (vértices o arcos). Otras modificaciones consideran reconexiones de arcos de diferentes tipos y otras consideran modificación en el número de elementos (contracciones etc…). Las  modificaciones que no suponen reconexiones ni modifican el número de elementos llevan al estudio del grupo de automorfismos de un grafo. En esta entrada hemos explorado con cierto detalle las modificaciones del tipo reconexión de arcos más sencillas y estudiado su posible relación con el problema de isomorfismo. Hemos visto que con este tipo de reconexiones se pueden obtener grafos no isomorfos al inicial pero que conservan el valor de un invariante de grafos dado. Hemos visto que no está claro que, tal y como considerábamos al inicio, con un conjunto de estas reconexiones digamos conservativas del invariante se pueda formar un grupo que contenga a todos los grafos posibles no isomorfos al inicial pero que conserven el valor del invariante.

b) Ahora vamos a ver algunos problemas que, al igual que los problemas de isomorfismo, se pueden expresar como problemas de teoría de grupos y  que hemos estudiado con cierto detenimiento.

Si en el problema de factorización de enteros te dan como input el orden de un grupo (en general abeliano) y se trata de encontrar (el output que hay que aportar) es el orden de los factores. En el peor caso el orden tiene muy pocos factores, con lo que por fuerza bruta es complicado encontrarlos: among the b-bit numbers, the most difficult to factor in practice using existing algorithms are those that are products of two primes of similar size. Este problema está en NP intersect coNP y su mejor (la que mostramos a continuación es la de uno de los métodos, no se si es el más rápido), cota superior es de

y por lo tanto subexponencial. Aunque la versión más estudiada es la de grupos abelianos (seguramente cíclicos), también se estudia para otro tipo de grupos. este problema tiene un algoritmo cuántico polinómico.

Si en el problema del camino más corto en dígrafos de Cayley (minimum length generator sequence) te dan dos elementos de un grupo y un conjunto de generadores y tienes que encontrar el camino más corto entre los dos elementos. Este problema, que en el fondo es un problema de optimización es Pspace-completo, y como en el caso del problema de factorización, el peor caso son los (dí)grafos de Cayley 2-generados. Dicho de otra manera, ya los 2-generados son Pspace-completos. No necesitas más generadores. Desconozco la mejor cota temporal para este problema en versión sucinta, imagino que (por la clase en la que está) exponencial. Si te dan el (dí)grafo completo creo recordar que este problema está en NL (como mucho tiene la complejidad del problema de camino más corto en (dí)grafos generales).

En el problema de isomorfismo, en su definición más minimalista, te dan como input dos elementos en forma de matrices de nxn, tienes que encontrar los generadores de un grupo de automorfismos vinculado a estos dos  elementos. Versiones sucintas de este problema, con respecto a los elementos, es que te den los dos elementos (las dos matrices) en vez de en forma de matriz, en forma sucinta. Cuando esto sucede su complejidad está, lógicamente, a un nivel superior. Esto es lo que sucede en el problema de isomorfismo de grupos de permutaciones: en vez de darte los dos grupos cuyo isomorfismo hay que determinar, en forma de tabla de multiplicación (que sería el equivalente a la matriz del grafo) te dan los grupos en forma de conjuntos de generadores (que sería equivalente a que te den el grafo en representación sucinta; todavía no he conseguido averiguar de que tamaño son los conjuntos de generadores). Pero realmente en todos estos casos, lo más importante no es tanto la representación del input, sino el número mínimo de operaciones (¿ de que tipo?) que tengas que realizar para obtener los generadores del grupo de automorfismos. Este número de operaciones será el mismo independientemente de si utilizas representación normal o sucinta. Esto puede ser un poco confuso en los grupos de permutaciones: te dan dos grupos en forma de generadores, y tienes que encontrar otro generadores, en este caso no de los grupos, sino del grupo de automorfismos de estos, cosa que no es lo mismo. ¿ Es el peor caso también para este problema en representación normal el de grupos de automorfismos bigenerables ?. No está claro. En la literatura hay indicios de que puede ser el caso, pero también de todo lo contrario. Tiene sentido que así sea: si, en el caso positivo de isomorfismo, lo que tienes que buscar en primer lugar son los generadores de un grupo (del grupo de automorfismos), parece que tiene que ser más complicado si este tiene pocos generadores, y el mínimo salvo para grupos cíclicos (que son fáciles a estos efectos) puede ser 2 (en el caso del problema negativo, es decir el problema de no isomorfismo al parecer ocurre todo lo contrario, pero ahora no recuerdo, entiendo bien pq tiene que ser así).

c) Fenomenología. 

Ahora vamos a ver como se explica la fenomenología conocida del problema de isomorfismo todo lo que hemos estado comentando en los puntos anteriores.

–el caso aleatorio del problema de isomorfismo es sencillo. Esto es un dato que siempre se comenta. Si para construir los casos aleatorios solo se tienen en cuenta los invariantes más superficiales uno se pregunta como podría ser esto de otra manera.

—

—

—

P.s. Enlaces relacionados: 

–Grupos de automorfismod de grupos.

https://groupprops.subwiki.org/wiki/Automorphism_group_of_a_group.

Extractos.

–In general, for an elementary abelian group of order , the automorphism group is the general linear group. Sobre el grupo lineal general: https://en.wikipedia.org/wiki/General_linear_group

–For a finite cyclic group of order , the automorphism group is of order  where  denotes the Euler totient function. Further, the automorphism group is cyclic iff  is 2,4, a power of an odd prime, or twice a power of an odd prime. In particular, for a prime , the automorphism group of the cyclic group of order  is the cyclic group of order .

–For finite abelian group, no simple description.

–For the symmetric group: the same symmetric group if the degree is not 2 or 6. For degree 2, the trivial group. For degree 6 (i.e., symmetric group:S6), the group automorphism group of alternating group:A6.

—the symmetric group if the degree is at least 3 and not equal to 6. For degree 6 (i.e., alternating group:A6), the group automorphism group of alternating group:A6.

—