Plegamiento de Digrafos de Cayley.

En este post seguimos con el tema que nos ha ocupado en los dos últimos posts: ¿ podemos expresar los problemas en la PH cómo problemas de RH en digrafos de cayley bigenerados y los problemas en la PH, NP-completos y NP-intermedios cómo problemas de RH en Digrafos de Cayley bigenerados con la propiedad cycle-entangled ? Abrimos un nuevo post para no sobrecargar el anterior que ya está suficientemente confuso. En lo que sigue los términos reducción/plegamiento y extensión /desplegamiento son intercambiables.

De momento hemos demostrado que la  computación de la comprobación de que un determinado par de generadores tiene la propiedad cycle-entangled se puede hacer con  los recursos de Pspace y hemos mejorado algo el tiempo de esta computación, aunque todavia se tiene que intentar mejorar más. Analizando todo ésto hemos demostrado que  los ciclos con esta propiedad deben tener un número par de arcos y que el número de representantes (arcos) de un mismo IAS en un mismo ciclo puede ser par o impar.

Para que encajen todas las piezas del rompecabezas, aparte de hacer la operación de comprobación de que un par de generadores son cycle-entangled con recursos Pspace, tema que hemos estado analizando en el post anterior, tenemos que demostrar que la operación de reducción o plegamiento también se puede hacer con recursos en Pspace al menos en algunos casos, cosa más complicada.  Con respecto a esto úlimo en el post anterior hemos presentado un caso que, por servir cómo ejemplo de cómo realizar un plegamiento de digrafo y por ayudarnos a cerrar un tema que dejabamos abierto en la solicitud de patente (en la solicitud, deciamos que si bien la operación de reducción / extensión conservaba los vertices finales de los ciclos y el número de RH´s, es decir estos eran invariantes ante las operaciones dichas, el tema no estaba tan claro con respecto a los vertices finales de los path) vamos a analizar con más detalle en éste post.

El caso son los generadores:  1235674 y 2314765 y sus parámetros son: generan un grupo de orden 24; 1235674 es de orden 4 y no cycle-entangled; el otro generador es de orden 6 y su divisor es 3; tiene 4 IAS de tamaño 12 (IAS/2 = 6); este digrafo no conmutativo de 24 vertices es reducible  o se puede plegar en uno no conmutativo de 8 vertices, dónde en cada vertice están identificados 3 vertices del original. Se obtiene cómo reducido dos ciclos de 4 elementos unidos por 4 involuciones de tal manera que haya 4 IAS de 4 elementos. En el IAS de la identidad del reducido hay dos vértices finales posibles y por lo tanto sabemos que hay ciclos hamiltonianos. Sabemos también que la operación de reducción conserva tanto los vertices finales de los ciclos y el número de RH´s. El reducido tiene 4 RH. 3 de estos RH del reducido acaban en el vértice triplete (1237456-3127456-2317456) y uno en el vertice triplete (3124765-1234765-2314765). Pues bien precisamente, al desplegar el digrafo se comprueba que existen también 4 RH´s (invarianza de número de soluciones), que cada uno termina en los vertices 1237456, 3127456, 2317456 y 3124765. Esto claramente nos da una regla sobre cómo descubrir los vertices finales de los RH del digrafo desplegado cuando conocemos las soluciones en el plegado. Por ejemplo en el reducido 3124765 se identifica con 1234765 y 2314765. Sabemos que en este triplete solo terminan un RH y que al desplegarlo el ciclo es invariante. Podemos deducir que los otros dos no tendrán RH. En cuanto al otro triplete sabemos que terminan tres RH y que tiene que tener necesariamente un ciclo. Pero de aquí no podemos deducir necesariamente en los otros dos termina un RH: podrian terminar los tres en el vertice del ciclo. ¿ se deben distribuir ? Porqué ? Este tema y describir un método con recursos Pspace de plegamiento quedan pendientes. Continuará.

Actualización 8/10/2010.

Buscando generadores para PSL(3,2) he encontrado estas páginas o papers:

Una página web con muchos Digrafos de Cayley de grupos pequeños (hasta orden 32) representados en el plano y en el toro.

http://www.weddslist.com/groups/cayley.html

http://www.weddslist.com/groups/cayley-31/index.html

http://www.weddslist.com/groups/cayley-31/index.html

Una curiosa página sobre simetria:

http://www.m759.net/wordpress/?s=eightfold+symmetry

Papers:

http://www.ime.usp.br/~antoneli/public/grpnet2.pdf

http://www.math.vt.edu/people/brown/doc/PSL(2,7)_GL(3,2).pdf

http://people.brandeis.edu/~igusa/Math101b/PSL.pdf

http://wdjoyner.com/writing/expository/groups-sage3.pdf (en este paper aparecen generadores explicitos en representación por permutaciones para PSL(2,7), que cómo sabemos es isomorfo a GL(3,2), sobre un conjunto de cardinalidad 8. No sé si son generadores de grado mínimo. Son 12658734 y 61845237, dos ciclos de orden 3, IAS 14 y aunque son entangled, no pueden ser cycle entangled (ciclos impares). He puesto a prueba estos dos generadores en el programa que desarrollé para encontrar RH y ha tardado 2-3 minutos en encontrar el siguiente RH (vi=vertice inicial=identidad; vf=vertice final; el RH se debe leer de izquierda a derecha y de arriba hacia abajo):

{vi,{2,3,7,6,9,8,4,5},{2,3,8,9,5,4,7,6},{4,2,6,9,5,3,8,7},{3,4,7,9,5,2,6,8},{3,4,2,5,8,6,7,9},{3,4,6,8,9,7,2,5},{7,3,5,8,9,4,6,2},{7,3,4,9,2,6,5,8},{6,7,8,9,2,3,4,5},{3,6,5,9,2,7,8,4},{3,6,7,2,4,8,5,9},{3,6,8,4,9,5,7,2},{5,3,2,4,9,6,8,7},{6,5,7,4,9,3,2,8},{6,5,3,9,8,2,7,4},{2,6,4,9,8,5,3,7},{5,2,7,9,8,6,4,3},{5,2,6,8,3,4,7,9},{4,5,9,8,3,2,6,7},{2,4,7,8,3,5,9,6},{2,4,5,3,6,9,7,8},{2,4,9,6,8,7,5,3},{7,2,3,6,8,4,9,5},{4,7,5,6,8,2,3,9},{4,7,2,8,9,3,5,6},{4,7,3,9,6,5,2,8},{5,4,8,9,6,7,3,2},{5,4,7,6,2,3,8,9},{3,5,9,6,2,4,7,8},{3,5,4,2,8,7,9,6},{7,3,6,2,8,5,4,9},{5,7,9,2,8,3,6,4},{5,7,3,8,4,6,9,2},{6,5,2,8,4,7,3,9},{7,6,9,8,4,5,2,3},{7,6,5,4,3,2,9,8},{2,7,8,4,3,6,5,9},{2,7,6,3,9,5,8,4},{5,2,4,3,9,7,6,8},{7,5,8,3,9,2,4,6},{7,5,2,9,6,4,8,3},{7,5,4,6,3,8,2,9},{8,7,9,6,3,5,4,2},{5,8,2,6,3,7,9,4},{5,8,7,3,4,9,2,6},{5,8,9,4,6,2,7,3},{2,5,3,4,6,8,9,7},{2,5,8,6,7,9,3,4},{9,2,4,6,7,5,8,3},{5,9,3,6,7,2,4,8},{5,9,2,7,8,4,3,6},{5,9,4,8,6,3,2,7},{3,5,7,8,6,9,4,2},{9,3,2,8,6,5,7,4},{9,3,5,6,4,7,2,8},{9,3,7,4,8,2,5,6},{2,9,6,4,8,3,7,5},{2,9,3,8,5,7,6,4},{7,2,4,8,5,9,3,6},{7,2,9,5,6,3,4,8},{3,7,8,5,6,2,9,4},{3,7,2,6,4,9,8,5},{3,7,9,4,5,8,2,6},{8,3,6,4,5,7,9,2},{7,8,2,4,5,3,6,9},{7,8,3,5,9,6,2,4},{7,8,6,9,4,2,3,5},{2,7,5,9,4,8,6,3},{8,2,3,9,4,7,5,6},{8,2,7,4,6,5,3,9},{8,2,5,6,9,3,7,4},{3,8,4,6,9,2,5,7},{3,8,2,9,7,5,4,6},{5,3,6,9,7,8,2,4},{5,3,8,7,4,2,6,9},{2,5,9,7,4,3,8,6},{3,2,6,7,4,5,9,8},{3,2,5,4,8,9,6,7},{3,2,9,8,7,6,5,4},{6,3,4,8,7,2,9,5},{2,6,5,8,7,3,4,9},{2,6,3,7,9,4,5,8},{4,2,8,7,9,6,3,5},{6,4,5,7,9,2,8,3},{6,4,2,9,3,8,5,7},{6,4,8,3,7,5,2,9},{5,6,9,3,7,4,8,2},{4,5,2,3,7,6,9,8},{4,5,6,7,8,9,2,3},{9,4,3,7,8,5,6,2},{9,4,5,8,2,6,3,7},{6,9,7,8,2,4,5,3},{6,9,4,2,3,5,7,8},{6,9,5,3,8,7,4,2},{7,6,2,3,8,9,5,4},{9,7,4,3,8,6,2,5},{9,7,6,8,5,2,4,3},{9,7,2,5,3,4,6,8},{4,9,8,5,3,7,2,6},{7,4,6,5,3,9,8,2},{7,4,9,3,2,8,6,5},{8,7,5,3,2,4,9,6},{8,7,4,2,6,9,5,3},{9,8,3,2,6,7,4,5},{7,9,5,2,6,8,3,4},{7,9,8,6,4,3,5,2},{7,9,3,4,2,5,8,6},{5,7,6,4,2,9,3,8},{9,5,8,4,2,7,6,3},{9,5,7,2,3,6,8,4},{9,5,6,3,4,8,7,2},{8,9,2,3,4,5,6,7},{8,9,5,4,7,6,2,3},{8,9,6,7,3,2,5,4},{2,8,4,7,3,9,6,5},{9,2,5,7,3,8,4,6},{9,2,8,3,6,4,5,7},{4,9,7,3,6,2,8,5},{4,9,2,6,5,8,7,3},{8,4,3,6,5,9,2,7},{9,8,7,6,5,4,3,2},{9,8,4,5,2,3,7,6},{3,9,6,5,2,8,4,7},{8,3,7,5,2,9,6,4},{8,3,9,2,4,6,7,5},{6,8,5,2,4,3,9,7},{6,8,3,4,7,9,5,2},{9,6,2,4,7,8,3,5},{9,6,8,7,5,3,2,4},{9,6,3,5,4,2,8,7},{2,9,7,5,4,6,3,8},{6,2,8,5,4,9,7,3},{6,2,9,4,3,7,8,5},{6,2,7,3,5,8,9,4},{8,6,4,3,5,2,7,9},{2,8,9,3,5,6,4,7},{2,8,6,5,7,4,9,3},{4,2,3,5,7,8,6,9},{8,4,9,5,7,2,3,6},{8,4,2,7,6,3,9,5},{3,8,5,7,6,4,2,9},{4,3,9,7,6,8,5,2},{4,3,8,6,2,5,9,7},{4,3,5,2,7,9,8,6},{9,4,6,2,7,3,5,8},{3,9,8,2,7,4,6,5},{3,9,4,7,5,6,8,2},{6,3,2,7,5,9,4,8},{6,3,9,5,8,4,2,7},{4,6,7,5,8,3,9,2},{4,6,3,8,2,9,7,5},{4,6,9,2,5,7,3,8},{7,4,8,2,5,6,9,3},{6,7,3,2,5,4,8,9},{6,7,4,5,9,8,3,2},{8,6,2,5,9,7,4,3},{8,6,7,9,3,4,2,5},{4,8,5,9,3,6,7,2},{4,8,6,3,2,7,5,9},{4,8,7,2,9,5,6,3},{5,4,3,2,9,8,7,6},{8,5,6,2,9,4,3,7},{8,5,4,9,7,3,6,2},{8,5,3,7,2,6,4,9},{6,8,9,7,2,5,3,4},{5,6,4,7,2,8,9,3},vf}

Teniendo todas las permutaciones, estoy generando pares no isomorfos para ver si en general tienen la propiedad cycle-entangled o no. Aunque asíntoticamente todos los pares de permutaciones elegidos aleatoriamente de un grupo finito simple el grupo, para grupos pequeños no hay tanta suerte. Según ésta página web http://math.ucr.edu/home/baez/week272.html la probabilidad de generar PSL (2,7) con un par aleatorio es de 0,679, que no está mal. Los que estoy probando de momento (unos 11), o son de ciclos con número impar de arcos, o no son cycle-entangled. En teoria en grado 8 y que dividan 168, es posible encontrar ciclos de 4(42),6(28),8(21) y12(14). De momento sólo he encontrado permutaciones de orden 4 o impares.

Un par de programas para trabajar con grupos:

http://sage1-math.univ-lyon1.fr/media/sage/docs_files/en/reference/sage/groups/perm_gps/permgroup.html, SAGE.

http://www-gap.mcs.st-and.ac.uk/Manuals/doc/htm/ref/CHAP048.htm, GAP.

Y una página web clave: el Atlas de grupos finitos.

http://brauer.maths.qmul.ac.uk/Atlas/v3/. Desde esta página se puede acceder al apartado de grupos lineales (linear groups), y dentro de estos la primera columna es la que nos interesa. La notación es diferente, pero de wikipedia: “The projective special linear groups PSL(n,Fq) for a finite field Fq are often written as PSL(n,q) or Ln(q)”.  Una vez dentro de cada grupo podemos ver mucha información sobre el grupo, por ejemplo si entramos en L4(2) = PSL(4,2) en  http://brauer.maths.qmul.ac.uk/Atlas/v3/alt/A8/ vemos que este grupo tiene ya 20160 elementos (es isomorfo a A8). Podemos ver la representación de grupos por permutaciones o matrices en las tablas que aparecen debajo. Por ejemplo presionando sobre details entramos en esta página http://brauer.maths.qmul.ac.uk/Atlas/v3/permrep/A8G1-p8B0 y dándole a la opción Magma entramos en esta otra: http://brauer.maths.qmul.ac.uk/Atlas/alt/A8/mag/A8G1-p8B0.M y obtenemos  lo que buscábamos. En esta página podemos ver que el grupo que estamos estudiando ahora PSL(3,2) tiene representaciones en forma permutaciones de grado 7,8, 14,21,24,28,42,56,84 y 168. En fin, esto es lo que estabamos buscando.

Actualización 11/12/2010:

He estado analizando el digrafo conmutativo que en un post posterior he puesto cómo ejemplo de digrafo de grado 9 que genera un digrafo de 24 vertices no isomorfo a ningún otro digrafo de grado inferior. Es decir el que tiene los siguientes parámetros: identidad 123456789, generador 123456798 de orden 2 y generador 2 231567489 de orden 12. Es un producto directo de C12xC2 y se puede plegar en uno de C2xC2. En el digrafo plegado se ve que hay ciclos hamiltonianos, sin embargo este digrafo, con el plegamiento que he realizado parece no captar toda la complejidad del desplegado. No parece que se conserven el numero de RH, pues en el plegado solo aparecen 2 y en el desplegado hay 7 y no se refleja una asimetria que existe en el desplegado: todos los vertices que se identifican o pliegan con un mismo vertice final ciclo, tienen path, y todos los que pliegan o se identifican con el otro vertice final ciclo, no tienen path. El caso es que las propiedades de los digrafos conmutativos y de los no conmutativos son algo diferentes y quizás el invariante “numero de RH” no se conserve en los conmutativos, quizás tenga que revisar este tema en los no-conmutativos o quizás haya que incorporar alguna información al plegado de la que se pueda deducir esta asimetria y el número de RH. Recordar también que el objeto de la solicitud de patente son los no-conmutativos.

Una respuesta to “Plegamiento de Digrafos de Cayley.”

  1. yiasld@gmail.com Says:

    It¡¯s an remarkable article in support of all the web visitors; they will obtain advantage from it I am sure.
    A new plum http://www.vibesconnect.com/mandelete13/blog/A-plum-maid-matron-of-honour-g,324831

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

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

Logo de WordPress.com

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

Imagen de Twitter

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

Foto de Facebook

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

Google+ photo

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

Conectando a %s


A %d blogueros les gusta esto: