Complejidad computacional & Algoritmica. Cuando el orden del IAS queda fijo.

(Entrada en construcción. Puede contener errores).

1. En esta entrada exploro el interrogante que planteábamos en una entrada anterior (y que reconozco me tiene “obsesionado”):

¿ Puede haber infinitos casos con las siguientes propiedades:

–grado de la  permutación n y orden n! o n!/2.

–caso smooth.

–|IAS|=2 ?

Realmente a veces me asaltan dudas incluso en el caso general sin restricciones: IAS y circunferencia pudiendo alcanzar la cota máxima (es decir Landau). ¿ Por qué esta duda ? Creo que el problema es que todavía mantengo mentalmente la imagen (errónea) que todos estos dígrafos (de Cayley Bigenerados y smooth) se pueden empotrar de manera planar en una esfera en un toro.

Sin embargo, estando acotados estos dos parámetros (orden del IAS y orden o tamaño de la circunferencia) por la cota de Landau   se puede ver que el máximo de vertices que se pueden empotrar en estas superficies (concretamente en el toro que acepta más vértices) es más o menos e^4*Raiz Cuadrada[n*log n] = t, valor que muy pronto se queda detrás de n! o de n!/2. 

Claramente, que un dígrafo sea smooth en el entorno de la identidad (y por lo tanto en el entorno de cualquier otro vértice) no  quiere decir que sea empotrable en la esfera o toro. Pero imagino que si deben serlo en multitoros.  Si cada toro del multitoro tiene más  o menos la cantidad indicada, t, cuantos toros tiene que tener la superficie (expresados cómo función del grado n de la permutación) para que t*nº toros = n!. Claramente nº de toros = n!/t. Sería deseable poder simplificar n!/t…

Una pregunta que surge inmediatamente en este contexto es si hay alguna cota (tendría que ser obviamente la de Landau) que limite de nuevo el número de estos componentes de tercer nivel (primer nivel sería el IAS, segundo nivel sería la circunferencia y quizás haya un tercer nivel que agrupe de manera natural estos componentes, esferas o toros y así sucesivamente aparecerían otros niveles, ya que cada nivel sólo incrementa la constante que antecede a la Raíz cuadrada del exponente).

Por cierto, existe un procedimiento intrínseco muy sencillo para determinar si el dígrafo que estamos considerando, en el segundo nivel, se descompone en esferas o en toros: construyamos la circunferencia de la identidad y llamemos X al conjunto de vértices (permutaciones) incluidos en esta circunferencia. Construyamos alguna de las otras posibles circunferencias que salen del IAS de la identidad (esto siempre es posible incluso cuando el |IAS| = 2) y llamemos Y al conjunto de permutaciones que pertenecen a esta segunda circunferencia. Si la intersección entre X e Y es nula (excepto obviamente aquellas permutaciones del IAS de la identidad) entonces hablamos de un toro. Si no es nula, y entonces en general compartirán permutaciones del IAS opuesto al de la identidad (lo que en otras entradas hemos llamado el IAS antípoda). Digo en general dado que  para casos pequeños la primera circunferencia del IAS, X, puede intersecarse ella mismas y además intersecar con la Y en la antípoda. Un ejemplo, el dígrafo de S5, con generadores 23154 y 12453. Entiendo que este tipo de fenómenos deben de desaparecer asintóticamente. Incluso pienso que la descomposición en esferas también debe desaparecer a partir de un cierto tamaño y sólo quedarán toros (multitoros).

Para que se entienda de que hablamos, un ejemplo gráfico. En la imagen siguiente un dígrafo de S5 (120 vértices), parámetros g1= 4, g2 = 5, IAS = 2 y circunferencia (la circunferencia se obtiene al comparar la identidad con la permutación de enmedio del segundo IAS y si el IAS es par se multiplica el número obtenido por 2; en este caso es 3×2 = 6, es decir la circunferencia consta de 6 IAS).

Caley Toro

La hoja se puede plegar pegando por ejemplo los números que están cómo en columnas en los dos lados (de arriba abajo, 2,3,4,5,6,7) y en filas abajo y arriba y se obtiene un toro. Pero ojo el empotrado no es planar en un sólo toro dado que hay algunos cruces, para los cuales se necesitarían más asas. Pero si nos olvidamos de estos cruces (en cuyo caso obtenemos lo que se llama un almost embedding) el dígrafo  se presenta cómo en una sola pieza, en un sólo toro. Cómo se ve, el entorno de la identidad es smooth. Y cómo se ve la Cota de Landau límita el volumen de cada componente (toro), ya que limita superiormente tanto el tamaño del IAS cómo el de la circunferencia. Si suponemos que el IAS de un caso iguala a la cota de Landau (no tengo claro si la Función de Landau lo que establece es una igualdad o una cota superior al máximo orden de una permutación; en lo que sigue suponemos que puede igualarla) entonces tendrá 2*e^Raiz[nlogn] permutaciones. Si la circunferencia iguala también la cota de Landau (idem) entonces esta contiene 2^2*e^2*Raiz[nlogn] permutaciones.  Si suponemos que el dígrafo está empotrado planarmente en el toro y multiplicamos la primera circunferencia por la segunda obtenemos 2^4*e^4*Raiz[n logn]. Si nos olvidamos de la constante, obtenemos la fórmula que hemos dado antes (obviamente sólo una aproximación).  Este caso lo representé la última vez que me interesé en este tema (diciembre 2011) y todavía no tengo 100% claro cuantos toros necesita para ser empotrado de manera planar.

A continuación otro ejemplo que estoy representando ahora. Este es de S6 (y por lo tanto tiene 720 vértices; cómo puede imaginar el lector, representar esto manualmente es un trabajo completamente ingrato, casi imposible, y sujeto a errores; yo he llegado a representar manualmente, hace años, casos completos de 120, que ya es una tortura, nunca de 720). Sus parámetros son g1 = 6; g2=4; IAS = 3 (y contiene el doble de permutaciones, 6) y la circunferencia = 6 (en este caso cómo el IAS es impar la circunferencia se obtiene comparando  la identidad con la permutación de enmedio del IAS de la identidad  y sin multplicar por 2).  Cómo se ve se trata de un toro también, dado que las dos circunferencias que salen del IAS de la identidad no intersecan esta en otros IAS que no sean los de la identidad. Sin embargo aquí la cosa se complica  con respecto a la planaridad dado que estas dos circunferencias tampoco comparten ninguna permutación (lo cual me ha sorprendido) y se tienen por lo tanto que cruzar. Obviamente de cada IAS saldrán dos circunferencias que se cruzarán también. Imagino que este caso es smooth también. Finalmente señalar que si este caso se pudiese descomponer en “esferas” entonces  los IAS laterales tendrían que pasar por el cuarto IAS (es decir tendrían permutaciones comunes con el cuarto IAS). Esto obviamente limita el crecimiento. Por ello entiendo que sólo pueden descompuestos en “esferas” aquellos con un IAS grandes en relación al orden del grupo. Esto podría darse por ejemplo cuando permutaciones de grado n generen grupos S(n-m).

Esto nos lleva a la reflexión de que además ¿ la esfera requiere una proporcionalidad entre el tamaño del IAS y el tamaño de la circunferencia?. Y llevando al extremo esta reflexión ¿ es posible que la relación entre los tamaños de estos dos parámetros (IAS y circunferencia) sea importante ? (lo que sigue no es más que una hipótesis que debe de ser comprobada.):

–cuando el tamaño de la circunferencia es mayor que el tamaño del IAS entonces obtenemos descomposición en toros;

–cuando son  ¿iguales? obtendríamos descomposición en esferas. No es “exactamente iguales”. Por ejemplo el caso de S5 de generadores 23154 y 21534 tiene IAS = 3 (y por lo tanto el IAS  contiene 6 permutaciones) pero la circunferencia es 4. Tema a estudiar, aunque no parece que tenga que haber ninguna relación entre IAS y circunferencia para obtener esferas.

–y cuando el tamaño del IAS es mayor que el de la circunferencia obtendríamos casos entangled, cycle entangled (ver patente para las definiciones). No  necesariamente. Sólo cuando el IAS tiene un tamaño considerable en relación con el número de vértices.

Visto lo visto parece claro que se debe de rechazar esta hipótesis, al menos tal y cómo está formulada.

Caley Toro S6

De todos los casos de S6 y grado de la permutación = 6, en total 84 casos, sólo hay dos con IAS = 2 y 4 con IAS = 3. Para S5 y grado 5, de 31 casos, hay 4 de IAS = 2 y 4 de IAS = 3.

La pregunta que planteamos al principio es si a partir de un cierto n el número de casos para Sn y grado n de IAS = 2 será igual a cero y si a medida que n crece, el IAS mínimo crece también (y por lo tanto habría un momento en el que tampoco  podría haber IAS de tamaño 3, luego de tamaño 4 etc…).

Y la otra pregunta es si hay más niveles acotados por la Cota de Landau. ¿ Cuales son los siguientes niveles ? No se si a esto se le puede llamar nivel, pero otro parámetro limitado por la Cota de Landau es el orden de los generadores. En el último caso presentado de 720 vértices uno es de orden 4 y el otro de orden 6. Cómo cuando se genera el ciclo 6 de la identidad, varias permutaciones quedan saturadas con el primer toro pero otras del ciclo (por ejemplo la permutación 456123 en este caso) queda libre y de aquí saldrá otro toro pensamos que “disjunto” con respecto al que aparece en la figura. Cuando el orden de este generador sea la Cota de Landau habrá e^Raíz[nlogn] permutaciones libres. De cada una de estas, en principio saldría un toro. Pero de nuevo esto sólo incrementará la constante que antecede a la Raíz Cuadrada en el exponente en unas unidades. Entiendo que se debe de multiplicar por el número de ciclos de este generador que contenga el caso.

2.  En diciembre de 2011 ya  publicamos una entrada con un contenido similar al de la presente entrada titulada Inmersiones de Grafos (de Cayley) en Superficies. Aunque densa, creo que es bastante completa y recomendable si te interesan estos temas. En ella ya comentábamos algo que creo que es necesario reiterar en esta: inmersiones y hamiltonicidad son propiedades ortogonales.

En lo que sigue resumo lo más relevante de esa entrada para el contenido de esta. Sabemos por ejemplo que el genus de S5 es 4. Incluso se sabe que el genus de Sn es n!/168 + 1 para n>167. Ver también aquí. Para todo esto parecen relevantes los grupos de Hurwitz.

De nuevo me ha surgido la duda, que ya planteábamos en esa entrada sobre la complejidad computacional de determinar el genus / género de un Dígrafo de Cayley (bigenerado o de grado superior). Es decir, por ejemplo, si te dan dos generadores, 23154 y 21534, si sería polínomico con respecto al grado de los generadores determinar el género del dígrafo que generan estas dos permutaciones; o cual sería la complejidad computacional si te el input es el dígrafo completo. En Wikipedia comentan (esto ya lo citábamos en la anterior entrada) que:

At the same time, the graph genus problem is fixed-parameter tractable, i.e., polynomial time algorithms are known to check whether a graph can be embedded into a surface of a given fixed genus as well as to find the embedding.

Y en este paper comentan:

The Graph Minor Theorem has the consequence that for each fi xed surface we can decide graph embedability by employing finitely many minor tests. Tests de tiempo polinómico, añado yo. 

Es decir por ejemplo si fijamos la superficie cómo una esfera (o un plano), se puede determinar en tiempo polínomico si  cualquier grafo dado es plano o no. Entonces,  aquí el input es el grafo y una superficie de un género dado, y se trata de determinar si el primero es empotrable en la segunda. Para Grafos de Cayley, si nos ceñimos a Sn o An, conocemos la cota inferior para el género de todos los Dígrafos de Cayley de un n dado (la señalada anteriormente). Pero para el dígrafo dado el procedimiento anterior implicaría que empezando por esa cota inferior de (n!/168)+1, deberíamos rechazar uno a uno todos los géneros superiores hasta llegar a la cota superior (¿ cúal es ?). A priori no se debe descartar que en el peor caso haya un número exponencial de géneros que descartar hasta encontrar el correcto.

¡ Ojo ! el t del que hablamos aquí no es equivalente al genus de un grupo. T se puede definir para cualquier Grafo de Cayley pero el genus de un grupo se obtiene del Grafo de Cayley con el mínimo genus para el grupo dado.

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: