Complejidad computacional. Cuando el orden del IAS queda fijo (7).

1. Hiperesfera e hipertoro. No se si esto o algo parecido es la forma que deben de tener los Dígrafos de Cayley bigenerados smooth (ver patente) de grupos simétricos a medida que se añaden niveles. Cada nivel superior está compuesto de unidades el nivel inferior. Ya sabemos el límite de niveles y el número máximo de unidades de nivel inferior de que puede estar compuesto.  Ahora  mismo no tengo claro si existirán en un número infinito el número de este tipo de “hiperesferas” (pienso  que si). Si que tienen que existir un número infinito de hipertoros. Tema a investigar. En la  imagen la “hiperesfera” de tercer nivel, aunque yo me la imagino más bien con el interior vacío, es decir sin la esfera azul…y seguramente me equivoco.

hiperesfera

Y también tema a investigar, de  manera más prioritaria si cuando son entangled pueden estar compuestos de más de una unidad. Ahora mismo creo que no…

2. Ojo, cuando hablo de hiperesfera (o n-esfera) o hipertoro (n-toro) el lector  podrá saber a que me refiero leyendo el resto de entradas de esta serie. Aunque la  figura que se ha mostrado anteriormente (y los conceptos de n-esfera o n-toro) son de matemáticas continuas en nuestro caso nos estamos refiriendo a una versión discreta que no tengo claro si va más allá de una metáfora.

El lector puede pensar en el hipercubo discreto, aunque tampoco es la visualización más adecuada. La construcción más corriente de un grafo hipercubo discreto es asignar a cada vértice una palabra binaria de n elementos y unir dos palabras binarias por un arco si difieren solo en un bit o coordenada (más técnicamente: we shall define the (binary) d-cube (d > 2) as the graph whose vertex set is the vector space V := (F2)^d of d-tuples over the field of two elements with two vertices adjacent if and only if they differ in exactly one entry).

Para  cualquier hipercubo de cualquier dimensión hay multiples Digrafos de Cayley isomorfos al hipercubo dado (en el enlace un artículo del John D. Dixon sobre como realizar esto para todo d; por lo que he leído, si el tamaño de la palabra es d,  el grado de la permutación correspondiente al Digrafo de Cayley isomorfo es 2^d y obviamente el grado del grafo es también 2^d), pero no son bigenerados ya a partir de d=3. En cada dimensión adicional se debe de añadir un generador. En contraste nuestros digrafos siempre son bigenerados. En el artículo citado no queda claro que todo hipercubo tenga al menos un Grafo de Cayley isomorfo, cosa que si que afirman aquí.

Otra familia de Digrafos / Grafos de Cayley que debemos de citar aquí ya que pueden llevar a confusión son los llamados toros (producto directo de dos o más ciclos). Como los hipercubos son abelianos y cuando hablamos de n-toro no nos estamos refiriendo a ellos.

Volviendo al hipercubo Qn, nuestra construcción es “similar” a la de esta familia de digrafos: partimos de una unidad de un nivel que se utiliza para construir unidades de nivel superior (en el caso del hipercubo siempre  se duplica la unidad, en nuestro suelen ser más copias que 2) que a  su vez se  utilizan para construir unidades de nivel superior,  así sin límite, es decir el  proceso se puede repetir ad-infinitum. Lo he llamado hiperesfera o hipertoro dado que los Digrafos de Cayley Smooth se pueden “empotrar” (esto también se debe de tomar de manera aproximada) en estas superficies.

P.s. investigando sobre esto leo sorprendido que el problema de determinar la complejidad computacional del problema de  isomorfismo para Grafos de Cayley  en general no estaba resuelto en el año 2000.

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: