¿ Una generalización del “teorema” de Milnor para dígrafos de Cayley (2-3) generados ?

1.En una nota de una entrada anterior hemos profundizado sobre el “teorema” de Milnor, cuyo enunciado y alcance en un principio no comprendíamos muy bien (su resultado no se publicó, se cita en otras fuentes de manera muy incompleta como si su demostración fuese evidente; aunque todavía tengo alguna duda sobre la constante, una vez que se comprende la idea efectivamente no es complicado comprenderla).

Tras darle unas cuantas vueltas y aunque , ya tengo más o menos claro su contenido, idea de demostración que esbozamos a continuación.

En los casos (2-3) generados, cuando un path recorre el digrafo fuera del IAS de la identidad, lo recorre necesariamente con el patrón abb o ab^2. Obviamente en cualquier caso, este patrón sólo se puede repetir un cierto número de veces hasta obtener de nuevo la identidad, que variará según los generadores.

El teorema de Milnor afirma:

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=1 (o la identidad). If |G|>9|ab^2|, then the Cayley digraph does not have a hamiltonian path.

Y lo que no me queda claro es de dónde sale este n=9, ya que entiendo que en general puede haber casos en los que (ab^2)^n=1 no quede acotada por esta constante. Por ello entiendo que el resultado de Milnor se refiere a un caso específico de dígrafos.

2. En cualquier caso, las tres variables clave para que funcione el teorema son:

el tamaño del IAS,

el tamaño del dígrafo y,

el n de la relación (ab^2)^n=1.

Si el tamaño del IAS es pequeño y el tamaño del n son pequeños en relación al tamaño del dígrafo completo entonces no podrá haber RHs, dado que gran parte del recorrido se haría fuera del IAS y el n aplicado a la relación repetitiva no llegaría a cubrir todo el dígrafo.

Es decir (una primera versión,  que variará cuando tenga todo más claro) si |G|-|IAS| > |ab^2|^n=1, entonces no puede haber RHs.

Por lo tanto en aquellos casos (2-3) generados en los que el IAS suponga una parte significativa del dígrafo (y existen) habrá más posibilidades de que existan RHs. Y en aquellos en los que el IAS sea pequeño en relación al dígrafo, habrá menos posibilidades.

Más que una generalización se trataría de un test que permitiría identificar los casos (2-3) generados que no tengan RHS en ninguno de los VFs posibles. Realmente una vez se comprende el sentido del teorema de Milnor y nuestros resultados con unas minimas comprobaciones se puede llegar a la generalización.

¿ No supondrían estos últimos casos, si existiesen (todo esto que estamos contando es abstracto, al margen de momento de casos reales), una excepción a nuestro test de smoothness / twistedness?. No, dado que en general son igualmente twisted, pero si son casos que permiten una expresión más concreta, de tipo aritmético, de un obstáculo a la hamiltonicidad (similar al expresado por el teorema de Rankin y que por cierto, hemos generalizado también, apareciendo esta generalización como contenido de dos de las reclamaciones), obstáculo que se podría expresar de manera más farragosa con el test indicado.

Estudiaremos todos esto con más detalle en próximas actualizaciones a esta entrada o en entradas posteriores. Concretamente quiero ver la forma general de los generadores (2-3) de An y Sn.

Actualización 26 mayo 2016.

Con lo que estamos comentado,  en abstracto, y a la espera de posteriores comprobaciones, más concretas, me queda claro que es muy posible que haya infinitos casos / familias infinitas de tipo (2-3) con RHs en alguno de los VFs posibles. Esto me aclara una duda que tenñia. Al igual que también los hay (y posiblemente más frecuentes sin RHs en ningún VF posible; en algunos artículos algunos). Incluso no veo imposible poder determinar de antemano, sin necesidad de aplicar el algoritmo cuales de los VFs finales posibles tendrán RH. Posiblemente sólo uno en cada VF.

Por otra parte comentar que pienso entiendo que esta generalización posiblemente ya debía de estar en la mente o comentario de Milnor o de cualquier otro que se haya interesado por su resultado, a poco  que hayan intentado profundizar. Para mi, con la información de que disponía el fogonazo fue casi inmediato una vez que comprendí el resultado de Milnor he hice unas cuantas comprobaciones. Antes de las comprobaciones me rondaba en la cabeza la generalización peor no la tenía para nada aterrizada. También es posible que este y otros investigadores o no profundizasen o no dispusiesen de la misma información que yo, o que considerasen que no era necesario hacer la idea mucho más explícita…

Fin de actualización. 

3. ¿ No podría generalizarse esta técnica a otros casos (2-n) generalizados ?. Entiendo que como mucho a los (2-4) generados.  A partir de aquí, el tema está tan abierto que determinar los paths posibles cuando se recorres la zona en la que no se encuentra el IAS identidad, puede empezar a ser complejo. Estudiaremos los casos (2-4) generados.

4. Otros resultados similares. Es posible que este resultado, sobre el que ya hemos hablado en otras ocasiones, de alguna manera utilice esta misma idea. Lo tengo que comprobar.

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: