HPC. Sobre la propiedad de lisura o smoothness en Dígrafos de Cayley Bigenerados: ¿ una caso que la falsifica ?.

Actualizado 27 de junio de 2015, con un resultado de 2013 que utiliza los resultados de la patente para obtener una familia infinita de Dígrafos de Cayley bigenerados que no tienen caminos hamiltonianos. Aunque no lo he mirado en detalle y reservo mi opinión para cuando lo haga, como comento más adelante, aunque a priori éste resultado es interesante (sobre todo porque una de las familias sobre las que hablan en el artículo no está basada en involuciones), conociendo mi método (y sobre todo la teoría implícita en la que se basa), obtener éste tipo de resultados ye a no tiene gran dificultad. Se conoce cuales son los parámetros que hay que tocar. 

La alternativa a usar nuestra teoría y los tests que se derivan de ella serían inviables: al margen de que para tamaños grandes ya sería (posiblemente, ya digo que tengo que mirar el artículo; la familia propuesta podría ser de orden pequeño en relación al IAS y por lo tanto resultar ser computacionalmente fáciles para nuestro método; he visto que incluyen una familia metacíclica y como es sabido estos tienen orden <n(n-1) con n el grado de la permutación) imposible determinar computacionalmente que no existen recorridos hamiltonianos en éste tipo de dígrafos sería imposible, también lo sería poner a prueba un número infinito de dígrafos. Sin embargo el examinador considera que éstos resultados no son más que ideas abstractas, que se agotan en si mismas sin ninguna consecuencia práctica. 

Nota inicial. Como puede ver el lector, se me acumula el trabajo. Esto es lo que tiene el ser  un investigador independiente…😦. No solo tienes que hacer tu todo el trabajo sino que  te  dan golpes por todas partes, los examinadores incluidos. Como en anteriores entradas distingo por  el color del texto la parte meramente técnica (color negro)  de la indignada (color rojo). La asignación de colores es puramente casual.  

Resuelto: el caso es twisted, no hay falseamiento, no podía haberlo.

En las anteriores entradas hemos hablado mucho de la propiedad de entrelazado o entangled ya que permite identificar casos potencialmente difíciles. Hay otra propiedad que nos permite afinar más: la de lisura o smoothmess, y sobre ella hablamos en éste punto.

I. La propiedad de lisura o smoothness.

Por definición los  casos en los  que uno de los generadores es de orden 2 son entrelazados. Pero hay muchos casos que siendo un generador de orden 2 y el otro de orden > 2, no son necesariamente difíciles y nos interesa  encontrar otra propiedad que nos permita identificar dentro de éste subconjunto de Dígrafos de Cayley bigenerados a los difíciles.

Para ésto hemos inventado o diseñado la propiedad de lisura o smoothnes. Esta propiedad viene a decir que hay casos  en los que el entorno de la identidad (con una definición muy concreta que se corresponde con un test muy concreto) es liso o smooth. Los que  no son lisos o smooth son retorcidos o twisted  y hacen honor a su nombre pues entre ellos están los casos más complicados.

En esta entrada, algunos ejemplos  gráficos, como el que sigue:

Parámetros: Grado 5, 120 vértices, identidad 12345, generadores 13254 de orden 2 y 24513 de orden 6, IAS de orden 12 (6 vértices finales posibles), Circunferencia de orden 2.

caso twisted

No es smooth ya que si construimos el IAS de la permutación 41324 o el DAS de la permutación 12543, teniendo en cuenta que ambas se encuentra dentro de las permutaciones que se encuentran al aplicar el generador de orden 6 a la identidad, este IAS y este DAS tienen permutaciones en común con los IASes o DASes de permutaciones que se encuentran dentro del IAS o DAS de la identidad. Por esto el entorno de la identidad no es liso.

Este caso es difícil ya que no tiene recorridos hamiltonianos en ninguno de los vértices posibles, excepto en uno. Ya obtuve éste resultado hace años y lo he repetido hoy. Para encontrar el RH en el único vértice que lo tiene ha tardado menos de 1 minuto. Para demostrar que no existe en los otros 5 vértices finales posibles ha tardado: 2 minutos para el primero, 7 minutos para el segundo, 5 minutos para el tercero, el cuarto es el que tiene RH, 2 minutos para el quinto y un minuto el sexto. Nótese que el método, aunque rápido es exhaustivo (y por lo tanto 100% fiable), es decir es el backtraking determinista más optimizado posible para éstos casos (Dígrafos de Cayley bigenerados) y que para casos de mayor tamaño (por ejemplo de 1000 o 10.000 vértices), seguramente ya sería poco práctico (en mis condiciones, ya comentadas en otras entradas digamos que tardaría no toda la vida del universo pero sí días o semanas; es suposición no lo he puesto a prueba; quizás en otras condiciones, la frontera de los casos difíciles en los que no merece la pena ni intentarlo sea más elevada, entre 10.000 y 100.000). ¿ Por otra parte tiene sentido  esta variación en el tiempo en función del vértice final ?. Si, tiene sentido, sobre todo aunque no solo, en los casos en los que un generador es una involución o de orden 2.

Pero precisamente por haber casos difíciles de este tipo es muy relevante desde el punto de vista práctico, para por ejemplo un diseñador de redes de interconexión, disponer de tests que nos permitan cribar los casos complicados de los tratables y dedicarnos a éstos últimos, siempre y cuando cumplan con otros parámetros que nos interesan. La diferencia está entre poder investigar o no poder investigar, por ser los tiempos prohibitivos.

A) ESTO PRECISAMENTE ES LO QUE NO HA COMPRENDIDO EL EXAMINADOR.  UN TEST NO SE AGOTA EN SI MISMO, PUEDE SER ALTAMENTE PRÁCTICO, PUEDE AHORRAR MUCHO TIEMPO, MUCHA ENERGÍA MUCHO DINERO AL USUARIO Y A LA SOCIEDAD.   POR ESO DIGO QUE EL EXAMINADOR ES UN IRRESPONSABLE: O BIEN POR SOBRECARGA DE TRABAJO (YA DIGO QUE QUIERO PENSAR BIEN) NO SE HA LEÍDO EN DETALLE LA DESCRIPCIÓN DE LA INVENCIÓN Y HA DENEGADO LA SEGUNDA SOLICITUD SIN SABER LO QUE ESTABA EVALUANDO, O BIEN SE LA HA LEÍDO EN DETALLE Y A CONCIENCIA DEL AHORRO QUE SUPONEN TODOS LOS TESTS DE LAS REIVINDICACIONES (Y YO SE LO HE EXPLICADO PERSONALMENTE EN VARIAS TELECONFERENCIAS), LA HA DENEGADO UTILIZANDO ARGUMENTOS QUE NO SE SOSTIENEN. POR SU RESPUESTA YO ESTOY CONVENCIDO DE QUE ESTAMOS EN LA PRIMERA POSIBILIDAD (Y EN PARTE LO COMPRENDO, YA QUE ME CONSTA QUE ESTÁN SOBRECARGADOS). DE CUALQUIER MANERA, HAYA SIDO LA DENEGACIÓN POR UN MOTIVO O POR EL OTRO, SEA POR DEJADEZ O POR MALA FE, EN MI OPINIÓN ES UN IRRESPONSABLE. ESTOY AVERIGUANDO SOBRE SI HAY ALGUNA MANERA DE PRESENTAR UNA QUEJA A LA USPTO POR EL COMPORTAMIENTO DE ÉSTE SERVIDOR PÚBLICO.

¿ RECOMENDACIÓN (son ideas que se me van ocurriendo y que escribo para madurarlas más adelante) ?: POR OTRA PARTE YO CREO QUE LOS EXAMINADORES / LA USPTO DEBERÍAN DE ASUMIR ALGUNA RESPONSABILIDAD ECONÓMICA POR LOS RECHAZOS INDEBIDOS QUE LUEGO SE DEMUESTREN COMO TALES EN EL CIRCUITO FEDERAL. SI NO ES MUY FÁCIL HACER DENEGACIONES GRATUITAS, OBSTACULIZAR…NI GANAN NI PIERDEN NADA. LA PROFESIONALIDAD NO SE DEBE DE DAR POR SUPUESTA. YA LAMENTABLEMENTE NI SIQUIERA EN EEUU.  

B) OTRA POSIBILIDAD ES QUE SEA LA PROPIA USPTO, LA QUE, A INSTANCIAS DEL GOBIERNO, HAYA CAMBIADO DE POLÍTICA, Y POR LO TANTO HAYA UNAS INSTRUCCIONES “OCULTAS” A LOS EXAMINADORES. ANTE LA SOBRECARGA DE TRABAJO, DÓNDE ANTES HABÍA UNA POLÍTICA FAVORABLE AL INVENTOR Y LA DIRECTRIZ ERA “CONCEDER TODO Y EL QUE ESTÉ EN CONTRA DEL INVENTOR QUE LITIGUE” AHORA ES TODO  LO CONTRARIO Y LA DIRECTRIZ ES “DENEGAR TODO Y EL INVENTOR QUE QUIERA IR ADELANTE QUE LITIGUE“.

YA HEMOS COMENTADO QUE NO SOY EL ÚNICO AFECTADO POR EL CASO ALICE CORP V. CLS BANK. SON CIENTOS DE MILES DE PATENTES. YA HEMOS COMENTADO QUE HABIENDO ALTERNATIVAS ALGUIEN DENTRO DEL PODER JUDICIAL DE EEUU (UNA MAYORÍA DE LOS JUECES DEL TRIBUNAL  SUPREMO DE EEUU), QUISO RESOLVER ESTE CASO DE DETERMINADA MANERA Y NO DE OTRA. 

EN ESTE CASO Y SÓLO EN ESTE CASO, EN CIERTO MODO SE PODRÍA EXCULPAR AL EXAMINADOR, QUE SÓLO CUMPLE ÓRDENES. TODAVÍA NO TENGO CLARO DÓNDE ESTAMOS, SI EN EL ESCENARIO ANTERIOR O EN ÉSTE QUE DESCRIBIMOS AHORA. Y DIGO EN CIERTO MODO PORQUE ES UN INDIVIDUO QUE SIGUE UN JUEGO QUE PODRÍA NO SEGUIR . SI LO SIGUE O BIEN ESTÁ DE ACUERDO Y ENTONCES ES CÓMPLICE O NO LO ESTÁ Y ENTONCES ES COBARDE (Y OJO, YA SE QUE ESTO ES MÁS FÁCIL DECIRLO QUE HACERLO). POR ELLO, REPITO, SÓLO EN CIERTO MODO.  

EL MOTIVO ESTÁ CLARO (ACABAR CON LOS ASÍ LLAMADOS PATENT TROLLS), PERO LA ESTRATEGIA ES MUY EQUIVOCADA. SI SE CONFIRMASE ÉSTO CUANDO MENOS ESTA OSCILACIÓN SUPONE UNA INSEGURIDAD JURÍDICA INDIGNA DE UN GOBIERNO EN EEUU. ¿ QUIEN VA A CONFIAR EN UN PAÍS CON UNA POLÍTICA INTERVENCIONISTA TAN IRREGULAR Y BRUTALMENTE AGRESIVA CON LA CIUDADANÍA GLOBAL (TÉNGASE EN CUENTA QUE MUCHOS DE LOS CIUDADANOS O EMPRESAS QUE PATENTAN NO SON DE EEUU) ? ¿ COMO AFECTA ESTO AL CRÉDITO PAÍS DE EEUU, ADEMÁS DE A LA DINÁMICA DE LA INVENCIÓN GLOBAL ?.

¿ DE VERDAD HAN ESTUDIADO BIEN ÉSTE TEMA O ESTÁN DESPISTADOS ?. ¿ SE ESTÁ APAGANDO EL FARO QUE ORIENTABA LA ECUANIMIDAD, EL PRAGMATISMO Y EL PROGRESO GLOBAL ?. ¿ SE ESTÁ ACOMPLEJANDO EEUU ADOPTANDO ESTRATEGIAS DEFENSIVAS ?.    ¿ SE ESTÁ QUEMANDO LA TIERRA PROMETIDA ?. ¿ CUANTO TIEMPO TARDARÁ EN SER ARRASADA SI SIGUE CON ÉSTAS POLÍTICAS ?.

¿ RECOMENDACIÓN ?. ¿ No debería de ser la USPTO una agencia independiente, autoregulada, al margen de los vaivenes políticos, y que sólo recurra al Estado en caso de incumplimientos, cuando haya que ejercer la fuerza ? ¿ Una especie de Banco Central que en lo suyo, tipo de interés, actúa de manera completamente técnica ? ¿ No es la invención / innovación demasiado importante para una sociedad como para dejarla en manos de injerencias políticas ?. Lo dejo como interrogante, ya que no lo tengo claro.

El recorrido hamiltoniano en el único vértice que lo tiene, a continuación, el vértice final es 52364.

Para comprobar que es un recorrido hamiltoniano se debe de empezar  por VI el vértice inicial (=identidad=23456), leer desde VI de izquierda a derecha y de arriba abajo (comprobando que cada permutación se obtiene de la anterior aplicando uno de los dos generadores)  hasta que se llega a la última permutación de ésta primera lista, es decir {2,6,3,5,4}. Entonces de pasa de ésta a la última permutación de la segunda lista (las dos listas están separadas por una línea discontinua), es decir la permutación (2,3,6,4,5) y se sigue la comprobación de derecha a izquierda y de abajo a arriba hasta llegar a VF, el vértice final.

Finalmente se debe de comprobar que hay 120 permutaciones (incluyendo VI y VF) y que no hay repeticiones (idem), es decir  que todas son diferentes.

{{vi, {2, 4, 3, 6, 5}, {4, 6, 5, 2, 3}, {4, 5, 6, 3, 2}, {5, 3, 2, 4, 6}, {3,
4, 6, 5, 2}, {3, 6, 4, 2, 5}, {6, 2, 5, 3, 4}, {6, 5, 2, 4, 3}, {5, 4,
3, 6, 2}, {4, 6, 2, 5, 3}, {4, 2, 6, 3, 5}, {2, 3, 5, 4, 6}, {2, 5,
3, 6, 4}, {5, 6, 4, 2, 3}, {6, 2, 3, 5, 4}, {6, 3, 2, 4, 5}, {3, 4,
5, 6, 2}, {3, 5, 4, 2, 6}, {5, 2, 6, 3, 4}, {5, 6, 2, 4, 3}, {6, 4,
3, 5, 2}, {6, 3, 4, 2, 5}, {3, 2, 5, 6, 4}, {3, 5, 2, 4, 6}, {5, 4,
6, 3, 2}, {4, 3, 2, 5, 6}, {3, 5, 6, 4, 2}, {5, 4, 2, 3, 6}, {4, 3,
6, 5, 2}, {4, 6, 3, 2, 5}, {6, 2, 5, 4, 3}, {6, 5, 2, 3, 4}, {5, 3,
4, 6, 2}, {3, 6, 2, 5, 4}, {6, 5, 4, 3, 2}, {5, 3, 2, 6, 4}, {3, 6,
4, 5, 2}, {3, 4, 6, 2, 5}, {4, 2, 5, 3, 6}, {4, 5, 2, 6, 3}, {5, 6,
3, 4, 2}, {6, 4, 2, 5, 3}, {4, 5, 3, 6, 2}, {4, 3, 5, 2, 6}, {3, 2,
6, 4, 5}, {2, 4, 5, 3, 6}, {2, 5, 4, 6, 3}, {5, 6, 3, 2, 4}, {6, 2,
4, 5, 3}, {6, 4, 2, 3, 5}, {4, 3, 5, 6, 2}, {4, 5, 3, 2, 6}, {5, 2,
6, 4, 3}, {2, 4, 3, 5, 6}, {2, 3, 4, 6, 5}, {3, 6, 5, 2,
4}, {6, 2, 4, 3, 5}, {2, 3, 5, 6, 4}, {2, 5, 3, 4, 6}, {5, 4, 6, 2, 3}, {
4, 2, 3, 5, 6}, {4, 3, 2, 6, 5}, {3, 6, 5, 4, 2}, {3, 5, 6, 2, 4}, {
5, 2, 4, 3, 6}, {2, 3, 6, 5, 4}, {2, 6, 3, 4, 5}, {6, 4, 5, 2, 3}, {
4, 2, 3, 6, 5}, {2, 6, 5, 4, 3}, {6, 4, 3, 2, 5}, {4, 2, 5, 6, 3}, {
4, 5, 2, 3, 6}, {5, 3, 6, 4, 2}, {3, 4, 2, 5, 6}, {3, 2, 4, 6, 5}, {
2, 6, 5, 3, 4}, {2, 5, 6, 4, 3}, {5, 4, 3, 2, 6}, {4, 2, 6, 5, 3}, {
4, 6, 2, 3, 5}, {6, 3, 5, 4, 2}, {3, 4, 2, 6, 5}, {4, 6, 5, 3, 2}, {
4, 5, 6, 2, 3}, {5, 2, 3, 4, 6}, {2, 4, 6, 5, 3}, {2, 6, 4, 3, 5}, {
6, 3, 5, 2, 4}, {6, 5, 3, 4, 2}, {5, 4, 2, 6, 3}, {4, 6, 3, 5, 2}, {
4, 3, 6, 2, 5}, {3, 2, 5, 4, 6}, {2, 4, 6, 3, 5}, {2, 6, 4, 5, 3}, {
6, 5, 3, 2, 4}, {5, 2, 4, 6, 3}, {2, 6, 3, 5, 4}},

——————————————————————-

{vf, {6, 5, 4, 2,
3}, {6, 4, 5, 3, 2}, {3, 6, 2, 4, 5}, {3, 2, 6, 5, 4}, {5, 3, 4, 2,
6}, {2, 5, 6, 3, 4}, {3, 2, 4, 5, 6}, {5, 3, 6, 2, 4}, {2, 5, 4, 3,
6}, {2, 4, 5, 6, 3}, {6, 2, 3, 4, 5}, {6, 3, 2, 5, 4}, {5, 6, 4, 3,
2}, {3, 5, 2, 6, 4}, {6, 3, 4, 5, 2}, {5, 6, 2, 3, 4}, {3, 5, 4, 6,
2}, {3, 4, 5, 2, 6}, {2, 3, 6, 4, 5}}}.

II. ¿ Una caso falsificador ?

Ahora estoy trabajando en otro caso similar, de grado 9, que tiene como generadores a 3452687(10)9 de orden 4 y 2346587(10)9 de orden 2 (es entangled pero sólo por ser un generador de orden 2), que nunca había estudiado en profundidad / dibujado (aunque sí que estaba en la base de datos con la que trabajé inicialmente). Es un caso difícil, ya que según el algoritmo no tiene recorridos hamiltonianos en ninguno de los vértices posibles. Pero no se si es twisted o liso, y por lo tanto podría falsificar la teoría.

Ya sus propiedades indican que debería de ser twisted: el IAS es de orden 10 (tiene 5 vértices finales posibles, pero por el teorema de Rankin sólo tenemos que comprobar si tiene o no  tienen recorridos hamiltonianos dos de ellos) y la circunferencia es de orden 6. Como el IAS/2 es impar, esto quiere decir que hay 6 IASes en la circunferencia (si fuese par habría el doble de IASes o DASes). Esto significa que si fuese liso, sólo en la primera circunferencia tendría 54 permutaciones diferentes. Una circunferencia ortogonal tendría que tener 52 nuevas permutaciones, todas diferentes a las anteriores. Esto suma 106. Si fuese liso todas los IASes y DASes del entorno de la identidad no podrían tener permutaciones comunes y así a ojo clínico, ya saldrían más de 120 permutaciones, que es el número total de vértices que podemos tener.

Por lo tanto, con esta cuenta de la vieja, ya podemos prever que debe de ser twisted. Queda claro  que lo anterior es un borrador o idea de demostración, que igual no le ha quedado clara al lector, pero que pulida se podría convertir en método alternativo a la construcción del entorno  de la identidad y comprobación de si la propiedad de lisura se cumple  o no. Pero de  momento prefiero dibujarlo a mano (no tengo programado de momento un test de smoothness / lisura y lo tengo que hacer a mano) para comprobarlo y lo comprobaré también con otros casos similares más que nada para ilustrar al lector en que consiste la propiedad de lisura o smoothness. Una vez realizadas las comprobaciones es posible que pula el método indirecto o numérico de demostración que nos permita, dados los parámetros, decidir si un caso es smooth sin construir el entorno de la identidad.

El lector puede hacerse una idea de lo que cuesta analizar manualmente un caso de éstos. Con S5, o casos de 120 vértices todavía es posible, pero ya con S6 es inviable. S6 revienta ya cualquier cerebro humano.

Mantendré al lector informado actualizando la entrada.

Actualización mismo día unas horas más tarde.

Primer avances:

SMOOTH O TWISTED

Por los parámetros sabemos que éste caso tiene 120/5 = 24 IASes o DASes.  Como se ve se han dibujado ya 4 IASes /DASes del entorno de la identidad y aparecen ya 34 permutaciones diferentes. De éste entorno de la identidad faltan los que aparecen a medio hacer (creo que no falta ninguno). ¿ Generarán permutaciones sin repeticiones en cuyo caso estamos hablando de un caso smooth o habrá repeticiones, en cuyo caso es twisted ?.

Segundo avance: 50 permutaciones, todas diferentes. ¿ Que piensa el lector que es twisted o que es smooth ?

twisted or smooth 2

P.s. Pido disculpas por los tachones y me he despistado en una transposición, me han interrumpido un par de veces…

Tercer avance. De nuevo varias interrupciones. En la imagen aparecen unas 75 permutaciones, todas diferentes. De momento o se puede considerar twisted.

smooth o twisted 3

Resultado final: twisted.

¡¡ twisted !!

¿ Por qué es  importante la propiedad de retorcimiento o su contrapositiva, la propiedad de lisura ? ¿ Por qué si es twisted entonces puede no haber recorridos hamiltonianos y si es smooth los habrá siempre en todos los vértices finales posibles ?.

1. Hamiltonianos por defecto:  ¡¡ casi todos !!. 

Por defecto hay recorridos hamiltonianos en todos los vértices finales posibles en todos los casos siempre, salvo que haya alguna barrera que lo impida.

Y la buena noticia, que conocemos gracias a los resultados de la patente, es que se puede demostrar que asintóticamente casi todos (almost all, palabra técnica) los casos son smooth y por lo tanto se aplica el defecto.

2. Efectos limitados y locales.

Salvo que el caso esté muy entrelazado, en cuyo caso es posible que sólo con la elección del vértice final posible, las consecuencias de ésta elección sean tales que se activen todos  los IASes sin que haya ninguna otra opción, las consecuencias de activar un IAS al inicio de la búsqueda suelen ser limitadas y locales: la activación de un IAS sólo afecta a aquellos IASes o DASes que están en contacto con él.

3. No puede haber efecto  sin causa.

Cuando es twisted, dos o varios IASes o DASes que están en contacto con el IAS de la identidad están en contacto entre sí y pueden tener efectos (contradictorios) sobre el IAS de la identidad.  Nótese que en los dos casos que hemos analizado, aunque tienen parámetros diferentes (los órdenes de los generadores, de los IASes, la circunferencia…) la situación es la misma: esta relación de dos IASes que están en contacto con el de la identidad se hace a través de involuciones. En general en los casos más  difíciles de gran tamaño estarán implicadas involuciones, ya que son éstas las que permiten mejor una transmisión de efectos de este tipo. Cuando el caso es smooth, los IASes distantes no pueden tener efectos sobre lo que pasa en el IAS de la identidad y no pueden generar barreras, obstáculos o contradicciones que impidan que haya recorridos hamiltonianos. Por otra parte es importante señalar que la  propiedad de twisted es necesaria pero no suficiente. Diría que puede haber casos twisted que finalmente no sean difíciles, cuya forma de interconexión entre los IASes del entorno de la identidad no generen obstáculos a la hamiltonicidad.

Dejamos al lector que analice por si mismo cuales son los efectos de la propiedad de retorcimiento que generan un obstáculo insalvable para que en éste caso haya recorridos hamiltonianos. Como hemos visto en otros casos anteriores, a veces los efectos no son totales y dejan que haya recorridos hamiltonianos en algunos de los vértices posibles, afectando sólo a otros.

No se si la explicación está clara.  En cualquier caso la propiedad de smoothness, para cuyo testeo todavía necesito construir todo el entorno de la identidad (es decir que la posible demostración más rápida con métodos cuantitativos todavía no está clara), es clave y absolutamente informativa para ver si el caso es fácil (tendrá recorridos hamiltonianos en todos los vértices posibles) o difícil (en cuyo caso lo mejor es analizarlo en produndidad.

Quiero que quede claro una vez más que ésta manera de ver éste problema no se conocía antes de los resultados de la patente: se iba a ciegas, para determinar si un caso tenía recorridos hamiltonianos se tenía que aplicar un algoritmo de fuerza bruta más o menos genérico, más o menos optimizado, incorporando a lo mejor alguna subrutina en función de las propiedades del caso, que acortase algo la búsqueda. Ahora, para todos los casos, gracias a los resultados de la patente, sabemos dónde mirar.

Es más claramente  al identificar que un caso es twisted, el investigador  en vez de realizar una búsqueda exhaustiva puede optar por analizar el caso tal y cómo hemos realizado nosotros, identificar el obstáculo a la hamiltonicidad, y demostrar de manera sencilla que el caso, en el vértice final posible seleccionado, no puede tener recorridos hamiltonianos. Este proceso se puede incluso automatizar, suponiendo un ahorro brutal. Ya hemos dicho que las búsquedas exhaustivas de recorridos hamiltonianos en casos en los que no existen exigen un esfuerzo computacional brutal que de esta  manera se puede evitar.

Sin embargo el examinador, por motivos que se me escapan no valora estos tests tan útiles para el diseñador de redes, que le permiten un ahorro de tiempo de investigación tan brutal, que permiten un ahorro de tiempo de búsqueda computacional de soluciones tan brutal.  Ha dictaminado que son ideas abstractas sin mayores consecuencias prácticas, que se agotan en sí mismas.

Relacionado. Un artículo reciente (de 2013, no se si lo reseñamos ya en una entrada en su momento o fue otro y éste no lo conocía) en el que dan dos ejemplos de familias infinitas de Dígrafos de Cayley bigenerados que no tienen caminos hamiltonianos.

El autor utiliza el IAS y el resultado de los vértices finales posibles, dos técnicas que nosotros hemos intentado incluir como reclamaciones en la segunda solicitud de patente.  Lo tengo que mirar en detalle. A priori interesante aunque conociendo mi método éste tipo de resultados ya no tiene mayor dificultad.  Ya se sabe dónde mirar para encontrar éste tipo de casos.

Título. On Cayley Digraphs That Do Not Have Hamiltonian Paths

Abstract.

We construct an infinite family of connected 2-generated Cayley digraphs that do not have hamiltonian paths, such that the orders of the generators and are unbounded. We also prove that if is any finite group with [[G,G]], then every connected Cayley digraph on has a hamiltonian path (but the conclusion does not always hold when or ). 

Extractos.

La primera familia.

Proposition 2 (attributed to Milnor [2, p. 201]). Assume the finite group is generated by two elements a and b, such that a^2=b^3=e. If |G|>= 9|ab^2|, then the Cayley digraph does not have a hamiltonian path.

La segunda familia.

The examples in the above proposition are very constrained, because the order of one generator must be exactly 2 and the order of the other generator must be exactly 3. In this note, we provide an infinite family of examples in which the orders of the generators are not restricted in this way. In fact, and can both be of arbitrarily large order.

Theorem 3. For any n elemento de N, there is a connected Cayley digraph, such that 

(1) The corresponding Cayley Digraph does not have a hamiltonian path,

(2) a and b both have order greater than n. Furthermore, if p is any prime number such p > 3 that and p es congruente con 3 (mod4), then we may construct the example so that the commutator subgroup of G has order p. More precisely, G=Zm*Zp is a semidirect product of two cyclic groups, so is metacyclic.

Remark 4. Here are some related open questions and other comments.

(1)The above results show that connected Cayley digraphs on solvable groups do not always have hamiltonian paths. On the other hand, it is an open question whether connected Cayley digraphs onnilpotent groups always have hamiltonian paths. (See [3] for recent results on the nilpotent case.)

(2)The above results always produce a digraph with an even number of vertices. Do there exist infinitely many connected Cayley digraphs of odd order that do not have hamiltonian paths?

(3)We conjecture that the assumption “p es congruente con 3 (mod 4)” can be eliminated from the statement of Theorem 3. On the other hand, it is necessary to require that p>3 (see Corollary 16).

(4)If is abelian, then it is easy to show that every connected Cayley digraph on has a hamiltonian path. However, some abelian Cayley digraphs do not have a hamiltonian cycle. See Section 5 for more discussion of this.

(5)The proof of Theorem 3 appears in Section 3, after some preliminaries in Section 2.

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: