Algorítmica y complejidad computacional. Familias infinitas de Digrafos de Cayley sin caminos hamiltonianos y Teoría Geométrica de Grupos.

(Disclaimer. los dos temas sobre los que trata esta entrada indicados en el título no tienen mucho más que ver entre si (al menos que yo  sepa) que el hecho que la aparición en ambos de los Grafos de Cayley,  y en esta entrada no se intenta relacionarlos. En realidad su aparición en una misma entrada es puramente accidental).

El otro día tras escribir esta entrada me quedé pensando en parte de lo que escribí sobre la clase P/Poly, la Extended Low Hierarchy (ELH) y como encajaba todo esto con los resultados reseñados en múltiples entradas de este blog sobre la complejidad del problema RH (recorridos hamiltonianos) en Dígrafos de Cayley bigenerados. El fin de semana pasado tuve un momento de lucidez que me llevó a concluir que debía de investigar sobre grupos infinitos y sus correspondientes Dígrafos de Cayley, tema sobre el que desconozco casi todo y sobre el que investigaré estas  navidades si finalmente tengo tiempo.

1. Un artículo encontrado por casualidad.

En fin, haciendo una breve búsqueda en internet sobe Dígrafos de Cayley infinitos, ayer encontré este paper relacionado muy directamente con la materia de mi patente. El autor, uno de los pocos que publica con una cierta continuidad sobre estos temas caracteriza una familia familia infinita de Dígrafos de Cayley finitos que no tienen recorridos (caminos) hamiltonianos.

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 a and b are unbounded etc…(en la siguiente parte del abstract detalla otros resultados).    

Enlace

Primero describe un resultado de  Milnor sobre otra familia infinita de Digrafos de Cayley finitos bigenerados tal que el  orden de los generadores tiene que ser 2 y 3. Si me he enterado bien (y no estoy seguro de ello), la familia que se propone en este paper es metacíclica. Creo que el resultado es muy interesante (al igual que el de Milnor) ya que me permitirá poner a prueba en grupos pequeños una hipótesis.

2. Tipos de grupos (finitos).

Entre las conclusiones dice que este resultado demuestra que no todos los Digrafos de Cayley de grupos solubles tienen caminos  hamiltonianos. Y comenta que queda abierto si la tienen los de grupos nilpotentes.

Dicíclicos, metacíclicos, policíclicos, solubles,  nilpotentes etc…son clases de grupos cuya diferencia no comprendo del todo ahora mismo (en realidad mi resultado se abstrae completamente de la teoría de grupos).

En este artículo de wikipedia lo aclaran un poco.

If we restrict ourselves to finitely generated groups, we can consider the following arrangement of classes of groups:

cyclic < abelian < nilpotent < supersolvable < polycyclic < solvable < finitely generated group.

Añadimos los siguientes datos:

–¿dicíclicos?<metacíclicos < policíclicos. Dentro de los dicíclicos están los grupos cuaternionicos sobre los que ya hemos hablado en detalle en otras entradas.

–todos los p-grupos finitos son nilpotentes.

–todos los grupos deorden impar son solubles.

3. Caracterización de los grupos Metacíclicos:

Según indican en este paper, titulado Some applications of metacyclic p-groups of nilpotency class-2, todos los grupos metacíclicos finitos (hay que tener cuidado pues según explican en el artículo de Mathworld, hay dos definiciones alternativas para este tipo de grupos no exactamente equivalentes) admiten una presentación por medio de 2 generadores y tres relaciones.

A group G is metacyclic with a kernel of order m and index n if, and only if, it has a presentation of the form

[a,b:a^n=b^l,b^m=1,a^(−1)ba=b^r]
 
where n,l,m,r are positive integers, such that rn≡1(m) and m|l(r−1).
 
Extraído de una pregunta en Mathematics stack exchange. Este es un resultado descrito por Hempel en un paper del año 2000 titulado

Sim (1994) ha demostrado que todos los grupos metacíclicos finitos se pueden descomponer de manera natural en productos semidirectos de dos subgrupos de tipo Hall.

Nada en contra de  mi resultado ya que si no me equivoco todos los metacíclicos son de tipo entangled (según defino este concepto en la patente).  Al contrario en el paper utiliza de manera ímplicita mis resultados (ojo no estoy afirmando ni que conozca la patente ni que lea este blog) y para la demostración creo que también de manera explícita (esto tengo que mirarlo con más detalle).

4. Grupos (discretos) infinitos.

4.1. Clasificaciones

Volviendo a la cuestión inicial  que motivó la  entrada, señalemos que los grupos infinitos son aquellos de orden infinito, es decir con un número  infinito de elementos.

Se clasifican en dos tipos:

grupos discretos finitamente generados / presentados. 

[nota: ojo no es el mismo finitamente generados que finitamente presentados; todo grupo finitamente presentado es finitamente generado, pero la inversa no es cierta; un dato importante es que un grupo admite una presentación finita si y solo si es el grupo fundamental de un espacio “razonablemente” compacto].

Un primer ejemplo de grupo finitamente generado es el de los enteros con la adición como operación y teniendo como generadores 1 y -1 (entiendo que solo estos dos generadores generan todo el grupo. Incorrecto).

De interés sobre esto es esta entrada de wikipedia sobre presentaciones de grupos (A presentation [S,R] is said to be finitely generated if S (el conjunto de generadores) is finite and finitely related if R (el conjunto de relaciones) is finite. If both are finite it is said to be a finite presentation. A group is finitely generated (respectively finitely relatedfinitely presented) if it has a presentation that is finitely generated (respectively finitely related, a finite presentation).

Los grupos finitamente generados se estudian en una disciplina llamada Teoría de Grupos Geométrica. Una muy buena introducción es este artículo de Bridson, titulado Geometric and Combinaroial group theory. Según este paper, el arranque histórico de la disciplina lo marca Poincaré y sus grupos fundamentales y por lo tanto la motivación fue topológica. Tietze (que estaba destinado a ser geólogo y de manera completamente imprevista acabó de matemático🙂 )  y Dehn le darán enseguida el giro algebraico combinatorio (aunque la motivación en Tietze seguía siendo plenamente topológica y parcialmente en Dehn)  y Gromow desarrollará plenamente el enfoque geométrico que ya estaba latente en Cayley.

En el artículo de Wikipedia enlazado se comenta: Geometric group theory, as a distinct area, is relatively new, and became a clearly identifiable branch of mathematics in the late 1980s and early 1990s. Geometric group theory closely interacts with low-dimensional topologyhyperbolic geometryalgebraic topologycomputational group theory and differential geometry. There are also substantial connections with complexity theorymathematical logic, the study of Lie Groups and their discrete subgroups, dynamical systemsprobability theoryK-theory, and other areas of mathematics.

Para un definición muy elemental de esta disciplina puedes ver esta página web. Parece que, aunque seguramente esto es incorrecto, la Teoría de Grupos Geometrica no  es más que el estudio de determinadas propiedades de los Grafos de Cayley finitamente generados, cuando se dota a dichos grafos de una métrica. 

Me pregunto cuales son las relaciones de este campo con la disciplina de la complejidad computacional (he encontrado algunos papers que relacionan las dos disciplinas, pero la relación es la clásica: complejidad computacional de problemas que aparecen en la teoría de grupos geométrica; por ejemplo este titulado The word and geodesic problems in free solvable groups del cual extraemos la siguiente frase: computing the geodesic length of elements in Sr,d con r = rango y d=clase de solubilidad es un problema NP-completo o este otro titulado The solvability problem for quadratic equations over free groups is NP-Complete. El autor del primero no parece muy satisfecho con la teoria de complejidad computacional clásica ni en su versión peor caso ni en su versión caso medio y ha propuesto otra teoría alternativa llamada generic complexity theory; sobre esto puedes ver esta presentación de 2009 titulada What is generic complexity theory ?).

Por otra parte uno de los temas sobre los que se ha investigado mucho en este campo es sobre el crecimiento en estos grupos (growth).

Finalmente señalemos que como el número de generadores de un grupo finitamente generado es siempre finito, el Grafo de Cayley que lo represente será siempre localmente finito.

no finitamente generados. 

Por ejemplo los racionales Q con la adición como operación. No existe una cantidad finita de generadores que pueda generar este grupo (en el enlace una demostración de esto; es muy elemental). Reconozco que nunca había pensado en los racionales de esta manera. Recordemos que el conjunto de los racionales es contable, pero dentro de este tipo están también los grupos incontables (es decir cuyos elementos no se pueden hacer corresponder uno a uno con los naturales). Un artículo que habla de los racionales como grupo. Había encontrado un enlace muy interesante sobre el grupo de los racionales y como se pueden empotrar en grupos con presentaciones finitas, pero aunque lo escribí en esos momentos tenía unos problemas con la conexión de internet que misteriosamente han desaparecido y no se cargó. No lo he vuelto a encontrar….

En fin, pregunta: ¿ entonces de todo vértice de un Dígrafo de Cayley de un grupo no finitamente generado salen un número infinito de arcos ?. Pregunta: ¿ que teoría o disciplina dentro de las matemáticas se ocupa de este tipo de estructuras, también la teoría geométrica de grupos ? En este paper titulado Analogues of Cayley Graphs for Topological Groups comentan: The concept of a Cayley graph has become a standard part of the toolkit sed to investigate and describe groups. It has become particularly important in the study of infinite finitely generated groups, where the Cayley graph and related concepts provide a way to treat the group as a geometric object. When the group is finitely generated it can be shown that various properties of Cayley graphs are the same no matter which finite generating set is used to construct the Cayley graph. This part becomes problematic when we consider groupsthat are not finitely generated.

[Nota: existen también los grupos continuos, cuya parte más interesante suele ser la Teoría de Grupos de Lie (al menos para los físicos; los grupos continuos constan de un número infinito no contable de elementos, piense el lector por ejemplo en el grupo de simetrías del círculo, pero algunos, entre los que están los de Lie se pueden parametrizar por un número finito de elementos) y que de alguna manera está relacionados con grupos infinitos discretos, pero desconozco si su estudio entra dentro de la teoría geométrica de grupos; aquí una introducción sobre los grupos aritméticos que son subgrupos enteros de Grupos de Lie continuos; por ejemplo Z como subgrupo de R o el subgrupo SL (2, Z) (de matrices 2×2 con entradas enteras y determinante igual a 1) de SL(n,R) o grupo especial  lineal; es importante señalar que según comentan en general los grupos aritméticos son finitamente generados y presentados; desconozco ahora  mismo si esto se puede afirmar de todos los subgrupos discretos; En el artículo de la Encyclopedia of Mathematics citado más abajo comentan que cualquier subgrupo discreto uniforme de un Grupo de Lie conexo es finitamente presentable; deduzco por lo tanto que no todos los grupos discretos son arítmeticos; aquí otra introducción, precisamente del autor del paper que hemos citado inicialmente sobre recorridos hamiltonianos en Dígrafos de Cayley  (juro que no somos primos ni nada de eso; dos personas que ni se conozcan ni tengan nada que ver pueden tener perfectamente los mismos intereses ¿ no ? ;-)).   Para terminar esta nota un enlace al artículo sobre subgrupos discretos en la Encyclopedia of Mathematics, muy completa, con antecedentes históricos. ].

4.2 Bibliografía. 

Me imagino que esta clasificación impresionista en dos tipos no es del todo correcta ni completa además de que no es más que la punta del iceberg. A continuación una selección de la abundante bibliografía descargable en PDF, para quien quiera tener un conocimiento más sistemático:

A primer to geometric group theory. Una página web (tipo.1). Tras un primer vistazo he visto cosas que me han sorprendido mucho, como esto, que sonará a quien haya leído mi patente.

primer236

Más adelante miraré esta página con más detalle.

A short course in geometric group theory.  En las primeras páginas el autor comenta que la formulación de los tres problemas de Dehn (word, conjugacy e isomorphism), que utilizan de manera ímplicita el concepto de algoritmo   precede en varios años a la formalización de  estos por Church, Kleene, Turing, Post en 1936…Todavía hoy, al menos en el correspondiente artículo de wikipedia Dehn y sus problemas no figuran en la genealogía del concepto  de algoritmo.

Geometric Group Theory. An introduction. Otra introducción, del año 2011, con un interesante gráfico en la página tres en el  que se reproduce una adaptación de la idea de otro artículo (de Bridson) sobre el universo de los grupos finitamente presentados:

bridsons-universe

El punto 1 del gráfico se corresponde con los grupos finitos, que como se ve, para los matemáticos no tienen mucho interés, pero si para informáticos y los teóricos de la complejidad computacional. El punto Z representa el conjunto de los enteros que como hemos visto es el grupo  infinito más sencillo.   A partir de Z el investigador tiene dos opciones: si se quiere mover en el terreno seguro de la conmutatividad y amenability (concepto que no se que quiere decir) se tiene que mover a lo largo de la linea superior. A  medida que avanzamos hacía la izquierda a lo largo de esta linea, se altera el crecimiento y las propiedades de construcción de los grupos (pasando de (virtualmente-) abelianos a (virtualmente-) nilpotentes, policíclicos, solubles y elementalmente amenables. Todos estos tipos de grupos construidos en base a productos semidirectos u operaciones de grupos similares tienen una estructura muy restringida. Por ello el investigador tiene la otra opción de construir en base a productos libres, en cuyo caso seguiría la otra línea que sale a partir del punto Z. En esta caso nos moveríamos por un eje que pasa por los (virtualmente-) grupos libres F, de curvatura infinita, luego por los grupos hiperbólicos Hyp de curvatura estrictamente negativa, y luego por los tipos de curvatura no positiva C0, SH (grupos semi-hiperbólicos), grupos automáticos AUT, los grupos combatatable y asíncronicamente combatable etc…[nota: este párrafo es una traducción libre de su homólogo  en el artículo original de Bridson; para una descripción más completa del gráfico y de los conceptos que aparecen en él con los artículos en los que se definen, el lector deberá ver éste].

Todo esto recuerda mucho a los gráficos y conceptos sobre clases de complejidad. En el punto 1.4 Bridson comenta “constructions such as the Higman Embedding theorem show that one can encode the workings of an arbitrary turing machine into a finite group-presentation.The groups that one obtains from such constructions will typically not belong to any of our marked classes but rather will lie in the region where the fierce lion is shown defying the groups that submit to the control of our definitions. One should therefore regard the lion as a warning that it is reckless to base a conjecture about arbitrary finitely presented groups on evidence gained along te coasts of the universe“.

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: