Caso de S5, C2C4 Twisted.

Disclaimer. Entrada en construcción. Cuando esté terminada, eliminaremos este mensaje.

En entradas anteriores hemos analizado casos entrelazados (entangled) y hemos visto como esta propiedad era clave para que emergiesen obstrucciones a la hamiltonicidad. En otras hemos realizado lo mismo para casos Twisted, pero de manera poco satisfactoria en nuestra opinión. En esta entrada lo intentamos de nuevo para casos Twisted, creo que de manera algo más clara ilustrativa. Pienso que el tema va tomando ya forma, aunque todavía hay algunos interrogantes.

En linea con la última actualización presentamos el análisis, según vamos realizando de un caso 1-twisted de S5. Ya lo hemos presentado en una anterior entrada pero con otro análisis. Con éste se aprecia claramente el efecto de la propiedad twisted.

1.Opción 1. 

Nota al margen 1.

Pido disculpas al lector por lo confuso de los dibujos. No tengo tiempo para hacerlos con más claridad y para lo que me interesa, es suficiente.

Fin de nota al margen 1. 

S5 c2 c4 twisted

Hemos marcado el IAS de la identidad por el generador de orden 2. Y su opuesto, el IAS de color violeta que contiene el arco 31245–>32154 entre otros, también por el generador de orden 2. Extraemos la consecuencias de estas dos opciones y el efecto es una contradicción que se aprecia en el ciclo 23145–>34215–>41325–>12435.

Los factores determinantes que generan obstáculos a la hamiltonicidad en los casos twisted.

¿ A que se debe que el efecto de realizar estas opciones sea una contradicción ?:

–primero, que el IAS amarillo que contiene, entre otros, el arco 34152–>31425, está conectado con el IAS de la identidad y al marcar este último en un sentido, obliga a ser marcado en el otro.

–segundo, que este IAS amarillo se tuerce (esto es precisamente la propiedad de twisted) y se conecta con otro IAS que está conectado con el de la identidad y que también “sufre”  sus consecuencias.

–Tercero, idem anterior con respecto al IAS opuesto a la identidad y los dos IASes conectados con él directamente por un generador de orden 2, y que intervienen en el fenómeno, es decir el de color verde que contiene, entre otros el arco 21354–>15234 y el de color negro o azul oscuro, que contiene el arco 14325–>13452 y que aunque no se aprecia se retuerce también.

–cuarto, el hecho de que el ciclo es de orden 4, es decir corto, también ayuda. A  medida que los ciclos sean más largos será más complicado que se genere la obstrucción. Es un hecho que si bien todos los del tipo C2C4 de S5 no tienen RHs en ninguno de los VFs posibles, los del tipo C2C5 o C2C6 son más bien del tipo que tienen RHs en algunos de los VFs. Ya lo hemos visto en otras entradas. Para más detalle el lector puede leer concretamente esta entrada.

Nota al margen 2.

De momento ya damos por resueltos los casos C2C3 (digamos que hay una “teoría general” para todos ellos, basada en el resultado de Milnor).

Ahora nos estamos concentrando en algo similar para los casos c2C4 (conseguir una teoría general es un tema más complicado, pero de momento diría que no imposible).

Aunque los hemos recopilado conjuntamente con sus propiedades de hamiltonicidad, no hemos analizado en detalle de momento estos casos C2C5 y C2C6. Lo dejamos para más adelante.

Fin de nota al margen 2.

Nótese que los varios factores señalados, explican completamente el fenómeno. Veamos que pasaría si fallase alguno de ellos. Antes recordamos que el IAS de la identidad no es un IAS cualquiera. Es aquel en el que están localizados los vértices finales posibles y dependiendo del vértice final posible que marquemos, se puede activar de diferentes maneras. Esto lo diferencia de todos los demás IASes. Por otra parte, en el caso de que lo que busquemos sean ciclos, este IAS es equivalente a cualquier otro y por simetría podemos elegirlo. Elegir cualquier otro no cambiaría nada.

–supongamos que la longitud de la circunferencia (en este caso contiene 6 IASes) es mayor y que el amarillo twisted conectase con un IAS. Si la circunferencia fuese más larga y el IAS amarillo conectase con un IAS que no estuviese en contacto directo con el de la identidad. Entonces no se generaría la contradicción, al menos tan directamente, ya que faltaría uno de los arcos para completar el ciclo de orden 4. Por lo tanto en este caso, para que se genere la contradicción de manera tan directa, dos de los IASes tienen que estar conectados con el de la identidad  y los otros dos con su opuesto.

–supongamos que ninguno de los IASes que conectan con el IAS de la identidad son twisted. A continuación el caso Sigma Tau de orden 5 cuyas propiedades de hamiltonicidad conocemos.

Nota al  margen 3.

Sobre el caso Sigma Tau, una famosa familia infinita de dígrafos de Cayley Bigenerados, ver este artículo reciente, dónde utilizando en parte técnicas de nuestra patente, lo resuelven. Como ya hemos señalado en otras entradas, pensamos, cierto que sin evidencias,  que no es casualidad que este problema se haya resuelto tras la publicación de nuestra patente. De hecho hacíamos referencia a él de manera velada en ella. Me pregunto si lo que afirman es que todos los Sigma Tau tienen recorridos hamiltonianos en todos los vértices finales posibles. Para  mi esto sería la solución más completa.

Fin de nota al margen 3.

ignacio reneses sigma tau orden 5

Como se puede ver con claridad, ninguno de los IASes que salen del IAS de la identidad es twisted, como no lo es ninguno de los que salen del IAS opuesto, uno de color rojo que contiene, entre otros el arco 21543–>12543. Al activar los dos IASes, el de la identidad y el opuesto, el efecto es que sólo se activan dos arcos del ciclo de orden 5 de los IASes que están en conexión con ellos.

Se puede concluir que en este caso la propiedad de retorcimiento o twistedness es clave para que se genere la contradicción en este caso y que un caso similar aunque no idéntico que “no la tiene” (ya explicaremos por qué el entrecomillado) no es problemático. Ojo, todavía no hemos demostrado que la propiedad sea clave para que no existan RHs en ninguno de los VFs posibles: quedan 3 opciones de activación del IAS de la identidad y de su opuesto, cuyos efectos iremos viendo en succesivas actualizaciones.  Los casos 1-twisted como este, en los que los IASes que conectan con la identidad están interconectados entre ellos son los más sencillos para ver como opera la propiedad de twistedness. Y son los más sencillos para que el algoritmo determine que no puede haber RHs en ninguno de los vértices finales posibles.

Pero como veremos los casos 2-twisted, de los que mostramos  una imagen a continuación (que ya hemos mostrado en entradas anteriores) no son twisted en los IASes que conectan con el de la identidad. Sin embargo tampoco son como el caso Sigma Tau. Más adelante explicaremos la diferencia.

Ignacio RenesesS5 2-twisted

Sigma Tau y otros casos: diferencias.

¿ Cual es entonces la diferencia entre el caso Sigma Tau, que no es problemático y el caso de la última imagen, que si lo es ?.

Observe el lector primero, que en ambos casos hay IASes del DAS de la identidad que si son retorcidos. Por ejemplo en el Sigma Tau, el amarillo, que contiene el arco 23451–>32451, el gris que se encuentra a su lado o el rosa que se encuentra al lado de este último. Y lo mismo sucede con el caso de la última imagen.

La diferencia es que en el caso Sigma Tau, falta uno de los factores señalados: ninguno de los que son Twisted conectan con un IAS que conecte con el IAS de la identidad por  un generador de orden 2. Bien conectan con IASes que están fuera del entorno de la identidad (definición fija), por ejemplo el IAS amarillo ya señalado, bien conectan con el IAS de la identidad a través de un ciclo de orden 5.

Sin embargo en el caso de la última imagen, los que son Twisted del DAS, como por ejemplo el de color azul que también pertenece a la circunferencia y contiene el arco 45132–>51342 si conectan con un IAS que está en contacto directo con la identidad por un generador de orden 2 y por lo tanto puede sufrir los efectos que se obtienen al marcar este IAS de la identidad de manera mucho más inmediata. En este sentido es un caso más restringido que el anterior, que el Sigma Tau, aunque menos que el 1-twisted.

Otra diferencia (me interesa poder expresar la diferencia de manera más cuantitativa) se puede explicar como  sigue: supongamos  que somos un punto (por ejemplo  una hormiga) que nos movemos en un plano, la hoja dónde se encuentra el dibujo y que estamos dentro del IAS de la identidad. Sólo podemos salir por los arcos de orden 2, que digamos serían las puertas (los de orden 4 o más serían las paredes). Nos interesa contar por cuantos generadores de orden 2 pasamos si salimos de la identidad y llegamos de la  manera más directa posible a IAS que es retorcido y luego regresamos al IAS de la identidad siguiendo el retorcimiento. En el caso de la última imagen, tenemos que pasar cuatro arcos: 12354–>12345; 45123–>45132; 13245–>13254  (para llegar aquí hemos tenido que seguir las “paredes” retorcidas) y 54123–>54132. Es decir, pasando cuatro puertas (y esto es lo mínimo) volvemos al IAS de la identidad. Si realizamos lo mismo con el primer caso 1-twisted, lo podemos hacer pasando tres puertas. Y si lo hacemos con el caso Sigma Tau, no lo podemos hacer con cuatro. No se si es posible hacerlo pasando 5. De momento esta diferencia es más escolástica, pero es posible (y ya veo horizonte) que se pueda hacer pragmática: de alguna manera lo que estamos diciendo es que hay grados de retorcimiento. Cuando menor sea el grado (cuantos menos generadores de orden 2 haya por medio, más restringido, más complicado será el caso en el sentido de contener RHs).

Una tercera diferencia es la manera que tiene el IAS opuesto al de la identidad de conectar con los IASes que conectan con él de manera digamos simétrica, cosa que no sucede en los otros casos. De momento no tengo claro como definir de manera operativa esta diferencia.

2.Opción 2. 

En la opción 2 marcamos el IAS de la identidad por el generador de orden 2 y el opuesto por el generador de orden 4. Esta opción vale por dos, ya que si hacemos la inversa el resultado sería el mismo. En la imagen siguiente la situación al  final de realizar esto y extraer consecuencias. Aquí la contradicción va a surgir de manera menos directa y seguramente hay varias maneras alternativas de generarla algunas más rápidas o cortas que otras.

ignacio reneses 1-twisted opción 2

Nosotros probamos la siguiente estrategia: se trata de demostrar que partiendo de esta situación al marcar un IAS por las dos opciones posibles, las dos llevan a contradicción. Marcamos el IAS azul claro que contiene el arco 43512–>45321 dado que está bastante interconectado con los IASes ya marcados (este es un criterio de selección que se podría automatizar fácilmente).

Si marcamos el IAS azul  claro indicado por el generador 2, entonces se genera una contradicción en el ciclo de orden 4 nº 21 ya que el arco 54321–>42531 del IAs amarillo y el arco 42531–>23451 del IAs rosa se deben de marcar por el generador 4 generandose un ciclo de orden 4 al estar los otros dos arcos de este ciclo ya marcados. De nuevo se aprecia en esta contradicción que el hecho de que el IAS violeta que contiene el arco 35241–>54321 sea retorcido juega un papel clave en la emergencia de esta contradicción. El resultado se muestra en la imagen siguiente:

ignacio reneses 1-twisted opción 2

En conclusión si marcamos el IAS de su identidad por el generador de orden 2 y su opuesto por el generador de orden 4, entonces necesariamente el arco azul tiene que ser marcado por el generador de orden 4.  Pasamos a explorar las consecuencias de realizar esto.

Si marcamos el IAS azul claro indicado por el generador de orden 4, entonces se fuerza al IAS de verde claro que contiene el arco 32415–>34251 a ser marcado por el generador de orden 2. Si no aparecería un ciclo de orden 4. Si marcamos este IAS verde claro por el generador 2, fuerza al IAS rojo que contiene el arco 35214–>32541 a activarse por el generador de orden 4.

Al activarse este IAS de color rojo de esta manera, se genera un ciclo de orden 4, el que contiene los arcos 34512–>41352–>15432–>53142, la contradicción esperada.

Como se ve todo en todo el proceso no ha habido opción, son consecuencias necesarias. Queda demostrado que al marcar el IAS de la identidad por el generador 2 y su opuesto por el 4 (o viceversa) no se puede obtener un RH.

En la imagen siguiente se presenta gráficamente todo lo comentado:

ignacio reneses s5 opcion 2

En este último caso también (aunque se ve menos claramente en el dibujo, se podría modificar el dibujo para que se apreciase esto) el hecho de tener algunos IASes la propiedad de ser retorcidos o twisted es condición necesaria para que se genera la contradicción.

Pasamos a estudiar la última opción que entendemos tiene que tener una demostración más complicada.

Nota al margen. ¿ Están siendo más cortas estas demostraciones que las que se obtienen al activar el ciclo de la identidad de todas las maneras posibles ?. Posiblemente no, o no mucho más. Pero creo que si son más ilustrativas del papel que juega la propiedad de retorcimiento para que surjan las contradicciones. Fin de nota al margen.

3. Opción 3.

En este caso  marcamos inicialmente el IAS de la identidad y su puesto en la circunferencia por el generador 4. La situación aparece en la imagen siguiente.

(Continuará próximamente…)

Actualización 29 de agosto de 2016.

Ya tengo perfilado el método (en realidad nada nuevo, es el lógico, pero con una vuelta de tuerca) tal que si el caso es twisted y no tiene RHs en alguno o en ninguno de los vértices finales posibles, entonces puede generar la demostración de que no los tiene de manera sucinta (utilizando ordenador: de momento las pruebas no son del todo rápidas, pero si evitan una búsqueda exponencial, lo cual ya es bastante notable). Funciona tanto para los casos 1-twisted como para los 2-twisted, de momento aplicado a casos de S5. Y discrimina los casos smooth como el Sigma Tau del que hemos hablado en esta misma entrada. Quiero aplicarlo a casos de S6, lo cual llevará un cierto tiempo.

Dónde me encuentro ahora no tengo acceso fácil a Internet. Tampoco tengo las herramientas habituales que necesitaría para publicar imágenes. Además hay que hacer más comprobaciones y aunque lo que tenía en la cabeza ya está aterrizando quedan todavía algunos interrogantes sobre la propiedad twisted / smooth. Cuando tenga todo esto más claro igual se le puede dar una vuelta de tuerca más. Daremos detalles en unos días.

 Fin de actualización.

Actualización 31 de agosto de 2016.

Antes publicar todos los detalles, cosa que haremos en un par de días, queríamos adelantar un resumen de la idea general (que es aplicable tanto a los casos twisted como a los entangled). Para ello introducimos dos conceptos: el primero es una distribución que se puede asociar a cada caso, que podemos llamar distirbución de RHs y el segundo es una media, que también se puede asociar a cada caso, de IASes de un generador que se activan por cada IAS del otro generador que hayamos activado. Nos abstraemos de momento del hecho de que al se puedan marcar diferentes vértices finales posibles. Luego comentaremos sobre como afecta esto.

Distribución: cuando hemos activado todos los IASes de un caso, por u generador o por otro, podemos contar el número de generadores activados de cada tipo y obtenemos 2 cifras. La distribución asocia a cada una de estas dos cifras bien un sí (si con esta activación se obtienen recorridos hamiltonianos) bien un no (si no se obtienen), bien un número, que indica el número de RHs diferentes que se pueden obtener con esta activación. Un ejemplo de distribución para un caso hipotético de 10 IASes de C2C4:

(0 IASes activados de C4, 10 de c2)——-0 RHs,

(1, 9)————————————-0 RHs,

(2,8)————————————-0 RHs

(3,7)————————————-1 RH

(4,6)————————————2 RHs

(5,5)————————————4 RHs,

(6,4)————————————2 RHS

(7,3)————————————0 RHs

(8, 2)———————————–0 RHs

(9,1)————————————0 RHs

(10,0)———————————-0 RHs.

Repetimos que el ejemplo es puramente hipotético.

Media. Cuando analizamos un caso de C2C4, si el IAS es por ejemplo de orden 5, si buscamos un ciclo y marcamos el IAS de la identidad inicial por el generador de orden 2 se activaran, como consecuencias, 5 IASes por el generador de orden 4. A medida que vamos activando IASes, esta cantidad de IASes que se activan por un generador al marcar un IAS de otro generador puede ir variando. Y tomando nota de todo esto, al final podríamos hacer una media del numero de IASes que se activan de un generador al marcar uno del otro tipo.

Aplicación de los dos conceptos indicados.

Hay casos en los que por sus propiedades estructurales, la media que se obtiene es baja y permiten recorrer todos los pares de cifras de la distribución. Pero hay otros casos, tales que sus propiedades estructurales (como por ejemplo el ser 1-twisted o 2-twisted, o el ser entangled) hacen que la media sea tan elevada que los saltos en la distribución hacen que, independientemente de como se activen los IASes, se salte de un extremo de la distribución al siguiente, extremos en los que no pueden existir RHs.

Creo que dentro de este esquema se pueden encajar varios de los resultados previos a nuestra patente (el de Rankin casi seguro; el de Milnor tengo mis dudas), así como varios de los que hemos aportado nosotros (no tengo muy claro si los casos cycle-entangled se pueden encajar dentro de este esquema). Cuando demos detalles se verá claramente porqué en los casos twisted la media es elevada. Todo es más complejo que lo aquí descrito (pues también entra en juego el número de IASes: a igualdad de media elevada, si el número de IASes del caso es también elevado es posible que incluso saltos elevados a lo largo de la distribución no impidan que haya RHs. Realemente los casos de S5 que hemos analizado no son los más representativos. Y también hay que tener en cuenta que al activar vértices finales posibles diferentes, se activan inicialmente un número diferente de IASes por los dos generadores. El esquema presentado explica concretamente que haya casos sin ciclos hamiltonianos pero que sí tengan caminos. Y posiblemente haya otras complicaciones que iremos viendo.

¿ Podemos derivar de este esquema una teoría general que nos permita dado un caso determinar rápidamente (con unas comprobaciones mínimas) si el caso tendrá RHs en los diferentes VFs ? No lo descarto. El método sobre el que hablamos en la actualización anterior, que es puramente algorítmico,  lo que hace es tener en cuenta que en los casos 1-twisted y 2-twisted la media es elevada, y teniendo en cuenta esto permite acelerar la prueba algorítmica de que no tiene RHs, seleccionando de manera “inteligente” pero automatizable, para su activación desde los primeros paso, los IASes que suben la media para llegar lo antes posible a la solución, es decir la determinación si el caso, para el VF dado, tiene RHs o no. De la misma manera se podría retrasar. Y el algoritmo tal y como lo tenemos programado ahora mismo, hace una selección no inteligente y por lo tanto hace computaciones que se podrían evitar. Este nuevo método algorítmico (el que comentamos en la última actualización), que como decíamos no aporta nada realmente nuevo, es ya un avance significativo con respecto a lo que teníamos pues ahorra bastante tiempo y uso de memoria.

Con respecto al tema de la segunda solicitud de patente, tras todo lo comentado en la presente actualización, se justifica con mayor razón su concesión, que está pendiente, pues en todo lo descrito anteriormente  lo que hemos hecho es utilizar dos de las propiedades estructurales que se pueden dar en los casos (la propiedad de retorcimiento y la propiedad de entrelazado) para resolver de manera más eficiente que la que existe en el estado del arte actual el problema de recorridos hamiltonianos en digrafos de Cayley bigenerados. Esto es precisamente lo que intentamos proteger en dos de las reclamaciones (las correspondientes a la propiedad de entrelazado y a la propiedad de retorcimiento). Las otras reclamaciones hacen los mismo con respecto a otras propiedades estructurales. Tras cuatro años de tramitación, no me explico todavía cuales on las dudas de la USPTO al respecto…

Fin de actualización.

Actualización 2 de septiembre de 2016.

Ya estamos instalados en nuestro entorno habitual de publicación. Esperamos poder terminar esta entrada hoy mismo.

Antes, en esta actualización queremos comentar que la redacción de la actualización anterior es algo confusa y aclarar algunos puntos.

Distribución. Obviamente, aunque tal distribución exista, es desconocida salvo algunos puntos que si se pueden calcular de manera rápida sobre todo en los extremos. Por ejemplo se sab que si activamos todos los IASes por el generador de orden 2, no podrá haber recorridos hamiltonianos. Y lo mismo si los activamos por el generador de orden 4. Un paso importante es determinar dentro del rango de pares, la frontera entre aquellos pares que se sabe que no pueden tener recorridos hamiltonianos y aquellos pares o puntos de la distribución en los que el tema queda como posibilidad indeterminada. Y obviamente habrá casos, aquellos que no tienen recorridos hamiltonianos, en los que ningún par o punto de la distribución tendrá este tipo de recorridos. Es claro que dado un par puede haber diferentes activaciones de IASes que se correspondan con este par y cada activación se corresponderá con un recorrido hamiltoniano diferente. Por lo tanto a cada para le puede corresponder una cantidad de recorridos hamiltonianos. Una pregunta interesante, creo, es hasta que punto podemos considerar que la distribución es continua entre extremo y extremo.

Media. Este concepto se puede comprender mejor como un proceso que empieza con el caso en cuestión sin haber marcado ningún IAS. A lo largo del proceso se van marcando IASes, siempre controlando que no se generen ciclos o caminos que contengan menos vértices que todos los del dígrafo (es decir controlando que no sean ciclos caminos no hamiltonianos). Al final del proceso, en el que se han activado todos los IASes, se ha llegado a un punto de la distribución. Si vamos anotando a lo largo del proceso el número de IASes que se marcan de un generador por cada otro generador, podemos calcular esta media.  Entiendo que esta media es invariante al camino que siga el proceso (tema pendiente de averiguar / demostrar). Pero igual el concepto de media es prescindible… De momento para entendernos vamos a seguir hablando de media pero tenga el lector en cuenta que el concepto se puede modificar o caer.

Lo que queríamos dejar claro en la actualización anterior, la clave de todo es que en algunos casos twisted (como los que estamos analizando)  y entangled se puede demostrar o ver claramente, que debido a que en cada marcado de IAS por un generador se marcan muchos del otro, al final del proceso tenemos que llegar necesariamente a uno de los pares o puntos extremos de la distribución, de aquellos sobre los que es fácil conocer de antemano que no pueden tener recorridos hamiltonianos.

Otros puntos importantes que está pendiente de investigación son:

–primero, si para un grado de retorcimiento (por ejemplo 1-twisted), la media obtenida es siempre constante dado un tamaño de IAS, independientemente del número de vértices del dígrafo. Pensamos que así es  y por ello al aumentar el número de vértices, siendo el mismo el grado de retorcimiento, pueden variar los resultados en cuanto a propiedades de hamiltonicidad.

–segundo, si las medias varian para los diferentes grados de retorcimiento. Por ejemplo si los casos 2-twisted tienen una media inferior a los casos 1-twisted. También pensamos que así es. Si se confirmase hay como una especie de efecto gravitatorio: a mayor distancia, a mayor grado de retorcimiento, menores efectos con respecto a la propiedad de hamiltonicidad, hasta el punto de que a partir de un cierto grado (2-twisted) y un cierto tamaño de dígrafo, el efecto es nulo.

Fin de actualización.

Actualización 3 de septiembre de 2016.

Por  lo comentado en los anteriores puntos le habrá quedado claro al lector que la existencia de recorridos hamiltonianos en un caso twisted depende de al menos los siguientes parámetros:

–nº de IASes del caso.

–Tamaño del IAS.

–Vértice final posible elegido.

–Grado de retorcimiento (esto está por ver).

También de que en los casos C2C4 se da un fenómeno inverso a los casos C2C3.

Si bien en estos últimos casos, cuanto mayor sea el número de IASes, cuantos menos IASes contenga el entorno de la identidad en relación con este número total de IASes, menos podemos esperar que tenga recorridos hamiltonianos el caso.

Al contrario, en los casos C2C4, cuanto mayor es el número de IASes en relación al entorno de la identidad, mayores son las expectativas de que el caso contenga recorridos hamiltonianos.

Fin de actualización.

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: