Algorítmica y complejidad computacional. Problema del camino más corto en Dígrafos de Cayley (bigenerados): los conjuntos de generadores “tratables” de J. o la historia de cuatro sorpresas.

Disclaimer. Ésta entrada puede contener algún error (máxime teniendo en cuenta lo que me cuesta leer sobre éstos temas ahora, tras varios años sin entrenar; y además la edad se va notando…no sé que es peor si el desentreno, la edad o los problemas de atención que genera internet :-)) y estar sujeta a cambios. 

Esta entrada es la historia de cuatro sorpresas. El factor común de todas ellas es que me las llevé leyendo un artículo científico de temas directa o indirectamente relacionados con los resultados de mi propia investigación (que he ido retomando de vez en cuando tras la presentación de la solicitud de la primera patente, que finalmente me fue concedida).

La primera fue del tipo de sorpresas que te dejan un poco descolocado (ya que ni te la esperas ni cuando llegas sabes por dónde cogerla), y tuvo lugar hace unos años (2009 o 2010); la segunda fue unos años después (entre 2011 y 2013, la puedo datar más concretamente) y fue grata dado que me resolvió una duda sobre la que estaba pensando activamente y a la que no veía posible por mi mismo llegar a una solución (es más la pre-solución a la que había llegado era incorrecta); la tercera fue hace una semana más o menos (la podría datar más precisamente ya que fue tras la, completamente injustificada en mi opinión, denegación de la segunda solicitud de patente) y fue de mucha menos intensidad que las otras, pero de nuevo es de las que te no te soluciona sino que te crea un problema (intelectual), de las que te deja en la incertidumbre (precisamente para aclararla he empezado a redactar ésta entrada). La cuarta ha tenido lugar hoy mismo, mientras redactaba la entrada, y de nuevo ha sido grata.

Las relato no necesariamente en orden cronológico.

1. La primera sorpresa: el problema del camino más corto (shortest path) en Dígrafos 2-generados, es Pspace-complete (ojo, cuando el tamaño del input es el grado de las permutaciones de los generadores).

Tras la investigación del resultado patentado oímos hablar del resultado publicado en un artículo en el que se determinaba la complejidad computacional del problema de encontrar el camino más corto en un Dígrafo de Cayley.

Creo que éste el artículo era o éste:

1985.

Título. THE COMPLEXITY OF FINDING MINIMUM-LENGTH GENERATOR SEQUENCES

Autor. Mark R. JERRUM. De aquí viene  la J. del título.

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 PSpACE-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 contains 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.

O éste otro anterior de Even y Goldreich.

1981.

Título. The minimum-length generator sequence problem is NP-hard. 

A natural problem which arises in connection with theisomorphism problem for graphs of bounded degree [1], and in connection with the Rubic-color-cube puzzle [2] is the following. Given a set of generators of a permutation group, determine whether a given permutation is in the group. This problem was solved by Sims [3] and the solution was investigated and shown to be polynomial by Furst et al. [4]. 

We examine the following question:

  (1) Given a set of generators of a permutation group G and a target
      permutation P, find (the length of) a shortest generator sequence
      realizing P.
  (2) Given a set of generators of a permutation group G, find the 
      minimum upper bound on the length of generator sequences needed
      to realize any permutation in G.

We show that both problems are NP-Hard by reducing the 3XC problem to each of them. The reductions we use show that these results hold even if the given set ofgenerators is restricted to contain for each generator its inverse too. 

By S. Even and O. Goldreich. Published in Journal of Algorithms, Vol. 2, pages 311-313, 1981. 

Nota al margen (importante).

Buscando (en el día siguiente al de la redacción de la entrada) el artículo de Goldreich he encontrado éste extracto, muy relevante para el tema que nos ocupa, de una de las columnas de David S. Johnson  en la que se hace eco del nuevo resultado.

[5] MINIMUM LENGTH GENERATOR SEQUENCE

INSTANCE (o Input): A set {gi : 1 ≤ i ≤ k} of generators of a permutation group G, a target permutation P ∈ G, and a positive integer K.

QUESTION: Is there a sequence gi 1 ,gi 2 , . . . , gij , j ≤ K, such that P = gi 1 gi 2 . . . gij ?- 10 –

Reference. Even and Goldreich [9]. Transformation from X3C. Comment. Also NP-hard is the problem, given a set of generators and an integer K, of determining whether all permutations in G can be generated by generator sequences of length K or less

Más adelante comentamos sobre ésta extracto, que nos aclara ya casi todo.

Fin de nota al margen.

Tras conocer éstos  resultados hace unos años le dedicamos  un cierto tiempo a éste problema (o más bien a analizar la complejidad computacional del problema de recorridos hamiltonianos en Dígrafos de Cayley), llegando a unas determinadas conclusiones.

2. La tercera sorpresa: pese a que el problema de encontrar caminos más cortos en Dígrafos de Cayley es Pspace-complete, hay casos tratables (en el sentido de que en estos casos, el camino se puede encontrar en tiempo polínomico, cuando el tamaño del problema se expresa en función del grado de la permutación).

a) La fuente de la sorpresa.

Hace poco nos encontramos el siguiente artículo en el que hacían el comentario que figura en los extractos (que señalo en rojo).

Título.  Symmetry in interconnection networks based on Cayley Graphs of permutations groups: a survey.

Extractos.

Remark 3.2. (página 375).

Notice that the notion of minimum distance between vertices in a graph is crucial to the definition of k-distance transitivity as well as to the problem of shortest path routing. If the underlying graph is a Cayley Graph, then the problem of finding the minimum distance between any arbitrary vertices say p and the designated vertex I (corresponding to the identity element) is equivalent to finding a minimal length generating sequence for the element p.

This latter problem when the generator set is not fixed is not only known to be NP-Hard, but PSpace-complete as well. However by fixing the set of generators in advance…Jerrum has derived polynomial time algorithms for minimal length generating sequence for elements of the symmetric group. This observation drives home the idea that practical interconnection networks can not be built out of arbitrary finite groups and arbitrary sets of generators.

Y tras enlazar el artículo a una entrada en éste blog, comentábamos:

hemos reflexionado y escrito mucho sobre este tema en el pasado y éste comentario nos ha abierto los ojos. El artículo de Jerrum, que conocía pero no recuerdo si pude consultar, es The complexity of finding minimal-length generator sequence (1985).  No recuerdo si el tamaño del input que consideraba el autor era el grado de la permutación o el número de vértices.  Tema a revisar“.

Decíamos “tema a revisar“. Cuando se habla del problema del camino más corto en Grafos de Cayley hay bastante confusión. Una confusión que tiene varios orígenes:

el objeto sobre el que se plantea el problema: grafos, dígrafos, grupos, conjuntos de generadores etc….

el problema en si que se plantea sobre éstos objetos: pertenencia de un elemento a un grupo dado (en cuyo caso nos vale cualquier camino del grafo o dígrafo, cualquier secuencia de generadores, de cualquier tamaño, que nos lleve al elemento, no es necesario la mínima), secuencia mínima de generadores de un elemento o de manera equivalente camino más corto entre la identidad y un elemento dado, y finalmente diámetro de un grafo (en cuyo caso hay que relacionar, en un enfoque de fuerza bruta los caminos más cortos entre todos los pares de vértices y seleccionar el más largo de todos ellos).

la complejidad computacional de éstos  problemas en éstos objetos. Aquí la confusión se origina dado que a veces se toma como tamaño del input el orden del grupo (o de manera equivalente el número de vértices del grafo o dígrafo) a veces se toma como tamaño el grado de las permutaciones del grupo y a veces (creo) el número de generadores. En función de una u otra opción los resultados varían.

Al final cuando uno lee la literatura, acaba bastante mareado con la confusión de todos éstos conceptos. No se si soy el único al que le pasa….

En fin hoy he buscado y encontrado rápidamente el artículo de Jerrum y lo he leído. Por el camino me he encontrado con otros artículos interesantes. Hablamos sobre ello en los siguientes puntos.

b) Los primeros casos tratables: el artículo de Jerrum con algunos comentarios. 

–Puedo confirmar que no había leído antes el artículo de Jerrum (lo busqué y no encontré ninguna versión descargable). No se si pude consultar el de Goldreich y Even (creo que sí, hoy no he encontrado ninguna versión descargable).

–puedo confirmar que aunque definen claramente el input en el problema,

(mi versión):

X es un conjunto finito de elementos. Y es un conjunto de permutaciones, subconjunto de S(X), el grupo simétrico sobre X o conjunto de todas las permutaciones del conjunto X. [Y] es el subgrupo de S(X) más pequeño que contiene a Y.   x es un elemento de [Y]. L(x,Y) es la minima longitud de una secuencia de permutaciones de Y cuya composición es x.

El problema de la Secuencia Mínima de Generadores se puede expresar como sigue: 

Input: una permutación x elemento de Y (la permutación objetivo que se debe de expresar como secuencia mínima de elementos de Y), el conjunto de generadores Y y un entero K (especificado en binario, luego veremos por qué).

Output: Verdadero sólo y sólo si L(x,Y)<=K.

de nuevo, tras una primera lectura (hace años que no leo sobre éstos temas y no me entero de mucho a la primera), me surge la confusión (que ya me surgió en su momento hace años cuando estudié éste tema) sobre lo que consideran el tamaño del input.

Concretamente no me queda claro si es el número de generadores o el grado de éstos (de las permutaciones que los representan). Por la definición del input parece que se refieren al número de generadores, pero en la demostración del principal teorema,

Theorem 2.2. MINIMUM GENERATOR SEQUENCE is complete for PSPACE with respect to log-space reducibility.

que es larga y para mi casi completamente incomprensible  de momento, comentan:

From the proof of the theorem we can, in fact, deduce rather more than the claimed result. Take as the machine M of the proof a fixed Turing machine which computes the solution to some problem which is complete for PSPACE with respect to log-space reducibility. Then the generator set H of the constructed instance of MGS is of fixed size, namely IFll QI + 2. Moreover, the generator set/7 is completely determined by n, the size of the input to M, and hence by the degree of the target permutation of the constructed problem instance. (It is assumed here that the reduction has been arranged in such a way that the degree of the target permutation is a strictly increasing function of n.) Hence we may deduce that MGS remains PSr’ACE-complete even when the generator set is of fixed size and is not specified as part of the problem instance.

Más adelante, cuando quiere demostrar  casos más restringidos, vuelve a comentar: A number of positive results can be obtained by specifying a fixed generator set which is not part of the problem instance. (More precisely, the generator set is determined solely by the degree of the target permutation.) 

Sobre el K del input (que al fin y al cabo es la longitud de la secuencia o del camino más corto):

Even and Goldreich [3] show that MINIMUM GENERATOR SEQUENCE is NP-hard [8, p. 324]. Furthermore, if we insist that the integer K of the problem instance be specified in unary notation, the problem is easily seen to be in NP, and hence NP-complete. (Nondeterministically generate all sequences of generators of length not greater than K, checking in polynomial time for each sequence whether its composition is z.) A different situation obtains if, as is conventional, the integer K is specified in binary notation. A consequence of Lemma 2.1 of this paper is that minimum generator sequences may be of length exponential in the degree of the permutation group; thus the obvious nondeterministic algorithm for MINIMUM GENERATOR SEQUENCE is no longer polynomial time bounded. As a result, in the formulation where K is specified in binary notation, membership of MINIMUM GENERATOR SEQUENCE in NP is not immediate.

El lema 2.1. que no conocía dice:

Lemma 2.1. For all sufficiently large positive integers n, there exists a permutation cr of degree [2n 2 In nJ such that the order of the cyclic permutation group generated by tr is greater than 2“.

The significance of the lemma, in the context of the construction about to be presented, is that it allows the role of an n-bit counter to be taken by a cyclic permutation group of small degree.

Nota al margen.

Una pregunta relevante en MathoverflowYou’re given a non-singular n×n matrix over F2and asked to determine whether it can be reduced to the identity using at most m Gaussian row operations….The question can be reformulated as asking for the length of the shortest path between two vertices in a certain Cayley graph. (NB, that doesn’t make it polynomial-time because the number of vertices in the graph is exponential.) I’d be just as happy to be told that the same problem in a different Cayley graph was probably of intermediate complexity: I chose the Gaussian elimination example because I happen to like that graph

Nótese que aquí se pregunta por un grupo en concreto con un conjunto de generadores en concreto (las operaciones de columna gausianas). Nótese que éste grupo con estos generadores tienen un número infinito de concreciones y por eso tiene sentido preguntarse por la complejidad computacional del problema.

Una de las respuestas hace referencia a los artículos de Goldreich y Jerrum. En la otra comentan:

If one relaxes the question to asking the row-reduction distance of arbitrary matrices over F2 then it can be shown that the problem is NP-Complete. That is, consider

RRD (Row Reduction Distance):

Input: m×n matrices M, N over F2, and an integer k

Output: Whether M can be row-reduces to N in k steps

The claim is that this problem RRD is NP-complete. It is within NP, so the hardness is all that remains. To do this, consider the following related problem.

MHW (Min Hamming Weight):

Input: PFm×>n2, bFn2, integer k

Output: Is b expressible as a linear combination of k rows of P.

I’ll first show that MHW reduces to RRD, then show that RRD is NP-hard. This together will show RRD is NP-hard.

On the Inherent Intractability of Certain Coding Problems.

The input must be encoded into a binary string of length N, for example, and fed into a deterministic computing machine, which outputs 0 when the input does not have the property and 1 when it does. If there is such a device for which the time for this computation is bounded by a polynomial in N, the problem is in P; otherwise it is not.

Desconozco si la persona que hizo la pregunta quedó satisfecha con las respuestas. Yo mientras estaba trabajando en mi problema en todo momento pensé que los problemas relacionados con los dígrafos de Cayley bigenerados tenían que ser NPI y por eso me llevé la primera sorpresa. Confieso que a mi no me ha resuelto la duda (que ha planteado éste investigador). Entiendo que no puede ser un problema completo para ninguna clase.

Fin de nota al margen.

Comentarios.

Por todo ésto pienso, de momento, que el tamaño del input que se considera en éste artículo de Jerrum (y en el de Goldreich y Even) es el grado de la permutación (pero no estoy 100% seguro, sólo casi seguro). En la descripción de David Johnson queda claro que la lista de generadores forma parte del input. Normalmente estarán dados en forma de permutaciones y estas se codificarán en binario (o unario según el caso). En cualquier caso, esto nos lleva a considerar el grado de las permutaciones como parámetro clave del input. Pregunta: ¿ Que pasa si el número de generadores es exponencial con respecto al grado de las permutaciones ?. La pregunta se refiere al número mínimo de generadores. En general responder preguntas sobre el mínimo número mínimo de generadores no es sencillo. No es sencillo salvo que te apellides ¡¡ Jerrum !!

Let G be a permutation group of degree d. Then d(G) ≤ d, con d = grado de la permutación. 

Se puede mejorar para casos especiales(los siguientes teoremas ya no son de Jerrum):

Let G be a permutation group of degree d. Then d(G) ≤ d/2, except that d(G) = 2 when d = 3 and G ∼= S3. Furthermore, if G is transitive and d ≥ 5, then d(G) < d/2, unless d = 8 and G ∼= D8 ◦ D8.

Let G be a primitive permutation group of degree d. Then d(G) ≤ Raiz cuadrada [log2 (d)].

There exists a constant c1 such that whenever G is a nilpotent transitive permutation group of degree d ≥ 2, then d(G) ≤ c1d/ Raiz Cuadrada [p log2 d]. c1 constante. 

There exists a constant c2 such that whenever G is a soluble transitive permutation group of degree d ≥ 2, then d(G) ≤ c2d/ Raiz Cuadrada [log2 d].

Ver también

–Los casos tratables que considera son los siguientes.

Section 3 aims to explore the finer structure of MINIMUM GENERATOR SEQUENCE by investigating some special cases of the problem which are in P. In addition to the single generator problem referred to above, five instances of the problem are considered, in which the set of generators is taken to be:

(i) all transpositions on the set {1, 2,…, n}, (Let n >= 2. (Recordamos que hay Combinaciones (n,2) transposiciones en Sn, es decir, n!/2!(n-2)!). 

(ii) all 3-cycles, together with all disjoint pairs of transpositions,

(iii) all 3-cycles,

(iv) all adjacent transpositions (i.e., the permutations (1, 2), (2, 3),…, (n – 1, n) on the set {1, 2,…, n}),

(v) all cyclicly adjacent transpositions (i.e., the generator set of (iv) together with the single transposition (1, n)).

It is well known that (i), (iv), and (v) generate the symmetric group on n letters, whereas (ii) and (iii) generate the alternating group.

In each of the five cases it is shown that minimum length expressions of arbitrary group elements in terms of the generators can be computed in time polynomial in n. Cases (i)-(iii) can be handled quite straightforwardly, while case (iv) is dealt with by counting ‘inversions’. A priori, one might expect case (v) to be easier to deal with than case (iv) (after all, it has greater symmetry); however, the converse seems to hold. The solution to case (v), forms the main content of Section 3. Further positive results concerning minimum length generator sequences have been obtained by Driscoll and Furst [14].

En todos estos casos el grado del dígrafo es bastante elevado y por lo tanto dudo que se utilice en la práctica como redes de interconexión, incluso aunque su diámetro no fuese exponencial. Por otra parte  el comentario que hemos señalado en rojo aplica pues lo único que quiere decir es que existen casos en los que el problema no es intratable, y la prueba son los casos tratables de Jerrum. Puede haber otros.

En cuanto a si el diámetro de un Digrafo de Cayley es exponencial o no, depende de lo que se tome como tamaño del Input (ver punto  5).

c)  Más casos tratables.

El paper de Driscoll y Furst que citan en el anterior, que no conocía, que es informativo por si  mismo y relevante para el problema del  camino más corto, es el siguiente.

Título. On the diameter of permutation groups.

Autores. James Richard. Driscoll Carnegie Mellon University Merrick Lee Furs

Abstract.  We show that any group represented by generators that are cycles of bounded degree has 0(n^2) diameter, i.e., that the longest product of generators required to reach any permutation in the group is 0(n^2 ) . We also show how such “short” products can be found in polynomial time. The techniques presented are applicable to generalizations of many permutation-group puzzles such as Alexander’s Star and the Hungarian Rings.

Lo estoy leyendo y luego comentaré.

También se debe de leer

1984. Permutations of bounded degree generate groups of polynomial diameter

ABSTRACT Given an arbitrary permutation h and a set of permutations generating a permutation group G, does h belong to GΦ This question can be answered in polynomial time on a deterministic Turing machine, but its parallel complexity is unresolved. We are concerned here with the length of a shortest expression for h∈G as a product of the permutations generating G.

Autor. Pierre McKenzie: Info. Proc. Lett. 19 (1984), 253–254

3. La cuarta sorpresa: casi todos (almost all) los Grafos de Cayley bigenerados (más inversos) son tratables. 

Ésta es la cuarta sorpresa y me la acabo de llevar aproximadamente a las 8 de la tarde de hoy viernes 19 de junio de 2015. Estaba buscando alguna versión completa del artículo de Goldreich y por el camino me he encontrado con otros artículos interesantes. Algunos los he hojeado y la sorpresa me la he llevado en uno de ellos. No tras leer el resultado sino un poco más tarde mientras descansaba del largo día. He caído en la cuenta que era un resultado muy sorprendente (obviamente para mi).

Empezamos con un primer artículo, del  tipo survey, que no es el que contiene la sorpresa.

1990 /1992.

Título. On the diameter of finite groups.

Autores. Babai et all.

The diameter of a group G with respect to a set S of generators is the maximum over g E (elemento de) G of the length of the shortest word in S U (unión) S^-1 representing g. This concept arises in the contexts of efficient communication networks and Rubik’s cube type puzzles. “Best” generators (giving minimum diameter while keeping the number of generators limited) are pertinent, to networks, “worst” and “average” generators seem a more adequate model for puzzles. We survey a substantial body of recent work by the authors on these subjects.

Regarding the “best” case, we show that while the structure of the group is essentially irrelevant if IS1 is allowed to exceed (log |G|)^1+c (c > 0), it plays a heavy role when 1.51 = O(1). In particular, every nonabelian finite simple group has a set of 5 7 generators giving logarithmic diameter. This cannot happen for groups with an abelian subgroup of bounded index. –

Regarding the worst case, we are concerned primarily with permutation groups of degree n and obtain a tight

exp((n lnn)^1/2 (1 + o(1)))

upper bound.

In the average case, the upper bound improves to

exp((ln n) ^1/2 (l + o(1))).

As a first step toward extending this result to simple groups other than An, we establish that almost every pair of elements of a classical simple group G generates G, a result previously proved by J. Dixon for An. In the limited space of this article, we try to illuminate some of the basic underlying techniques.

Es un artículo muy interesante. El lector debe de tener precaución pues a veces expresa los resultados en función del orden del grupo y a veces en función del grado de la permutación.

Anterior de los  mismos autores. L. Babai and A. Seress. On the diameter of Cayley graphs of the symmetric group. J. Combin. Theory Ser. A, 49(1):175–179, 1988.

El siguiente es el que contiene la sorpresa. Es de uno de los varios autores del anterior, un autor que recientemente ha recibido un premio importante y habla de mi grupo preferido: el grupo simétrico.
2005. 
Near-independence of permutations and an almost sure polynomial bound on the diameter of the symmetric group
Autores. Babai y Hayes.
Abstract (parte). We address the long-standing conjecture that all permutations have polynomially bounded word length in terms of any set of generators of the symmetric group Sn. This is equivalent to polynomial-time (O(n^c)) mixing of the (lazy) random walk on Sn where one step is multiplication by a generator or its inverse. We prove that the conjecture is true for almost all pairs of generators. Specifically, our bound is O(n^7) (ojo es una O con tilde del tipo ñ). For almost all pairs of generators, words of this length representing any given permutation can be constructed in Las Vegas polynomial time. The best previous bound on the word length for a random pair of generators was n ^(ln n(1/2+o(1))) (Babai–Hetyei, 1992).
Extracto.
Regarding random pairs of generators, Dixon’s classical result states that almost all pairs of permutations in Sn generate either Sn or An [9] (cf. [8, 2]). The main result of the present paper shows that the generation a.a. leads to polynomial diameter:
Theorem 2.2. For almost all pairs of permutations S = {σ, τ} of G = Sn or An, the diameter of the Cayley graph Γ(G, S) is bounded by O(n^C) where C is a constant. (Our current estimate of C is 7 + o(1).) The best previously known bound for almost all pairs of generators was n^ln n(1/2+o(1))
Nota. El resultado se refiere a grafos. He visto que define el grado de una permutación de manera diferente a la habitual.
La sorpresa en este caso es la cota Oñ(n^7). Interpreto éste resultado como que casi todos los Dígrafos de Cayley bigenerados son bastante equilibrados, en el sentido de que no tienen parámetros (los que se pueden definir de acuerdo con los resultados de nuestras investigaciones) extremos. No tengo claro que implicaciones tiene ésto desde el punto de vista práctico: un grado 7 no parece muy práctico….
4. La segunda sorpresa. Casi todos los dígrafos de Cayley bigenerados del grupo simétrico y alternado son similares a una esfera (yo me entiendo).
El autor que publicó el resultado es un autor que ha escrito mucho últimamente (en la última década) sobre el problema del diámetro de los grupos de permutaciones. La lectura de uno de sus artículos nos puede dar una idea de la situación actual sobre el problema del diámetro de los grupos de permutaciones.
2011.
On the diameter of permutation groups
Autores: HARALD A. HELFGOTT AND AKOS SERESS
Abstract.
Given a finite group G and a set A of generators, the diameter diam(Γ(G, A)) of the Cayley graph Γ(G, A) is the smallest ℓ such that every element of G can be expressed as a word of length at most ℓ in A ∪ A −1 . We are concerned with bounding diam(G) := maxA diam(Γ(G, A)).
It has long been conjectured that the diameter of the symmetric group of degree n is polynomially bounded in n, but the best previously known upper bound was exponential in √ n log n.
We give a quasipolynomial upper bound, namely, diam(G) = exp O((log n) 4 log log n) = exp (log log |G|) O(1) for G = Sym(n) or G = Alt(n), where the implied constants are absolute. This addresses a key open case of Babai’s conjecture on diameters of simple groups. By a result of Babai and Seress (1992), our bound also implies a quasipolynomial upper bound on the diameter of all transitive permutation groups of degree n. 
Extracto.
As far as work in this vein on the diameter of finite simple groups is concerned, the best results to date are those of Pyber, Szabo [PS] and Breuillard, Green, Tao [BGT11]. Their wide-ranging generalisation covers all simple groups of Lie type, but (just like [GH11]) the diameter estimates retain a strong dependence on the rank; thus, they prove Conj. 1 only for groups of bounded rank. The problem for the alternating groups remained wide open.
In the present paper we address the case of alternating (and symmetric) groups. We expect that some of the combinatorial difficulties we overcome will also arise in the context of linear groups of large rank.
No se si es éste paper el que contiene el resultado que originó la segunda sorpresa.  Sí sé que el autor es el mismo, Helfgott y que en su momento hicimos una entrada al respecto (cuando  la recupere actualizaré ésta). Tras esa sorpresa dejé de investigar sobre éstos temas, pues prácticamente me quedaron aclaradas todas las dudas.
Realmente es una suerte que éste campo haya contado con investigadores de la categoría de los nombres que aparecen como autores y en las bibliografías. No lo  digo sólo yo, lo dice también el autor de uno de los artículos que hemos consultado y sobre el que hablaremos en el P.s. de la entrada. Y en la cita le faltan unos cuantos nombres (sin ánimo de ser exhaustivo pienso en Erdos, en Landau, en Dixon, en Cameron y tantos otros; estoy citando los nombres de aquellos que no habiendo trabajado directamente en el problema de recorridos hamiltonianos tienen resultados o publicaciones que nos han sido útiles, que hemos utilizado).
The mathematical problems supporting the security properties of Cayley hash functions have a rich history in mathematics, if not in cryptography. They originate at least in the work of Babai in the late eighties and in particular to its conjecture on the diameter of the Cayley graphs of finite non-Abelian simple groups. The research on these problems has been very active and has involved distinguished mathematicians such as Babai, Bourgain, Gamburd, Green, Helfgott, Kantor, Lubotzky, Tao,…. Nevertheless, with the exception of permutation groups, very few instances have been solved today after twenty years.
Realmente, hasta hace poco, no sabía que algunos de éstos investigadores habían trabajado en éste tipo de problemas…
Entonces ¿ cual es la situación actual del problema del diámetro ?. El principal resultado del artículo de Helfgott al que hemos enlazado es:
Main Theorem. Let G = Sym(n) or Alt(n). Then diam(G) ≤ exp( O((log n) 4 log log n)), where the implied constant is absolute.
Queda claro  que n es el grado de las permutaciones. Los otros dos resultados son:
Corollary 1.2. the diameter of any transitive permutation group G of degree n is diam(G) ≤ exp O((log n) 4 log log n).
y, a continuación pasa de Grafos de Cayley a dígrafos.
Finally, the Main Theorem and Cor. 1.2 extend to directed graphs. Given G = hAi, the directed Cayley graph ~Γ(G, A) is the graph with vertex set G and edge set {(g, ga) : g ∈ G, a ∈ A}. The diameter of ~Γ(G, A) is defined by (1.1), where “path” should be read as “directed path”; −−−→diam(G) is the maximum of diam(~Γ(G, A)) taken as A varies over all generating sets A of G. Thanks to Babai’s bound −−−→diam(G) = O diam(G) · (log |G|) 2 [Bab06, Cor. 2.3], valid for all groups G, we obtain immediately from Cor. 1.2 that
Corollary 1.3. Let G be a transitive group on n elements. Then −−−→diam(G) ≤ exp(O((log n)^4  log log n)).
Por lo tanto la cota superior del diámetro de los Dígrafos de Cayley de grupos de permutaciones transitivos es cuasipolínómico en el peor caso. Quede claro que el que sepamos que estos son los diámetros, no implica que nos sea, en general, fácil resolver el problema del camino más corto, al igual que aunque sepamos que cualquier número natural tiene una factorización única, no implica  que nos sea fácil encontrarla. De hecho los casos más complicados de factorizar en naturales son aquellos que tienen dos factores.
¿ Y con respecto a los grupos de permutaciones no transitivos (concepto, que según aprendo acuñó Ruffini), cual es su diámetro ? Recordamos que  un grupo intransitivo es aquel que parte el conjunto de elementos a permutar en varias partes disconexas, de tal manera que un elemento que se encuentra en una parte no sale de allí.
Un artículo de Helfgott recién salido del horno (febrero de 2015) nos lo aclara.
GROWTH IN GROUPS: IDEAS AND PERSPECTIVES
HARALD A. HELFGOTT In memory of Akos Seress (1958–2013) ´
Abstract. This is a survey of methods developed in the last few years to prove results on growth in non-commutative groups. These techniques have their roots in both additive combinatorics and group theory, as well as other fields. We discuss linear algebraic groups, with SL2(Z/pZ) as the basic example, as well as permutation groups. The emphasis will lie on the ideas behind the methods.
Extracto.
Before [HS14], the strongest bound on the diameter of permutation groups was that of Babai and Seress [BS88], who showed that, for any permutation group G on n elements and any A ⊂ G generating G,
diam(Γ(G, A)) ≤ exp((1 + o(1)) n log n).
While this is much weaker than the bound in Theorem 1.4, it does not assume transitivity (and indeed it can be tight for non-transitive groups).
Aquí se refiere a grafos, pero entiendo que el resultado es extensible a dígrafos. Un problema abierto sobre el que habla luego me hace dudar:
Does every Cayley graph Γ(Sym(n), A) (A a set of generators of Sym(n)) have diameter n^O(1)? (This predates Babai’s more general conjecture. Here Theorem 1.4 (as in [HS14]) is the best result to date). 
El teorema 1.4 es el  ya conocido.
Theorem 1.4 (Helfgott and Seress [HS14]). Let G = Sym(n) or Alt(n). Let A be any set of generators of G. Then the diameter of G with respect to A is ≤ exp(O((log n)^4 log log n)), where the implied constant is absolute
Por otra parte también comenta:
it is easy to construct a non-transitive group of very large diameter [BS92, Example 1.2]. (However, if the number of orbits1 is bounded, then the problem reduces to the transitive case.)
El ejemplo 1.2 del artículo de Babai y Seress es el siguiente:
Example 1.2. Let P1, P2, . . . be the sequence of primes and let m(n) be the greatest integer such that P i≤m(n) Pi ≤ n. Let τ ∈ Sn be a permutation consisting of cycles of lengths P1, P2, . . . , Pm(n) . Then diam(Γ(hτ i, {τ})) = P1 · · · Pm(n)/2 = exp((n ln n) 1 2 (1 + o(1))).
(This is immediate from the Prime Number Theorem; cf. Propositions 3.9 and 3.10.)
In the present paper, we examine the “worst case” diameter diam(G) = maxSdiam(Γ(G, S)) for permutation groups. The previous example shows that for some G ≤ Sn the diameter can be as large as exp((n ln n) 1 2 (1 + o(1))).
In [BS2] we have shown that the same quantity is an upper bound for the diameters of Sn and An. The main result of this paper extends this bound to all permutation groups of degree n.
Theorem 1.3. For any G ≤ Sn, the diameter of any Cayley graph of G is ≤ exp(((n ln n)^1/2) (1 + o(1))).
We prove a potentially considerably stronger bound for transitive permutation groups.
Theorem 1.4. If G ≤ Sn is transitive then diam(G) ≤ exp(C log^3 n) · diam(Am(G) ) where C is an absolute constant and m(G) is the degree of the greatest alternating composition factor of G.
Therefore, the bottleneck is the estimation of the diameter of the alternating group. Our upper bound exp((n ln n) 1 2 (1 + o(1))) [BS2] seems far from best possible; in fact the following conjecture seems to be folklore: Conjecture 1.5. diam(An) < nC for some absolute constant C.
En éste otro artículo (nada que ver con Helfgott) nos ponen un ejemplo de un grupo de un generador con diametro 2^O((Raiz cuadrada de n)).
Coordinating Pebble motions in graphs, the diameter of permutation groups and applications.
Actualización 21 de junio 2015.
Cuando uno lee sobre grupos de permutaciones en seguida se da cuenta que no se estudia, que se deja de lado los casos intransitivos.
En esta actualización intento comprender ésto, expresando el problema en los términos en los que estoy más acostumbrado y comprendo mejor: los dígrafos de Cayley. Para mi la teoría de grupos ha sido bastante tangencial. Lo que a mi me interesa es el par de permutaciones (también otras tuplas), el conjunto (grupo de permutaciones que genera), el dígrafo que se genera y los recorridos que se pueden obtener (más cortos y sobre todo los hamiltonianos). Obviamente para cualquiera que trabaje en estos temas la teoría de grupos es de gran utilidad, aunque no fácil de aprender por  sí mismo, debido a la alta abstracción con la que se trabaja: es de las ramas de las matemáticas dónde los ejemplos han desaparecido completamente del mapa….Según he leído esta deriva hacía la abstracción en la comunicación de resultados comenzó en el período de la primera globalización, a partir de 1870. ¿ Profesionalización ?
En fin primer intento de explicación: ponemos un ejemplo con Dígrafos de Cayley de grado 5, generadores 21354 y 23145. Se ve claramente que  dividen el conjunto (identidad) en dos bloques, 123 por un lado y 45 por el otro. Si construimos el Dígrafo de Cayley correspondiente a éstos generadores vemos que es un dígrafo de 6 vértices (que representa a un grupo de orden 6) que es isomorfo al digrafo de Cayley de S3 por los generadores 132 y 231. El lector puede construir ambos en dos minutos y verá gráficamente a que nos referimos.
Entiendo que  de la misma manera, a todo Dígrafo de Cayley Intransitivo generado por permutaciones de grado n se le puede asociar un Dígrafo de Cayley transitivo isomorfo de grado m con m<n. Por lo tanto a efectos de clasificación (que es lo que interesa a los teóricos de grupo), los intransitivos no tienen interés, son redundantes, ya se han estudiado antes como transitivos de menor grado.
Pero a continuación un caso en el que no se puede reducir un caso intransitivo bigenerado a otro bigenerado  de grado menor: grado 8, generadores 23451786 y 21345687. Si he comprendido bien la definición, es intransitivo pero que yo sepa no puede tener grafos isomorfos de grado inferior a 8 (entre otras cosas por el orden del primer generador, de orden 15).
Este caso es un grupo de orden 360 = 2^3*3^2*5. Es igual también a 6!/2 y podría ser un A6 (alternado de grado 6).  Hemos obtenido ésta información sobre el orden gracias a ésta aplicación encontrada en Internet. Y más información sobre los grupos  de éste orden aquíhay 160 grupos de  éste orden.
En retrospectiva estaba claro que estos dos generadores tenían que generar un grupo de 360 elementos: en un bloque un ciclo y una involución (como es conocido), generarn S5. El otro bloque es Z3. S5*Z3=360, que no se si es un grupo válido (entiendo que no por la paridad de la permutaciones).  Es otra manera de verlo. Seguramente se puede generalizar éste caso, y la generalización nos daría una familia infinita de Dígrafos de Cayley tales que no tienen un dígrafo isomorfo de grado inferior.
De paso informamos de los otros parámetros clave del caso: generador 2 orden 2, IAS orden 8 y Circunferencia orden 3.
Aprovechamos para recordamos la definición de circunferencia, que es un parámetro que encontramos en nuestras investigaciones tras solicitud de la primera patente. Si el generador 1=x y el generador 2 =y, (asignación puramente convencional) la circunferencia (se define siempre cuando el IAS es regular), se puede definir como el orden de la permutación p que se obtiene al aplicar a la identidad (=1) la siguiente relación:
–si el IAS es par, 1 (x^-1y)^n/2(xy^-1)^n/2 = p.
–si el IAS es impar, 1 (x^-1y)^(parte entera de (n/2)-1)x^-1  = p. Es decir el orden de la permutación que se encuentra en medio del IAS de la  identidad, con respecto a la identidad. 
con n el número tal que 1 (x^-1y)^n=1. 
¿ Muy abstracto verdad ? Con una explicación en persona se comprendería en do minutos.
Comento también que ya que estoy, voy a poner éste caso a prueba con mi algoritmo / programa, para encontrar si tiene recorridos hamiltonianos (ya adelanto que salvo que sea cycle-entangled, cosa que no se puede descartar, los tiene, por la propia teoría implícita en los resultados de la patente, teoría de la cual se derivan unos tests que el examinador no ha sabido valorar). Hace tiempo que no utilizo el programa, tiene miles de líneas de código, había un par de valores tres valores que había que poner manualmente, uno ya lo he identificado pero el otro me está costando encontrarlo…Mantendré al lector informado sobre ésto. Actualización 22 de junio. Ya he encontrado los tres valores que hay que poner a mano (la cantidad de vértices, una lista de ceros que se corresponda con ésta, son los que aparecen en la matriz que representa al dígrafo, y el vértice final de entre los posibles). Me ha costado primero encontrar en el programa dónde estaba el tercero, la especificación del vértice final posible, y sobre todo, tras fallar el programa (se especificaba 360 vértices y la matriz tenía 120; sin embargo he comprobado que cuando pones 24, aunque la matriz tenga 120 ceros funciona ¿?), recordarme que había unos terceros datos que hay que poner a mano (los ceros) y de nuevo identificarlo. En fin ya está el caso en marcha (14:35) y tardará seguramente como poco un par de horas. Informaré de resultados cuando termine. Ahora veo la ventaja de un multicore…¡¡Encontrado!!. Vértice final 21345876 (hay otros tres posibles más y también tienen RH). Ya había confirmado antes manualmente (lo puedo hacer de manera automática pero se me ha olvidado comprobarlo antes y ya digo que no puedo ejecutar dos programas a la vez) que no era cycle-entangled y por  lo tanto que tenía que tener RH.  Ha tardado un poco más de una hora (hay que tener en cuenta que he navegado por internet en paralelo y eso seguramente le ha restado tiempo.
Ahora tengo que encontrar la parte del programa que dada la matriz que contiene el RH lo  genera como lista e imprimir la lista y copiarla, para que terceras partes lo puedan comprobar con facilidad. Existe pues ya lo hice para la primera solicitud de patente, para casos de 720 vértices, que tardaron bastante más….Encontrado, pero para ejecutarlo tengo que volver a ejecutar el programa. Lo hago pero con otro vértice final. Imprimiré el resultado en unas dos horas (ahora son las 17:02).
Fin de actualización.
¿Relacionado?: The maximal subgroups of the finite symmetric groups fall into three classes: the intransitive, the imprimitive, and the primitive.
–The intransitive maximal subgroups are exactly those of the form Sym(k) × Sym(n − k) for 1 ≤ k < n/2.
–The imprimitive maximal subgroups are exactly those of the form Sym(k) wr Sym(n/k) where 2 ≤ k ≤ n/2 is a proper divisor of nand “wr” denotes the wreath product acting imprimitively.
–The primitive maximal subgroups are more difficult to identify, but with the assistance of the O’Nan–Scott theorem and the classification of finite simple groups, (Liebeck, Praeger & Saxl 1988) gave a fairly satisfactory description of the maximal subgroups of this type according to (Dixon & Mortimer 1996, p. 268).
P.s. Artículos relacionados directa o indirectamente, que he encontrado, a recordar para posteriores entradas.
a1) Libro clásico. Theory of Groups of Finite order. Burnside. 1897
Al parecer Burnside introdujo la teoría de grupos en Inglaterra. Desde hacía más tiempo se estudiaba en Francia o Alemania. Hasta ese momento se estudiaban como objetos concretos (sobre todo como grupos  de permutaciones) y es con el cambio de siglo cuando empiezan a estudiarse de manera más abstracta. He accedido a éste libro para ver si veo ejemplos de grupos intransitivos.
The theory of groups of finite order may be said to date from the time of Cauchy. To him are due the first attempts at classification with a view to forming a theory from a number of isolated facts. Galois introduced into the theory the exceedingly important idea of a self-conjugate sub-group, and the corresponding division of groups into simple and composite. Moreover, by shewing that to every equation of finite degree there corresponds a group of finite order on which all the properties of the equation depend, Galois indicated how far reaching the applications of the theory might be, and thereby contributed greatly, if indirectly, to its subsequent developement. Many additions were made, mainly by French mathematicians, during the middle part of the century. The first connected exposition of the theory was given in the third edition of M. Serret’s “Cours d’Algèbre Supérieure,” which was published in 1866. This was followed in 1870 by M. Jordan’s “Traité des substitutions et des équations algébriques.” The greater part of M. Jordan’s treatise is devoted to a developement of the ideas of Galois and to their application to the theory of equations. No considerable progress in the theory, as apart from its applications, was made till the appearance in 1872 of Herr Sylow’s memoir “Théorèmes sur les groupes de substitutions” in the fifth volume of the Mathematische Annalen. Since the date of this memoir, but more especially in recent years, the theory has advanced continuously. In 1882 appeared Herr Netto’s “Substitutionentheorie und ihre Anwendungen auf die Algebra,” in which, as in M. Serret’s and M. Jordan’s works, the subject is treated entirely from the point of view of groups of substitutions. Last but not least among the works which give a detailed account of the subject must be mentioned Herr Weber’s “Lehrbuch der Algebra,” of which the first volume appeared in 1895 and the second in 1896. In the last section of the first volume some of the more important properties of substitution groups are given. In the first section of the second volume, however, the subject is approached from a more general point of view, and a theory of finite groups is developed which is quite independent of any special mode of representing them.
a2) Seguimos con los clásicos. George Miller (1863-1951). Se trata de un matemático de EEUU que trabajó mucho sobre grupos de permutaciones.
Miller spent the years from 1895 to 1897 in Europe attending lectures on group theory by Lie in Leipzig and Jordan in Paris. On his return to the United States Miller was appointed assistant professor at Cornell University. He held this position from 1897 until 1901 when he was appointed to Stanford University. In 1906 he moved from Stanford to the University of Illinois at Urbana-Champaign where he remained for the rest of his career.

Miller worked mostly on group theory but he was also interested in the history of mathematics. Although interesting because it was done at an early stage, his work fails to show much depth. He wrote more than 800 articles over a period of 40 years about half at research level, the others aimed at school teachers. His collected works appear in five volumes: the first contains 62 papers which Miller published before 1900; the second contains 107 of the 147 papers he published during the years from 1900 to 1907; the third includes 89 of the 180 papers he published during the years 1908 to 1915; the fourth contains 98 of the 232 papers he published during the period 1916 to 1929.

Many of Miller’s group theory papers enumerate the possible finite groups which satisfy given conditions such as: the prime factors which divide the order, the orders of two generating permutations and their product; the types of subgroups; or the degree of a representation as a permutation group. Several papers investigate groups generated by two elements satisfying given conditions. For example he considered groups generated by two elements of order three whose product is of order four or three or six. He also considered permutation groups of small degree, groups having a small number of conjugacy classes, multiply transitive groups, and characteristic subgroups of finite groups. He found the list of all possible groups of order 1909 to 1919 inclusive. Miller did not introduce new techniques to attack these group theory questions and one is tempted to say that he should have applied his undoubted skills to produce fewer yet more significant results.

Ésto explica que en una búsqueda sobre grupos intransitivos, casi todas las entradas sean de éste prolífico autor.
Relacionado (curiosidad). Un clásico sobre los clásicos de la teoría de grupos.
The foundation period in the history of the theory of groups (1911). Una linea sobre Abel y un muy pequeño apartado sobre Galois. Tras éstos y otros precusores, se veía a Cauchy como el verdadero fundador de la teoría de grupos. Curiosamente hoy vemos ésto de manera muy diferente.
a3) Algoritmos paralelos para grupos de permutaciones.
a4) On transitive permutation groups. ¿2004?. Conway, Hulpke, McKay.
¡¡¡ Muy interesante !!!. “Catálogo” que contiene detalle de todos  los grupos transitivos hasta el grado 15, incluyendo para cada uno de ellos generadores en forma de permutaciones (no necesariamente mínimos: he visto que no bigeneran algún An).
Como es bien conocido, Conway es uno de los autores del Atlas de Grupos Finitos.
a5) Número de grupos transitivos de grado 32.
The transitive permutation groups of degree 32.
Dado un grado encontrar todos los grupos no isomorfos no es sencillo. Este artículo se escribió en ¿ 2008 ?  y comentan:
We have not yet seriously considered the problem of calculating lists of transitive permutation groups of higher degree. We would hazard a guess that for degrees between 33 and 64, 36 and 48 would be very difficult but potentially possible, degree 64 would be impossible with current techniques and resources, and the other degrees would be comparatively straightforward.
Creo que está claro por qué el problema no es sencillo (sobre todo si el único método es la fuerza bruta: la cantidad de combinaciones que hay que probar ya es brutal con el grado 32).
Here, we report on our recent computation of a complete list of representatives of the conjugacy classes in Sym(32) of the transitive groups of degree 32. There are 2 801 324 such classes. The magnitude of this number in comparison with smaller degrees (the largest such is 25 000 classes of transitive groups of degree 24) had already been anticipated by Hulpke, who perceived this a disincentive to extending his lists to degree 32
¿ Existe alguna fórmula para calcular el número de grupos que se corresponde  a un grado ? Creo recordar que no existe y que una acotación tampoco es sencilla.
We discuss the methods used in Section 2. We used two different methods, which we shall call the brute force method and the Hulpke method, depending on the smallest size of a block in a block system preserved by the group. 
Cuales son los resultados:
there are 487 distinct orders of groups in the final list,
–2 737 535 of the 2 801 324 groups – that is, about 97.7% of them – are 2-groups of order 2n for 5 ≤ n ≤ 31
the most popular order being 215, of which there are 391 809 groups.
–Only 1051 of the groups are insoluble.
–All except 8295 of the groups – that is, about 99.7% of them – are imprimitive groups with a block system with blocks of size 2.
–We observe also that 11605 of the groups in the list are minimally transitive; that is, all of their proper subgroups are intransitive.
Los grupos intransitivos se pueden obtener como productos de grupos transitivos de grado inferior.  Aunque no lo tengo claro, diría que dado un grado el número de grupos intransitivos es una minoría.
b1) Algoritmos para el problema del camino más corto en Dígrafos de Cayley. 
Es posible que haya un spin-off de éste punto más adelante. Éste tema me interesa, tenía una propuesta basada en las técnicas de la patente que fui publicando en el blog en su momento (no recuerdo por qué dejé de investigar sobre ésto en su momento, tengo que releer las entradas).
Pero realmente nunca estudié que algoritmos constituyen el estado del arte (y reconozco que tenía que haber empezado por ahí) y es lo que voy a hacer ahora.
On the diameter of Eulerian orientations of graphs Laszlo Babai. No es algorítmico pero es relevante.
–más que el problema del camino más corto, el problema que se ha estudiado más es el problema relacionado del diámetro, y todavía más el problema grado (del grafo) / diámetro. Una publicación reciente (2014) al respecto: Algebraic and computer-based methods in the undirected degree/diameter problem – A brief survey. Abstract This paper discusses the most popular algebraic techniques and computational methods that have been used to construct large undirected graphs with given degree and diameter.
b2) Grafos de Cayley y criptografía.
Hace poco hablábamos de un artículo de un investigador de la NSA (desclasificado en 2011) cuyo principal  resultado consistía en identificar el problema del camino más corto en Dígrafos con el problema de factorización en grupos.
Nota al margen. No tengo claro que el nombre de factorización aplicado al concepto al que lo aplica éste autor sea el más adecuado. Si se puede definirir una multiplicación de naturales, también se puede definir una multiplicación de permutaciones (de hecho la segunda contiene a la primera como restricción). Si el problema de factorización de enteros es dado un orden de un grupo, encontrar el orden de las permutaciones que lo han generado al ser multiplicadas, de las misma manera se puede definir el mismo problema para grupos de permutaciones (no  necesariamente commutativas). ¿ Existe alguna relación entre las dos factorizaciones (la del camino más corto y la que comento) que yo desconozca ?. Fin de nota.
Un artículo de la AMS escrito por Petit y Quisquater que relaciona determinados problemas de criptografía con los problemas sobre los que hemos hablado en los anteriores puntos.
Título.  Rubik’s for Cryptographers. Junio 2013.
Extractos.
Presumably hard mathematical problems stand at the core of modern cryptography. A typical security proof for a cryptographic protocol relates its resistance against a particular attack to the hardness of some mathematical problem. Very few problems have survived thorough cryptanalysis, the most established ones being the integer factorization problem and the discrete logarithm problems on finite fields and elliptic curves. Other problems have been suggested, related, for example, to hyperelliptic curves, lattices [42], error-correcting codes [31], or multivariate polynomial equations [35] (the so-called postquantum cryptographic algorithms). They are currently less trusted than the three previous ones, but they might join or replace them in the future.
In this paper we discuss three alternative computational problems: namely the balance, representation, and factorization problems in finite non-Abelian groups. 
For the cryptographic applications to be secure, the balance, representation, and factorization problems must be computationally hard. These problems are of course easy for the Rubik’s Cube. They are also easy in a few other particular cases, but they may still be hard in general. In fact, they are strongly connected to famous problems in group theory and can be seen as algorithmic versions of a twenty-year-old conjecture of Babai on the diameters of Cayley graphs. Although the conjecture is now proved for all parameters of interest in cryptography, many of the proofs are nonconstructive, hence useless, to “break” the functions
Ésto último es equivalente al problema de factorización de enteres. Sabemos que existe pero no es sencillo encontrarla.
In the last twenty years, the cryptography community (for Cayley hash functions) and the mathematics community (for Babai’s conjecture) have been working independently on very similar problems. The goal of this paper is to bridge the results obtained by the two communities, with the cryptographic application in mind. In particular, we review known results coming from both sides, we provide some general attacks and design principles for the Cayley hash function construction, and finally we propose some parameters that can be considered as “safe” from our current knowledge of these problems.
El uso de estos problemas sobre Grafos de Cayley para criptografía se inició por Zémor (Hash Functions and Graphs with high Girth. 1991). Tras ser criptoanalizado, este mismo autor conjuntamente con Tillich realizaron una nueva propuesta (Hashing with SL2. 1994). En 2009 Charles et al redescubrieron la aplicación Cryptographic Hash Functions from Expander Graphs. De momento parece más bien una propuesta que no ha pegado el salto a las aplicaciones reales.
In the last twenty years, the cryptography community (for Cayley hash functions) and the mathematics community (for Babai’s conjecture) have been working independently on very similar problems. The goal of this paper is to bridge the results obtained by the two communities, with the cryptographic application in mind. In particular, we review known results coming from both sides, we provide some general attacks and design principles for the Cayley hash function construction, and finally we propose some parameters that can be considered as “safe” from our current knowledge of these problems.
En éste paper nos aclaran que la investigación sobre el problema del camino más corto  y del diámetro en éste tipo de dígrafos se relanzó en 2005 por  un resultado de Helfgott, que aparentemente no se publicó hasta 2008: Growth and generation in SL2(Z/pZ), Ann. of Math. (2) 167 (2) (2008), 601–623. Pensamos que la fecha de 2005 debe de ser un error y la fecha real es 2008.
While cryptographers have been trying to break Cayley hash functions, mathematicians have studied the diameter of Cayley graphs and tried to prove Babai’s conjecture. The conjecture has been proved for almost all sets of generators in symmetric and alternating groups by Babai and Hayes [5]. The proof is constructive, hence permutation groups must be avoided in cryptographic applications (see also [23]).
No entiendo muy bien por qué la mención de las permutaciones. Por el teorema de Cayley se sabe que todo grupo finito se puede expresar como grupo de permutaciones. ¿ Acaso para pasar de un grupo de permutaciones a otro tipo de expresión la transformación es compleja ?
Relacionado. Group Theoretic Cryptography. By Maria Isabel González Vasco, Rainer SteinwandtChapman and Hall/CRC – 2015 – 244 pages
–c) Una curiosidad.
Está citado en alguno de los artículos anteriores y según he visto efectivamente hablan de los grupos de permutaciones, pero desconozco que relación tienen con los POMDP (Partially Observed Markov Deterministic Process), que se han utilizado en Inteligencia Artificial. No he conseguido determinar el año.
Departamento de Computación
Universidad Simón Bolívar

Caracas, Venezuela

d) relevante para los sistemas RH.
THE FORWARDING INDICES OF GRAPHS – A SURVEY Jun-Ming Xu and Min Xu Communicated by Gyula O.H. Katona
Abstract. A routing R of a connected graph G of order n is a collection of n(n − 1) simple paths connecting every ordered pair of vertices of G. The vertex-forwarding index ξ(G, R) of G with respect to a routing R is defined as the maximum number of paths in R passing through any vertex of G. The vertex-forwarding index ξ(G) of G is defined as the minimum ξ(G, R) over all routings R of G. Similarly, the edge-forwarding index π(G, R) of G with respect to a routing R is the maximum number of paths in R passing through any edge of G. The edge-forwarding index π(G) of G is the minimum π(G, R) over all routings R of G. The vertex-forwarding index or the edge-forwarding index corresponds to the maximum load of the graph. Therefore, it is important to find routings minimizing these indices and thus has received much research attention for over twenty years. This paper surveys some known results on these forwarding indices, further research problems and several conjectures, also states some difficulty and relations to other topics in graph theory.
e) Grafos de Cayley y Grafos de Kautz.
Recordamos que los Dígrafos de Kautz se utilizaron como modelo para la red de interconexión de los supercomputadores de la empresa SiCortex. También recordamos que ésta empresa no duró mucho en el mercado, pero que sus activos IP fueron comprados en parte por Cray.
Explicit Cayley covers of Kautz digraphs. 2011.
Josep M. Brunat∗ Departament de Matem`atica Aplicada II Universitat Polit`ecnica de Catalunya Josep.M.Brunat@upc.edu Submitted: Mar 3, 2010; Accepted: Apr 27, 2011; Published: May 8, 2011 Mathematics Subject Classifications: 05E18, 05C25, 05C20
Abstract
Given a finite set V and a set S of permutations of V , the group action graph GAG(V, S) is the digraph with vertex set V and arcs (v, vσ ) for all v ∈ V and σ ∈ S. Let hSi be the group generated by S. The Cayley digraph Cay(hSi, S) is called a Cayley cover of GAG(V, S). We define the Kautz digraphs as group action graphs and give an explicit construction of the corresponding Cayley cover. This is an answer to a problem posed by Heydemann in 1996.
Extracto.
The idea of associating a Cayley digraph to a non-symmetric digraph in such a way that the properties of one gives information about the other has been frequently used.
For instance,
–Fiol et al. [7, 8, 9] have shown that, in the context of dynamic memory networks, the idea of associating a Cayley digraph on a permutation group on the set of vertices of the network plays a central role in a unified approach to the topic.
–The idea of symmetrization of a digraph is used by Espona and Serra in [6] to construct Cayley covers of the de Bruijn digraphs,
–and by Mansilla and Serra in the context of k-arc transitivity [15, 16].
–The group action graphs defined by Annexstein et al. in [2], give a way to associate to each non-symmetric digraph a number of Cayley graphs.
The de Bruijn and Kautz digraphs are the iterated line digraphs from the complete digraph with and without loops, respectively [10]. They are dense digraphs, and they have high connectivity, and many other good properties [3]. But, in general, they are not symmetric.
Serra and Fiol have calculated the permutation groups of the de Bruijn digraph [18]. From them, an explicit construction of the Cayley digraph associated to the de Bruijn digraphs as group action graphs is known.
For Kautz digraphs K(d, n), it is known for which values of d and n they are Cayley digraphs (see [4]), and, in the case that d + 1 is a prime number, Mansilla and Serra [15] gave an explicit construction of the corresponding Cayley digraph. 
The problem 47 posed by Heydemann in [13], consists in giving an explicit construction of the Cayley digraph associated to the Kautz digraphs K(d, n) considered as group action graph. Our goal here is to solve this problem for all values of d and n
f) Grafos vértice transitivos No Cayley.
Non-Cayley Vertex-Transitive Graphs of Order Twice the Product of Two Odd Primes

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: