¿Existe alguna forma de etiquetar canónicamente los grupos de permutaciones?

Question

Cuando se trabaja con un gran número de grafos, una rutina de etiquetado canónico es esencial ya que, tras el coste inicial de etiquetar canónicamente cada grafo, permite sustituir las comprobaciones de isomorfismo por comprobaciones de identidad.

Actualmente estoy trabajando con un gran número de grupos de permutación transitiva; el grado es pequeño (40ish), pero el tamaño del grupo puede ser grande, y mis programas están engomando debido a tener que realizar un gran número de - no exactamente isomorfismo - pero conjugación controles. (Tengo que comprobar cada par de grupos para ver si son conjugados en el grupo simétrico).

Este proceso sería considerablemente más fácil si hubiera una forma conocida de encontrar un conjugado canónico de los grupos de permutación entrantes...

Answer 1

Una forma rápida de obtener conjugados canónicos de grupos de permutaciones sería de pero tal vez sea demasiado optimista. En lugar de intentar seguir ese camino, en su situación yo intentaría reducir el número de pares de grupos para ser probado para conjugacy -- y mi conjetura es en la práctica se puede obtener una reducción bastante grande. Concretamente, yo para cada uno de los grupos invariantes como el siguiente:

• orden de grupo,

• primitividad / grado de transitividad,

• número, tamaños, órdenes de representantes y estructuras de ciclos de representantes de clases de conjugación.

El tiempo necesario para calcular estos invariantes ya no es cuadrático, sino lineal en el número de grupos. Por último, sólo hay que probar los pares de grupos en los que coinciden todos los invariantes.

Para dar una idea aproximada de lo buenos que son los invariantes mencionados a la hora de separar grupos no conjugados: los invariantes distinguen todos los grupos transitivos no conjugados no conjugados de grado inferior a $12$ y entre los $301$ no conjugado grupos de permutaciones transitivas de grado $12$ sólo hay $2$ pares de grupos para los que los invariantes coinciden.

Answer 2

Babai, Codenotti y Qiao (ICALP 2012 de Página de Babai también en La tesis de Codenotti ) muestran cómo probar el isomorfismo permutacional (=conjugación - pero ésta podría ser otra buena frase con la que buscar) de grupos de permutación en un tiempo que es polinomial en el orden de los grupos y simplemente exponencial ( $c^n$ para fijo $c$ ) en el tamaño del dominio de permutación. Desde un punto de vista teórico, creo que es el más conocido.

En el caso transitivo, el tiempo de ejecución sigue siendo simplemente exponencial en el grado pero sólo lineal en el orden, y en esta cantidad de tiempo pueden de hecho lista todos los isomorfismos permutacionales. Enumerar los isomorfismos permutacionales permite elegir un etiquetado canónico por, por ejemplo, orden lexicográfico. (Y $|G|2^{40}$ es mucho mejor que el límite ingenuo de $|G|40!$ : $2^{40} \approx 10^{12}$ mientras que $40! \approx 10^{48}$ .)

Ahora bien, los límites teóricos de los algoritmos pueden no decir nada sobre la eficiencia en la práctica. (Dependiendo de lo grandes que sean sus grupos transitivos, incluso el factor lineal de $|G|$ puede ser demasiado para usted). Al menos es razonable pensar que su algoritmo no sólo es teóricamente más eficiente, sino también más eficiente en la práctica que los algoritmos ingenuos. Y, por supuesto, uno siempre puede esperar que funcione para sus instancias de todos modos, o tal vez con algunas heurísticas adicionales.

Answer 3

Éste parece ser uno de los mayores agujeros en el arsenal del isomorfismo práctico. Se me ocurren varias posibilidades no triviales, pero su eficacia depende mucho de una cuestión más básica. Definir (y calcular eficientemente) un orden total en grupos de permutación finitos etiquetados. Así, para dos grupos de permutaciones cualesquiera $G_1,G_2$ dados por generadores de permutaciones, determinar si $G_1\lt G_2$ , $G_1=G_2$ o $G_1\gt G_2$ donde $G_1=G_2$ si son exactamente iguales (no sólo isomorfas) y el orden obedece a la ley de transitividad. Esto es posible en principio: calcular los grupos completos y compararlos lexicográficamente. Pero, naturalmente, no queremos calcular los grupos enteros.

Answer 4

En GAP, para grupos de permutación transitiva de grado como máximo 30 se puede utilizar TransitiveIdentification(G) del paquete TransGrp por Alexander Hulpke. Da el índice del grupo de permutaciones (¡único!) de la biblioteca que es conjugado con el grupo de permutaciones dado y, al parecer, es bastante rápido. Véase la sección 13 de

Hulpke, Alexander , Construcción de grupos de permutaciones transitivas. J. Symb. Comput. 39, nº 1, 1-30 (2005). ZBL1131.20003 MR2168238 .