Sobre el comportamiento asíntotico de la distribución de casos por grados, de Sn II (actualizado)

Abro un nuevo post, continuación del anterior.

1. Recordemos que según los resultados de la solicitud de patente, la propiedad clave para la existencia de RH en todos los vértices finales posibles es que los digrafos sean smooth, es decir localmente lisos.

Realmente no tango nada claro que los casos free-entangled del post anterior sean escalables para tamaños mucho más grandes de IAS / DAS. De cualquier manera, presento aquí un caso, que se puede considerar free-entangled (aunque especial porque su entrelazamiento consiste en que uno de los generadores es una involución), no es smooth y si que pienso ahora mismo que éstos casos puedan ser escalables independientemente del tamaño del IAS, es decir que haya infinitos casos de éste tipo.

Una imagen del caso:

 

 

 

 

 

 

 

 

 

 

 

 

Sus parámetros.

Identidad 12345, genera S5 (de 120 vertices), aunque no todos los vértices aparecen en el gráfico. Sólo aparecen 96, es decir está incompleto ya que con 96 vertices yo ya tenía suficiente información para lo que me interesaba.

No es smooth ya que el IAS de color azul que tiene el arco

15243–>12534

conecta el DAS, de color negro, que tiene el arco 12534–>15243, con otros IAS que está conectado con IAS de la identidad. En los casos smooth esto no puede suceder (por definición).

No es cycle-entangled. No es necesario que el otro generador sea de orden 4. Experimentalmente hay casos de orden 6…pero no tengo clara la compatibilidad  de las siguientes propiedades:

–no ser localmente liso o smooth,

–IAS/DAS, tamaño de Landau, orden del generador que no es involución tamaño de Landau,

–genera Sn, para un n dado

–es vértice transitivo.

Es decir si queremos que tanto el orden del generador no involución cómo del IAS/DAS sea asíntoticamente Landau, no podrá ser localmente no liso. Sin embargo si creo que si que puede ser asíntoticamente no liso si solo exigimos que uno de los dos ordenes, por ejemplo el del IAS/DAS sea de orden “Landau”.  Estos casos, dónde un generador es una involución y el IAS puede tener el tamaño de Landau son los que debemos considerar cómo los que dado un Sn, para todo grado podrían ser escalables y tener mayor tamaño.

Éste caso es además muy interesante ya que no tiene RH en ninguno de los vertices finales posibles. Es decir pertenece a la clase de casos más difíciles. Si añadimos el generador inverso del generador que no es una involución, se convierte en un grafo de Cayley cúbico, que son conocidos por ser los más difíciles para el problema RH entre los expertos en éste problema. Pese a su dificultad el método de la patente determina muy rápidamente si existen RH o no.

2. A partir de este nuevo modelo de cota inferior así es cómo veo las cosas ahora mismo en relación a la distribución que estudiamos. Posiblemente esta visión tenga un carácter provisional, pero creo que supone un nuevo  avance hacía el modelo correcto:

A los casos que no son smooth, en la solicitud de patente les llamo twisted.  Además a los casos parecidos al de la figura de arriba se les puede llamar free-twisted dado que ninguno de los IAS /DAS que salen del IAS y del DAS inicial están relacionados entre ellos (dejemos esto cómo definición muy provisional de free twisted).

Entonces al igual que hay un grado cota inferior del limite de dificultad debe de haber un grado  cota superior: aquel tal que los casos free-twisted-Landau generan un número de vertices superior a Sn. Todos los digrafos no isomorfos a digrafos de grado inferior que sean generados por permutaciones de grado entre  estas dos cotas tendrán un número subexponencial de IAS de tamaño subexponencial. Por debajo de la cota superior, todos fáciles. Por encima de la cota superior, los digrafos tendrán número polinómico de IAS de orden Landau (subexponenciales). Muy posiblemente todos o casi todos los de esta franja sean cycle-entangled y deben ser los que caracterizan a los problemas en NP.

Cabe preguntarse si el tamaño de la supuesta franja entre la cota inferior y la superior se mantiene, estrecha o ensancha, asíntoticamente. Claramente las dos se deben alejar de los extremos del rango, inferior y superior respectivamente. Pero cómo el rango se ensancha, este alejamiento es compatible con al menos dos de las opciones. Por otra parte si utilizamos la misma ecuación para definir la cota inferior y la superior, parece que esta franja sólo podría contener un grado para todo Sn: aquel que hace que la cota iguale n!.

Por otra parte pienso que los únicos digrafos de grados superiores no isomorfos a digrafos de grados inferiores son aquellos que tengan al menos algún  parámetro (orden de un generador, orden del IAS, circunferencia…) de orden “Landau”. Si esto se confirmase y combinamos el teorema de Erdos-Turan con el teorema de Dixon obtenemos una idea de cuán frecuentes pueden ser asíntoticamente: son una fracción que tiende a cero cuando n aumenta, y a partir de un n suficientemente grande el orden de Landau está en el extremo de una distribución normal.

Actualización 20/12/2010:

A continuación figura una “tabla” que resume cómo será la dificultad que le corresponde a cada  grado del rango posible (de n a  maxdgSn) para todo Sn.

n–> smooth

n+1–> smooth

n+2–>smooth

.

.

n+x con  x la solución a la ecuación descrita en el post anterior para la cota inferior o alguna más exacta, limite de dificultad–>free-twisted  (los casos twisted, con una involución, es decir siendo uno de los dos generadores una involución y con el mínimo número de relaciones, que permitan el mayor crecimiento posible dadas estas restricciones).

.

.

n+x con el x solución a la ecuación descrita en el post anterior para la cota superior twisted, cota inferior entangled o alguna más exacta–> entangled

idem cota superior entangled–>cycle-entangled

maxdgSn.

Se debe señalar que hay casos twisted sin que ninguno de los generadores sea un involución, pero son fáciles y aquí para simplificar los identificamos con los casos smooth.

Quedaría por determinar:

— si la ecuación dada en el post anterior para las cotas inferior y superior es válida o encontrar una ecuación que ajuste de manera más exacta.

–cómo se distribuyen asíntoticamente todos los casos no isomorfos de Sn en los diferentes escalones en la distribución límite. Obtener una expresión de la distribución límite en función del grado quizás sería ya pedir mucho…

 

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: