Algoritmica y complejidad computacional. Resumen investigaciones recientes: los casos entangled 1/2.

Actualización 20 de marzo 2016. Ya tengo clara conceptualemente una definición de twisted y smooth en la  que para determinar si un caso es smooth o twisted se utiliza tanto el concepto de entorno inmediato de la  identidad (tal y como está definido en la patente) como el concepto de circunferencia. Tengo que hacer una serie de comprobaciones para determinar si esta definición es válida. Cuando realice estas comprobaciones, que llevarán su tiempo haré una entrada al respecto.

Es  más, cada vez tengo más claro que con un argumento numérico (que implica hacer varios cálculos con los 5 principales parámetros: nº de vértices, orden del IAS, orden de los dos generadores, orden de la circunferencia), debe de ser posible comprobar (más rápidamente que construyendo el entorno de la identidad) si un caso será smooth o no. Ahora mismo me interesa conocer que pasará asintoticamente con el caso típico, es decir aquel que saldrá en una elección aleatoria.

Para ello se debe de utilizar: 

–el método “numérico” que acabamos de comentar (que seguramente ya adelantamos en anteriores entradas de hace años, pero que ahora empiezo a tener totalmente claro) y que está en construcción. Un  ejemplo es el caso de S5, identidad 23456 y generadores 34526 y 23564. Tiene 120 vértices, 30 IASES, el entorno de la identidad tiene 12 IASES y la circunferencia 10. Si no hubiese repeticiones (si no fuese twisted) nos saldrían más de 120 permutaciones. En otros casos, el nº de IASES del entorno de la identidad y de la circunferencia será una fracción mínima del total de IASES y pasa lo contrario: si hubiese repeticiones, no llegaríamos al número deseado (de Sn o An). Así a ojo de buen cubero, el método ya se puede utilizar y lo complicado es hacerlo preciso.  Realmente hay que encontrar una fórmula que nos permita determinar con exactitud o al menos acotar, dados los parámetros, cuantas permutaciones diferentes contendrá el entorno de la identidad. Esto ya es posible para la circunferencia (asumiendo que no tenga repeticiones, que las puede tener; sirva por lo tanto como cota superior).    

–el resultado de Erdos-Turan.

–la aplicación del resultado de Erdos-Turan para determinar el orden del IAS típico, según hemos comentado en anteriores entradas. Por cierto acabo de comprobar que este resultado ya se había demostrado en 2010

¡¡ por uno mismo !! y utilizando exactamente el mismo argumentos, es más casi las misma palabras. Ya decíamos en la entrada de hace poco, cuando redescubrimos esta demostración que a medida que iba escribiendo, lo que escribía tenía un aroma familiar…Las entradas en las que hablaba de todo esto son de 2010 y se titulaban Caso Medio I, II y III.   En esas mismas entradas ya concluía que asintoticamente el caso típico sería smooth. También afirmaba con total seguridad que la circunferencia típica también tendría el orden típico, pero esto sigo sin tenerlo nada claro ahora mismo.  

En fin según lo explicado, conociendo los parámetros del caso típico, si pudiésemos hacer preciso el método, me refiero a obtener una fórmula o una cota de las permutaciones del entorno de la identidad dados los valores de los parámetros, podríamos determinar con exactitud o con una buena aproximación si el entorno del caso típico se queda corto o no. Esto para quien tenga dudas, claro…

También tengo clara la definición más clara e inambigua posible de entorno de la identidad.  

Fin de actualización. 

He preparado el siguiente resumen de las investigaciones que hemos ido publicando (utilizando la base de datos de Ruskey y Effler para S6) en los últimos meses en este blog, para enviárselo a mi agente de cara a la entrevista que tendrá en breve con el examinador.

1.Definiciones.

Recordamos brevemente algunas definiciones.

Caso = par de permutaciones de igual grado que genera Sn.

Caso potencialmente difícil = caso que puede no tener recorridos hamiltonianos en alguno de los vértices finales posibles o caso que puede tener recorridos hamiltonianos en todos los vértices finales posibles pero que  encontrarlos pueda ser complicado.

Entangled = son aquellos en los que la intersección entre el IAS y el DAS no  es vacía.

2-Entangled = son aquellos casos que solo son entangled por ser uno de los dos generadores de orden 2. El IAS y el DAS no tienen otra permutación en común que la de orden 2.

Entangled 1/2 = son aquellos que son entangled en la permutación que se encuentra en medio del IAS o DAS, aquella que deja entre la identidad y ella misma el mismo numero de permutaciones a un lado y otro.

2 Entangled 1/2 = aquellas en las que se dan las dos propiedades anteriores.

Cuando hablamos de un caso entangled sin más nos referiremos a aquellos casos en los que solo sean entangled sin ser 2-entangled ni entangled 1/2.   Es decir ninguno de los generadores es de orden 2 y el IAS o DAS tienen una o más permutaciones en común pero no aquella que se encuentra en la mitad del IAS  (o DAS).

2. Resultados (nos limitamos a S6):

2.1. Algunas estadísticas iniciales.

Ruskey y Effler encontraron 84 casos de Digrafos de Cayley Bigenerados no isomorfos de S6, es decir de orden 720 y grado de la permutación 6.

De estos:

–al  menos 52 son no entangled (pero podrían ser twisted o smooth). Digo al menos porque cuando hice la investigación a los que se podía aplicar el teorema de Rankin no comprobé si  eran entangled o no, ya que no  iban a tener ciclos hamiltonianos independientemente de si eran entangled o no.

–los de tipo Rankin son 20, que por lo tanto tienen IAS impar.

–quedan 12, que son entangled con IAS par, cuyas propiedades analizaremos en un siguiente punto.

La mayoría de estos de grado 6 tienen los parámetros que son de esperar según lo que hemos publicado en las últimas entradas del resultado de Erdos-Turan y su aplicación adeterminar que IAS tendrá el par típico de Sn seleccionado al azar. Es decir los dos generadores tienen orden 4, 5 o 6 y lo  mismo el IAS. La mayoria de los que son de tipo Rankin tienen IAS de orden 5.

2.2 Casos de S6, de cualquier grado, entangled con ciclos hamiltonianos según la investigación de Ruskey y Effler.

Según nuestras investigaciones un caso con propiedad entangled es potencialmente difícil y era sorprendente que Ruskey y Effler hubiesen podido encontrar recorridos hamiltonianos en estos casos. Ya en la patente señalábamos que había casos entangled fáciles e interesaba poder distinguir por qué algunos entangled son fáciles y otros no.  Luego veremos como identificar mejor los difíciles.

Hay 34 de este tipo (12 de grado 6 y 22 de grado 8; los 12 de grado 6 son aquellos a los que nos hemos referido antes). La conclusión principal es que todos son o bien sólo 2-entangled o sólo entangled.

Es decir ninguno  de ellos son entangled 1/2, tengan un generador de orden 2 o no. Quedese el lector con este dato. 

2.3 Casos que Ruskey y Effler encontraron que no tenían ciclos hamiltonianos, no siendo del tipo Rankin.

Desde el punto de vista algorítmico el pero caso son aquellos que no tienen ciclos hamiltonianos, o si lo que se busca son recorridos hamiltonianos (es decir ciclos o caminos) los casos que  no tienen recorridos hamiltonianos en ninguno de los vértices finales posibles. Es sorprendente que identificasen estos casos con los medios y conocimiento de que disponían.

Hay cinco casos de este tipo que se distribuyen como  sigue:

–2 son cycle-entangled. Por los resultados de la patente ya sabemos que estos pueden no tener ciclos hamiltonianos.

–3 son entangled 1/2.   Quédese el lector con este dato.

2.4. Casos  de resultado desconocido o unknown en la investigación de Ruskey y Effler.

Estos casos son muy interesantes: tras dos años de búsqueda utilizando potentes ordenadores, los dos investigadores tuvieron que abandonar la búsqueda pues no pudieron determinar si tenían ciclos hamiltonianos o no. Ahora vamos a ver que hicieron bien.

Estos son 29 casos que se distribuyen como sigue:

–18 son cycle-entangled (y por lo tanto es de esperar que no tengan ciclos hamiltonianos si se dan las condiciones (ver pasos 5 y 6 de la solicitud de patente).

–11 son entangled 1/2.

Las conclusiones son claras: los casos que pueden dar más complicaciones son o bien entangled 1/2 o bien cycle-entangled. Es más, se puede conjeturar sin temor a equivocarse que todos los casos cycle-entangled son entangled 1/2.

Pero ojo que sean entangled 1/2 no  significa que necesariamente no tengan recorridos hamiltonianos en todos los vértices finales posibles. En una entrada anterior hemos dado un ejemplo de S4 que es entangled 1/2 y tiene recorridos hamiltonianos en todos los vértices finales posibles. Es decir todavía no se ha llegado al fondo del asunto. Y que sean sólo entangled (es decir no entangled 1/2) tampoco significa que sean necesariamente fáciles. Y hemos hablado en otras entradas de algún caso sólo entangled, que tenía recorridos hamiltonianos en todos los vértices finales posibles pero que encontrarlos en uno  de ellos no era nada nada fácil.

Por otra parte recordamos que los casos entangled 1/2 y cycle-entangled no agotan todos los casos potencialmente difíciles. En la patente identificamos otro tipo de propiedad que se puede dar en los casos no entangled y que también puede ser causa de dificultad, la propiedad de ser Twisted (y su contraria la de ser smooth que sería señal de facilidad).

Aunque dejamos para otro día nuestros comentarios al respecto, queda claro que las causas de no hamiltonicidad son diversas: rankin, twistedness, entanglement 1/2, cycle-entanglement. Normalmente los casos complicados no Rankin no aparecerán en pares de Sn que generen el grupo de orden n! sino en pares de Sn+1, Sn+2 etc…que generan el grupo de orden n!.

4. La familia infinita Sigma Tau.

Ya en la descripción de la patente comentábamos, citando el libro de Knuth TAOCP en el  que habla del problema, que dábamos este caso y otros por resueltos (es decir considerábamos que asintóticamente todos los miembros de la familia  tendrían recorridos hamiltonianos en todos lo vértices finales posibles), módulo teorema de Rankin.

Nota. Este es el problema al que Knuth calificó como uno de los  más complejos de todos los  problemas de su libro, con una calificación de 48/51, siendo 51 la calificación más compleja posible.  Fin de nota.

En 2012-2013 un investigador canadiense ha confirmado  nuestra afirmación utilizando en parte las técnicas de nuestra patente. No he leído con detalle el artículo y desconozco hasta que punto la parte que utiliza de nuestros resultados es importante para el resultado. Concretamente utiliza la propiedad de regularidad de IAS que intentamos patentar como paso 1.

El caso es que no le he prestado atención a este tema hasta la última Office Action.  A continuación mis averiguaciones. Todos estos casos van a tener los siguientes parámetros:

–generador de orden 2 (por la propia definición del caso),

–generador de orden n (por la propia definición).

–IAS de orden n-1  (es fácil ver que esto tiene que ser así para toda la familia). Como n recorre los naturales, n-1 también y por lo tanto habrá casos en los que el teorema de Rankin sea aplicable. Interesa por lo tanto conocer que pasa cuando el IAS es par.

Conociendo sólo estos tres parámetros me parece bastante notable que estos casos puedan generar Sn para todo n. Entiendo que la clave debe de estar en la circunferencia. He calculado los 4 parámetros (orden de generador 1, orden de generador 2, IAS  y circunferencia que aparecen en este orden a continuación) para algunos n. En negrita los que tienen el IAS impar. Recordemos  que en los casos de IAS impar el número que expresa el valor de la circunferencia tiene un significado literal, en el sentido de que esta contendrá tantos IASes como indique este número. Mientras que en los pares tendrá el doble de IASes (indicamos el número de IASes entre paréntesis).

n=4. 2434. Este es smooth. Es planar y por  lo tanto se puede empotrar en una esfera. Que sea planar implica que sea smooth. 

n=5. 2543 (6). Este es smooth. Pero de momento no tengo clara su topologia: ¿ esfera o toro ?.

n=6. 2656. 

n=7. 2763 (6).

n=8 2878

Empieza a emerger un patrón.

n=9 298¿?

3 (6).

Realmente notable, y me refiero a los casos de IAS par. Si se confirma que este patrón es así, si se demuestra que tiene que ser así, entonces un generador queda fijo (el de orden 2) y la circunferencia también, y van variando en una unidad con cada n tanto el IAS como el otro generador.  Me pregunto que propiedades estructurales tienen los casos de IAS par.

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: