Algorítmica y complejidad computacional. Sobre el diámetro de grupos simétricos.

(Disclaimer: esta entrada ha quedado un poco confusa; en cuanto que disponga de tiempo haré una nueva que intentará ser más clara).

Nuevo artículo sobre este tema (publicado el 26 de noviembre 2013). Ya hemos hablado sobre uno de los autores, que es el que ha obtenido la demostración de la Conjetura de Goldbach débil (que parece confirmarse definitivamente, pues no he visto noticias en contra). Otro es un autor, recientemente fallecido, que ha publicado mucho sobre estos asuntos. El  tercero por lo que he visto ha publicado más sobre un tema que ha captado nuestro interés recientemente, los grupos discretos infinitos.

Título. RANDOM GENERATORS OF THE SYMMETRIC GROUP: DIAMETER, MIXING TIME AND SPECTRAL GAP

Abstract.

Let g, h be a random pair of generators of G = Sym(n) or G = Alt(n).
We show that, with probability tending to 1 as n → ∞, (a) the diameter of G
with respect to S = {g, h, g^−1, h^−1} is at most O(n^2 (log n)^c), and (b) the mixing time of G with respect to S is at most O(n^3 (log n)^c). (Both c and the implied constants are absolute.) These bounds are far lower than the strongest worst-case bounds known (in Helfgott–Seress, 2013); they roughly match the worst known examples. We also give an improved, though still non-constant, bound on the spectral gap. Our results rest on our proof that the action of g and h on ℓ-tuples of elements of {1,2, . . . , n} gives an expander for any constant ℓ. This generalizes (Broder–Shamir, 1987), which implied the case ℓ = 1.

No se debe confudir el diámetro de un grupo con el diámetro de uno de sus Dígrafos de Cayley. El problema de encontrar el diámetro de Sn para un conjunto dado de generadores es equivalente a encontrar el diámetro del correspondiente Grafo de Cayley (el de mayor diámetro de todos los grafos de Cayley de ese grupo).

Ya hemos hablado en reiteradas ocasiones en este blog sobre el problema del diámetro en Digrafos de Cayley, desde el punto de vista algorítmico y de su relación con la teoría de la complejidad computacional. Cierto es que hablamos hace tiempo y tengo este tema completamente oxidado; no obstante en junio de 2013 publicamos la última entrada, la séptima, de la serie que hemos titulado Cuando el orden del IAS queda fijo serie de entradas que creo relevantes para los temas tratados en esta entrada.

(actualización 1, 4/12/2013: tengo que digerir con la máxima profundidad todos los artículos reseñados en esta entrada y otros para ver como encajan las entradas de esta serie con estos resultados; me ha sorprendido altamente gratamente por ejemplo ver un resultado que no conocía: los generadores de Sn, que a veces son llamados  Slow Shuffle o a veces Bubble  Sort S={(12); (12….n)} tienen siempre un diámetro Theta (n^2), según el paper Small-Diameter Caylee graphs for finite simple groups;  n indica el grado de la permutación cíclica, por lo tanto el grado; hmm…tengo que analizar estos casos en profundidad, pero ¿ por qué gratamente ? primero porque según esto hay infinitos pares de generadores,  que no tienen nada de especial, tal que el Dígrafo de Cayley de Sn que generan se puede caracterizar con sólo dos niveles (IAS y circunferencia); segundo porque por el nombre parece que estos dígrafos son siempre esféricos (no parece que el nombre tenga nada que ver con esto; no obtante tema a comprobar si efectivamente son esféricos o no); esto quiere decir que quizás casi todos los Dígrafos de Cayley de Sn se pueden caracterizar sólo con estos dos niveles y son todos de una sola pieza y los desarrollos que hemos realizado en la serie de entradas citada, Cuando el orden del IAS  queda fijo, sean innecesarios; tema a estudiar, pero de hecho el resultado del paper que comentamos va en este sentido (por ello, ¡ gran resultado !); por otra parte señalemos que el problema de recorridos hamiltonianos para este conjunto infinito de pares, gracias a los resultados de la patente está resuelto: creo que se puede demostrar fácilmente que  a partir de un tamaño son smooth, que cuando el grado n es par, el IAS y la circunferencia son iguales a n-1 y por lo tanto por el Teorema de Rankin no tienen ciclos, pero si tienen caminos en todos los restantes vértices finales posibles; cuando el grado n es impar entonces el IAS es de orden n-1 y la circunferencia es de orden  n+1 y hay recorridos hamiltonianos en todos los vértices finales posibles, sean de ciclos o caminos; según he comprobado, esto lo confirmé experimentalmente para n=5 y n=6; sería interesante estudiar como se comporta esta familia infinita de cara al tema de los sistemas RH. Aquí se puede ver un survey de 2009 titulado Survey on Path and cycle embedding in some networks, en el que repasan múltiples redes de interconexión y asignan el nombre de Bubble Sort a otro tipo de generadores. Es decir parece más bien que Bubble Sort se refiere a cualquier conjunto de generadores que genere Sn. Fin de actualización 1).

No he leído de momento el artículo.  En lo que sigue pongo en contexto sobre su contenido a los lectores.

a)  Diámetro.

Señalemos primero que el resultado de este paper se refiere a pares de generadores elegidos al azar (según la distribución uniforme) y diámetro de grafos (no de dígrafos).

Sobre el estado del arte en 2012 puedes ver este artículo (en el que participa como autor uno de los autores del artículo reseñado en la entrada.  También de interés esta entrada de mathoverflow del mismo año (en la que idem de idem.  Existe una conjetura que afirma que:

Conjetura 1: the diameter of every connected Cayley Graph Γ on Sn is O(n^2),

Sin embargo, según comentan en el paper reseñado (de noviembre de 2013).

The best worst-case bound known (i.e., the best bound holding for all generating sets S) is O(n^O((log n)^3 log log n)) [HS]. Back in [SC04], the kind of question addressed by both Thm. 1.1 and Thm. 1.2 had been described as “wide open” (see [SC04, Problem 8.11] and the remarks immediately following).

El lector puede ver aquí un paper (titulado, On the diameter of the Cayley Graphs of finite groups) sobre este mismo tema, analizado desde el punto de vista algorítmico y de fecha al menos de 2011. En el hablan de la Cota de Landau que tanto hemos utilizado nosotros y nos dan el siguiente upper bound , precisamente basado en la Cota de Landau, sobre este problema:

De nition 5.1. Let G be a group. Define diammaxG to be the maximum of
diam(G; S) taken over all sets of generators S.

Theorem 5.2 (Babai – Seress). Let G be Sn or An. (For the rest of this section, G will denote either Sn or An.)

Then diammax(G) =< e^ Raiz cuadrada[n ln n (1+o(1))]
:
This proof, like that of Proposition 3.2, is algorithmic. We define a procedure for generating any group element from an arbitrary set of generators and show that the length of the word we get has the upper bounds we want. Recall that in Proposition 3.2, we used transpositions as \stepping stones”. In this proof, however, we shall let the 3-cycles play that role.

(Actualización 2 4/12/2013: bien pensado este es otro resultado altamente relevante para la serie Cuando el orden del IAS  queda fijo; esto indica de nuevo que dos parámetros, IAS y circunferencia, parecen ser suficientes. De relevancia para esto es todo lo establecido en el paper ya citado On the diameter of the Cayley Graphs of finite groups capítulo 5, que trata sobre The maximum diameter of Sn and An. Todo es muy técnico, pero nos quedamos con la siguiente frase del final:

…which implies that length (l; S) = e^n ln n(1+o(1)). Obviously, multiplying this value by n or 2n^t does not change the asymptotics, so by Propositions 5.9 and 5.8, we have diam(G; S) <= e^nlnn(1+o(1)).

  . Fin de actualización)

Por lo tanto todavía se está lejos, en el peor caso, de la cota conjeturada. Finalmente recordamos que desde el punto de vista de su complejidad computacional,

The diameter of Cayley graphs has been studied in a number of contexts, including interconnection networks, expanders, puzzles such as Rubik’s cube and Rubik’s rings, card shuing and rapid mixing, random generation of group elements, combinatorial group theory. Even and Goldreich [EG] proved that finnding  the diameter of a Cayley graph of a permutation group is NP-hard even for the basic case when the group is an elementary abelian 2-group (every element has order 2).

Jerrum [Je] proved that for directed Cayley graphs of permutation groups, to find the directed distance between two permutations is PSPACE-hardNo approximation algorithm is known for distance in and the diameter of Cayley graphs of permutation groups. Strikingly, the question of the diameter of the Rubik’s cube Cayley graph appears to be wide open (cf. [Ko]). We refer to [BHKLS] for more information about the history of the diameter problem and related results and to the survey [He] for applications of Cayley graphs to interconnection networks.

Esta cita está extraída de un paper ya de una cierta antigüedad. El diámetro del Cubo de Rubik se conoce ya, es 20. Sobre el paper de Jerrum,  a continuación el abstract.

The computational complexity of the following problem is investigated:

Given a permutation group specified as a set of generators, and a single target permutation which is a member of the group, what is the shortest expression for the target permutation in terms of the generators? The general problem is demonstrated to be PSppace-complete and, indeed, is shown to remain so even when the generator set is restricted to contain only two permutations. The restriction on generator set cardinality is the best possible, as the problem becomes soluble in polynomial time if the generator set cantains only one permutation. An interesting feature of this problem is that it does not fall under the headings of ‘two person games’ or ‘formal languages’ which cover the great majority of known PSpace-complete problems. Some restricted versions of the problem, in which the generator set is fixed rather than being part of the problem instance, are also investigated and shown to be computationally tractable. One result of this kind is that determining the most compact expression of a permutation in terms of ‘cyclicly adjacent transpositions’ can be achieved in polynomial time. Thus, from an initial arrangement of distinct objects on a circle, one can quickly compute the smallest number of interchanges of adjacent objects required to realise any other arrangement. Surprisingly, this problem appears substantially more difficult to solve than the related one (for which a solution has been known for some time) in which the objects are arranged on a line segment.

Entonces encontrar el  camino más corto entre la identidad y una permutación dada es Pspace-complete. Para encontrar el diámetro, según un algoritmo de fuerza bruta obvio, habría que encontrar el camino más corto entre la identidad y todos los otros vértices y seleccionar el  (los, creo que no tiene porqué ser necesariamente único) de mayor longitud. Por lo tanto la complejidad del problema del diámetro para este tipo de dígrafos tiene que ser superior o igual a la del problema de encontrar el camino más corto. En Mathoverflow hay varias entradas que hablan sobre la relación entre el diámetro y la distancia media.  Aquí y aquí. (Nota: en esta otra entrada hablan sobre una aplicación de los caminos hamiltonianos]

b) Mixing time. 

En cuanto al mixing time, de relevancia son este artículo de 2004 titulado Random Walks on Finite Groups o este otro de temática similar de 2006 titulado A survey of results on random walks on finite groups. Sobre este tema, que conozco mucho menos, existe la conjetura que: 

for every O(1) generators of Sn, the mixing time of the nearest neighbor r.w. on the corresponding Cayley graph Γ is O(n^3 logn).

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: