Complejidad computacional. Isomorfismo de grafos en tiempo cuasi-polinómico (2). Las novedades, o lo que hay de nuevo en el resultado de Babai.

  1. Ya hay algo más de información aunque todavía no hay un artículo publicado. Tenemos:

–la secuencia de tweets o twits (no se cual es la forma correcta de escribir esta palabra) que ni los expertos se atreven a descifrar y,

esta entrada en reddit recién salida del horno, escrita por alguien que también asistió a la conferencia, que seguramente es experto en el problema de isomorfismo de grafos y que personalmente encuentro más informativa que la secuencia de twits, ya que nos resume loque hay de nuevo. Obviamente mucho más  informativo es la combinación de las dos fuentes.

–y una entrada en un blog de otro asistente a la conferencia que da bastante más detalles (ver actualización; aunque no me he enterado de mucho, este bloguero ha realizado un gran trabajo para explicar la conferencia).

No hace falta decir que también se han hecho eco ampliamente del tema los blogs que tratan habitualmente sobre complejidad computacional, que el lector conoce seguramente de sobra.

Extractos de la entrada de reddit y del enlace que aparece en la actualización.

The algorithm followed previous work on the topic, with the bulk of the work focused towards eliminating known barriers to solutions (basically, the problems caused by Johnson Graphs).

1) The first lemma is a very cool combinatorial lemma about the structure of graphs which can be converted into a criterion for when a graph is “basically” a canonical representation of a Johnson Graph. This will definitely see further application, and I’m pretty sure it’s applicable to a problem I’m working on currently.

De la tercera fuente citada en la actualización.

Theorem (Babai 15): If X is a regular graph on m vertices, then by individualizing a polylog number of vertices we can find one of the three following things:

  1. A canonical equitable partition with each block having at most 90% of all the nodes.
  2. A canonical equitable partition with some block having at least 90% of the nodes.
  3. A canonically embedded Johnson graph on at least 90% of the nodes.

The first two are apparently the “easy” cases in the sense that they allow for simple recursion that has already been known before Babai’s work. The hard part is establishing the last case (and this is the theorem whose proof sketch he has deferred for two more weeks). But once you have such a Johnson graph your life is much better, because (for a reason I did not understand) you can recurse on a problem of size roughly the square root of the starting size.

In discussing Johnson graphs, Babai said they were a source of “unspeakable misery” for people who want to solve GI quickly. At the same time, it is a “curse and a blessing,” as once you’ve found a Johnson graph embedded in your problem you can recurse to much smaller instances. This routine to find one of these three things is called the “split-or-Johnson” routine.

The analogue for strings (I believe this is true, but I’m a bit fuzzy on this part) is to find a “canonical” k-ary relational structure (where k is polylog in size) with some additional condition on the size of alternating subgroups of the automorphism group of the k-ary relational structure. Then you can “individualize” the points in the base of this relational structure and find analogous partitions and embeddedJohnson schemes (a special kind of combinatorial design).

2) The second lemma is a lemma in group theory about substructures of permutation groups that hopefully I’ll understand when he talks about it Thursday. He was a bit rushed at this point and didn’t explain it much. This lemma is apparently reliant on the Classification of Finite Simple Groups.

En el enlace de la actualización también desarrollan este punto.

The second crucial lemma has to do with giant homomorphisms, and this is the method by which Babai constructs automorphisms that bound \textup{Aut}_G(x) from below. As opposed to the split-or-Johnson lemma, which finds structure to bound the group from above by breaking it into simpler pieces. Fair warning: one thing I don’t yet understand is how these two routines interact in the final algorithm. My guess is they are essentially run in parallel (or alternate), but that guess is as good as wild.

Definition: A homomorphism \varphi: G \to S_m is called giant if the image of G is either the alternating group A_n or else all of S_m. I.e. \varphi is surjective, or almost so. Let \textup{Stab}_G(x) denote the stabilizer subgroup of x \in G. Then x is called “affected” by \varphi if \varphi|_{\textup{Stab}_g(x)} is not giant.

To recall, we started with this assumption that \textup{Aut}_G(x) was the entire symmetry group we started with, which is in particular an assumption that the inclusion \varphi \to S_m is giant. Now you want to refute this hypothesis, but you can’t look at all of S_mbecause even the underlying set m has too many subsets to check. But what you can do is pick a test set A \subset [m] where |A| is polylogarithmic in size, and test whether the restriction of \varphi to the test set is giant in \textup{Sym}(A). If it is giant, we call A full.

Theorem (Babai 15): One can test the property of a polylogarithmic size test set being full in quasipolynomial time in m.

Babai claimed it should be surprising that fullness is a quasipolynomial time testable property, but more surprising is that regardless of whether it’s full or not, we can construct an explicit certificate of fullness or non-fullness. In the latter case, one can come up with an explicit subgroup which contains the image of the projection of the automorphism group onto the symmetry group of the test set. In addition, given two test sets A,B, one can efficiently compare the action between the two different test sets. And finding these non-full test sets is what allows one to construct the k-ary relations. So the output of this lower bound technique informs the upper bound technique of how to proceed.

Diría que este último resultado es la clave.

4) Babai does not think that Graph Isomorphism is contained within P, due to the fundamental role that Johnson graphs play, and because he does not think one can handle the “hard” johnson graph cases efficiently enough for combinatorial and group theoretic reasons

Lo nuevo es por lo tanto lo indicado en los puntos 1 y 2. El metacomentario del punto 4 es muy interesante. Me pregunto si solo excluye P en relación a sus métodos o en términos absolutos, en relación a cualquier método posible. En la actualización nos aclaran que se trata de un obstáculo relativo a sus métodos.

Actualización mismo día unas horas más tarde.

Añado una nueva fuente, que parece la más completa, que estoy leyendo ahora  mismo. Tras una primera lectura en diagonal no me he enterado de mucho. Es bastante más complicado de lo  que pensaba, aunque el autor del resumen lo deja claro no veo muy claro la relación de la primera parte con la segunda (en la primera da una cota superior, demostrando que los grafos de johnson son el peor caso; en la segunda daría una cota inferior, demostrando que este peor caso se puede trata en tiempo cuasipolinómico). Tampoco comprendo del todo algunos pasos de la segunda.

Y ni conozco bien el problema de string isomorphism, aunque tampoco parece mayormente complicado si está relacionado con esto: Let sΣ be a formal language string. Consider the automorphism group of s, defined to be the set of all permutations of positions of s that leave s fixed; for instance G(abab)={id, (1,3), (2,4), (1,3)(2,4)}, ni he comprendido bien la necesidad de utilizarlo en vez de trabajar con grafos directamente. ¿ Es algo sustancial o simplemente ha querido resolver un problema más general ? He visto que hay gente que comparte esta confusión conmigo. En este artículo de Babai hablan del problema.

Let us fix a permutation group G acting on the set Ω. Given two input strings x, y : Ω → {0, 1}, we say x is “G-isomorphic” to y if y is a a π-shift of x for some π ∈ G. We want to test the property “x is G-isomorphic to y,” that is, we want to distinguish the case when x and y are G-isomorphic from the case when every string that is G-isomorphic to y is far from x. [Formal definitions are given in Section 2.] 

Graph Isomorphism is a special case of G-isomorphism: let Ω be the set of unordered pairs of the set V of vertices; and G = Sym(2)(V ) the induced action on Ω of Sym(V ), the symmetric group acting on V (so n = |V | 2 ). We note that the induced symmetric group action on pairs is primitive (does not admit nontrivial invariant partitions of the permutation domain). This fact defines the direction in which we extend results on Graph Isomorphism. We note that by considering the induced symmetric group action on k-tuples, another primitive action, we also cover the case of k-uniform hypergraphs (k-hypergraphs). Here k is a variable, 2 ≤ k ≤ |V |−2. Various finite geometries also correspond to primitive groups, so G-isomorphism includes equivalence under geometric transformations (projective, orthogonal, symplectic, etc.)

Los detalles de la sección son demasiado técnicos y no me aclaran mucho.

La idea parece remontarse a Luks y el paso de grafos a strings es el evidente. Pero sigo sin tener clara la ventaja.

2.2 Strings and graphs. Let V be a linearly ordered set and Z an alphabet. A E-string on V is a function x :V—+ Z. The set of all Z-strings on V is denoted by Z V. Strings can be regarded as particular structures with only unary relations. Thus, for o ~ Sym(V) the string x a satisfies x~(v) = x(vO-l). Canonical forms for strings are defined as above. Since we have found ‘labeling v awkward in this setting, we shall refer to the subcoset of oG which maps x to CF(x, aG) as a canonical placement-coset, denoted CP(x,aG). Whereas for graphs, etc., our basic problem is to find canonical forms w.r.t. Sym(V), this problem becomes trivial for strings: the lexicographically first string obtained by reordering V will do it. However, the canonical form problem for graphs is easily reduced to the canonical form problem for strings with respect to a particular group. The adjacency matrix of an n-vertex graph (digraph, colored graph, etc.) is a string of length n 2 (indices ordered lexicographically) over a suitable alphabet. Then ~ e Sym(V) acts on such strings via a~(i,j) = a(i ° -I, ja-l). Observation 2.2. A canonical form for graphs w.r.t. aGe Sym(V) i8 precisely a canonical form for strings of length n 2 w.r.t, the induced action of oG. Switching back and forth between graphs and strings will enable us to combine geometric and algebraic ideas, each in their natural setting, Our basic tool is the string placement algorithm of §3.2, the canonicity of which is rigorously proved.

Aquí lo dejamos.

Expertos que han leído esta entrada de reddit siguen pensando que será P, lo cual es perfectamente posible, según hemos visto. Y les llama la atención que no se haya publicado en forma de artículo. Seguramente éste no existe todavía e su forma definitiva y el autor tenía prisa en presentar los resultados.

Como veremos  en el siguiente punto varios artículos relacionados con el problema de isomorfismo de grafos de johnson se han publicado recientemente y el pensar que otros estaban cerca de su resultado puede ser el motivo de que presente sus resultados de esta manera. O quizás el pensar que alguien podría patentar sus avances🙂. ¿ Estará trabajando ahora mismo cortando los últimos flecos ?🙂. En fin por argumentación ad-hominem (el prestigio y carrera anterior del autor) todo el mundo da por hecho que el resultado será correcto. Me incluyo entre ellos.

El tema ya ha transcendido a las revistas de divulgación científica.

For days, rumors about the biggest advance in years in so-called complexity theory have been lighting up the Internet. That’s only fitting, as the breakthrough involves comparing networks just like researchers’ webs of online connections. László Babai, a mathematician and computer scientist at the University of Chicago in Illinois, has developed a mathematical recipe or “algorithm” that supposedly can take two networks—no matter how big and tangled—and tell whether they are, in fact, the same, in far fewer steps than the previous best algorithm.

Esto es lo que hacemos nosotros en la segunda solicitud de patente, con algunos pasos de nuestro método, acortar el número de pasos para otro problema con aplicaciones prácticas, y sorprendentemente nos la han denegado…¡¡ por considerar que estos pasos eran una idea abstracta !!. ¿¿ Algo que consigue una mayor eficiencia (de doblemente exponencial a subexponencial, en los improbables peores casos) en aplicaciones prácticas una idea abstracta ??. Esperemos que con la nueva argumentación que vamos a presentar entren en razón.

Nueva actualización, día siguiente: algunos blogueros señalan que todo esto se podría haber realizado ya hace 30 años, en los 80. Es decir que no se basa en trabajo nuevo y se preguntan, si esto es así, como se ha tardado tanto….Buena pregunta.

Por una parte es posible que sí haya habido novedades sustanciales que hayan hecho posible este avance;  los expertos dirán.

Relevante (de un comentario del autor del resumen en un blog).

In re point (4), I recall Babai emphasizing that this new result was heavily influenced by relatively recent work (2008) on hypergraph isomorphism with his student Paolo Codenotti. I have not read this paper, so I don’t know how much it relates to what I have absorbed about the problem so far.

See: Babai-Codenotti, Isomorphism of Hypergraphs of Low Rank in Moderately Exponential Time. FOCS’08.

Extracto.

A key ingredient of our procedure is a subexponential algorithm for the Coset Intersection problem: given two subcosets of the symmetric group, determine their intersection. The intimate connection of this problem to Graph Isomorphism was first highlighted in Luks’s seminal paper [Lu1]; an n O( √ n) algorithm was found by the first author:

Theorem 1.2. ([Ba7]) The Coset Intersection Problem can be solved in n O( √ n) time. In fact, it can be solved in time n O(1)mO( √m) time where m is the length of the longest orbit of the two groups.

The n O( √ n) result was first described in [Ba5] (1983). It was included with a sketch of the proof in [BKL]. The proof of the main structural group theoretic lemma was given in full in [BBT]. While the outline of the coset intersection algorithm given in [BKL] omits key details, a full proof is now available [Ba7]. Other ingredients include the moderately exponential Graph Isomorphism test and a combinatorial lemma (Lemma 3.10).

Nos seguimos preguntando sobre la relación entre el coset intersection problem y nuestro problema sobre la intersección IAS/DAS, clave en nuestro resultado y en la estructura de los Digrafos de Cayley bigenerados.  Por su relación con el problema de isomorfismo de grafos ¿ debemos de suponer que también se puede resolver este problema CIP (que para  nosotros sería sub-exponencial, cota de Landau, en el peor caso)  en tiempo cuasi-polinómico ?. Si es así  y existe relación o equivalencia entre los dos problemas esto reduciría la complejidad de nuestro problema. Tema a estudiar.

Ayer estuve precisamente hojeando algún artículo de Codenotti, no recuerdo ahora cual, pero con seguridad no era el indicado, era más bien una tesis.

Por otra parte, en mi opinión, sin ánimo de ser cínico, sin ánimo de ser injusto (obviamente los comentarios que siguen son sobre un sistema y no sobre las personas que se ven obligadas a seguirlo) y al margen de la dificultad que los problemas puedan tener, el sistema académico no está  diseñado, no premia el que se maten los grandes problemas, lo  cual quemaría los campos de investigación, sino para muchas pequeñas publicaciones graduales, aunque importantes, menores, que van cercando poco a poco al problema, que permiten construir una carrera a largo plazo. No olvidemos que son profesionales que viven de publicar. A un aguador  nunca se le hubiese ocurrido hablar (publicar sobre) de cañerías…

Por eso a nadie debe de sorprender que este resultado lo publique un investigador de 65 años y no alguien joven: se va a jubilar y la publicación ya no supone para él pegarse un tiro en el pie🙂, ya no supone arruinar su propia carrera, ya no supone arriesgarse a que sus colegas le  hagan luz de gas por haber quemado su campo de investigación y arruinado sus carreras.🙂.

Finalmente es posible, que el hecho de que en este campo no esté nada claro (ya cada vez menos, según las nuevas regulaciones en EEUU) si es posible la apropiación de resultados (mediante patente) y lo que prime es la entrega al dominio público,   tampoco ayuda mucho a que se aceleren los grandes descubrimientos en este campo. Si se permitiese la apropiación sin ninguna ambigüedad, otro gallo cantaría.

En definitiva el sistema de producción de conocimiento, tal y como está diseñado y tal y como se está diseñando con los últimos cambios en el sistema de patentes de EEUU, es más propio de una Sociedad Agrícola, que vive en un mundo de eternidad cíclica, contemplativa, que gusta más de darle vueltas a la noria que de inventar la máquina de vapor, que gusta más de marear la perdiz que de cazarla de una vez, (el uso, muchas veces innecesario, de un lenguaje abstruso, solo apto para iniciados, propio de cultos mistéricos de sociedades agrícolas de la Antigüedad, obviando casi siempre el muy clarificador ejemplo concreto, demuestra que nuestra descripción es acertada) que en el mundo propio de la Sociedad Industrial que necesita el progreso rápido y real, para superarse a si misma y llegar lo antes posible al siguiente estadio, la Sociedad del Ocio.

Fin actualizaciones. 

De los comentarios a la entrada:

He proves that big Johnsons are the only obstructions to Sachs’s work, and then shows how to build a recurrence that breaks down the problem quick enough in that case. 

2. Los Grafos de Johnson y sus grupos de automorfismos.

En esta segunda parte recopilamos algunos enlaces que nos aclaren algunas dudas que tenemos sobre los Grafos de Johnson. Planteamos las dudas y hacemos algunos extractos de los enlaces que las aclaran. Probablemente esta parte sea solo de interés para el que escribe estas lineas y por ello la redacción es (todavía) más confusa que la del punto anterior. No obstante me han quedado más claras estas cuestiones que las del punto anterior.

Sólo me queda una duda por aclarar: dado un número de vértices, ¿¿ cuantos grafos de Johnson no isomorfos puede haber ??

Relevante (de un comentario de un blog): In what sense are Johnson graphs ‘hard’? In some sense they seem to be easy, because there’s no ‘quasi-johnson’ graph to fool you. If two things look like Johnson graphs of the same size, then gosh darn it, they are in fact isomorphic.

Teniendo en cuenta todo lo que comentamos a continuación, y teniendo en cuenta los métodos de solución del problema de isomorfismo (la  individualización de vértices en base a propiedades como el grado, la conectividad con otros vértices etc…), parece claro que los peores casos tenían que ser la clase de los grafos más simétricos posibles  (aquellos que hacen más difícil la individualización de los vértices) siempre y cuando la clase  permita casos varios para cada cardinalidad. Es decir, si no me equivoco, los más simétricos posibles son los grafos completos Kn, pero para cada cardinalidad sólo tienen un representante. La siguiente clase más simétrica posiblemente sea la de los grafos de Johnson, que son vértice transitivos, arco-tansitivos, distancia-transitivos… En los  siguientes enlaces veremos que se puede definir todavía una propiedad que asegura mayor simetría (la propiedad de homogeneidad) pero en cuyo caso se obtienen clases de grafos (salvo una que no tengo clara) triviales para el problema de isomorfismo, entre ellas la clase de grafos completos.

Se construyen de manera similar a los Grafos  de Cayley, aunque los objetos que etiquetarán a los vértices no  son permutaciones sino los subconjuntos de un conjunto. Son similares a los grafos de Kneser.

Se da el caso de que por sus propiedades (son “supersimétricos”, palabra no técnica, pero el lector entenderá) los grupos de automorfismos de los grafos de Johnson son o An o Sn y entiendo que por ello constituyen casos difíciles para el problema de isomorfismo; “n” sería en este caso la cardinalidad del conjunto finito del cual se seleccionan los subconjuntos.

Siendo la construcción similar, ¿ que relación tienen los grafos de Johnson con los Grafos de Cayley ?.

Algunos enlaces al respecto.

a) Definición general de los Grafos de Johnson y algunas de sus propiedades.

https://esc.fnwi.uva.nl/thesis/centraal/files/f1182505387.pdf

En este artículo dan una definición general de este tipo de grafos construidos en base a subconjuntos de un conjunto dado.

3.6 The Uniform Subset Graph.

Definition 3.15. The uniform subset graph G(n, k, t) has as vertices the k-subsets of {1, 2, . . . , n} where two vertices are adjacent if the k-subsets have t elements in common.

Definition 3.16. A graph G = (V, E) is edge transitive if for all e, f ∈ E, there exists an automorphism of G that maps the endpoints of e to the endpoints of f.

Theorem 3.17 (Chen and Lih [12]). G(n, k, t) is edge transitive.

Definition 3.19. The Johnson graph J(n, k) is the graph G(n, k, k − 1). The Johnson graph is derived from the Johnson distance, which is the number of elements between two k-subsets, the k-subsets differ.

Theorem 3.20. All Johnson graphs are Hamiltonian.

Alspach demostró en 2012 un resultado más potente que este en relación a la hamiltonicidad de los grafos de Johnson.

Johnson graphs are Hamilton-connected

Brian Alspach School of Mathematical and Physical Sciences University of Newcastle Callaghan, NSW 2308, Australia Received 15 December 2011, accepted 15 January 2012, published online 1 June 2012

Abstract We prove that the Johnson graphs are Hamilton-connected and apply this to obtain that another family of graphs is Hamilton-connected.

b) Todos los grafos de Johnson son vértice transitivos.

Un artículo más elemental y por ello clave.

Distance-Transitive Graphs

Submitted for the module MATH4081 Robert F. Bailey (4MH) Supervisor: Prof. H.D. Macpherson May 10, 2002

For n ≥ 2k, the graphs J(n,k,k −1) are known as Johnson graphs, the graphs J(n,k,0) are known as Kneser graphs and the graphs J(2k−1,k−1,0) are known as the odd graphs. These families had been investigated before the general definition of a uniform subset graph was given by Chen and Lih [15] in 1987. The Johnson and odd graphs are the ones which this chapter is devoted to, as we shall see that they are distance-transitive.

Y antes nos comentaban:

Proposition 2.1.1 Any distance-transitive graph is vertex-transitive.

Proof: Let Γ be a distance-transitive graph. Take vertices u = v and u 0 = v 0 ∈ VΓ (so that d(u,v) = d(u 0 ,v 0 ) = 0). We know there exists g ∈ Aut(Γ) such that ug = u 0 and vg = v 0 (as Γ is distance-transitive). Hence Γ is also vertex-transitive . However, the converse is not true in general; there exist vertex-transitive graphs that are not distance-transitive.

Lo cual aclara  mi duda principal: todos los Grafos de Johnson son vértice transitivos. Es más también son arco-transitivos. Es  por lo tanto una clase muy restringida. Por otra parte el lector ya se habrá dado cuenta, en base a la definición que el grado de los vértices crece bastante rápidamente en esta familia.

Ya sabemos que los grafos de Johnson son vértice transitivos. También avanzamos  que en general no son grafos de cayley. Pero ¿ cual es la relación exacta entre las dos clases ?.

c1) La mayoría de los grafos de Johnson no son Grafos  de Cayley. En general su grupo de automorfismos es Sn o An. 

El siguiente es el abstract  que hemos encontrado más informativo, el que aclara casi todas las dudas de forma más directa.

Which merged Johnson graphs are Cayley graphs?

http://s3-eu-west-1.amazonaws.com/kg15/production/abstracts/316_gareth-aneurin-jones.pdf?1431579199

It has been conjectured that ‘most’ vertex-transitive connected graphs are Cayley graphs. Recently Dobson and Malniˇc, building on earlier work of Godsil on Kneser graphs and of Kantor on permutation groups, have determined which Johnson graphs J(n, k) are Cayley graphs: most are not, although they are all vertex-transitive and connected.

Using finite group theory we extend this result to the distance i Johnson graphs J(n, k)i and the merged Johnson graphs J(n, k)I : despite some of these having much larger automorphism groups, no further Cayley graphs arise, apart from a few trivial examples.

Indeed, in most cases the only vertex-transitive groups of automorphisms are the alternating and symmetric groups of degree n.

Este abstract lo es de una presentación en unas conferencias de junio de 2015 Minisymposium: STRUCTURE AND PROPERTIES OF VERTEX-TRANSITIVE GRAPHS Organizer: Robert Jajcay (Comenius University, Bratislava, Slovakia, and University of Primorska, Koper, Slovenia) en las que se presentaron otros resultados interesantes. La compilación de abstract aquí.

https://conferences.matheo.si/event/20/picture/0

Sobre el grupo de automorfismos de los grafos de Cayley.

Automorphism Groups of Cayley Graphs

Ted Dobson Department of Mathematics & Statistics Mississippi State University dobson@math.msstate.edu http://www2.msstate.edu/∼dobson/ Symmetries of Graphs and Networks November 23–28, 2008

http://www.cs.uleth.ca/~morris/banff-symmetries/talks/Dobson-Banfftalk.pdf

c2) ¿ Podemos entonces estimar cuantos Grafos de Johnson son Cayley o determinarlos ?.

Al parecer se podría.

Groups That Are Transitive on All Partitions of a Finite Set We study the question of which subgroups of Sn are transitive on the set of all ordered partitions of the set [n] = {1,…,n} and all unordered partitions of [n]. This work can be considered a generalization of well known work in which subgroups of Sn that are transitive on the set of all subsets of [n] of size k were determined. As an application of our results, we determine which Johnson graphs are Cayley graphs.

Autor: Ted Dobson.

c3) ¿ Son todos los grafos de vertice transitivos no Cayley, Johnson o de la familia más general ?.

Seguramente no. El siguiente artículo es relevante. Ya hemos realizado algunas entradas compilando artículos sobre grafos vértice transitivos no Cayley. seguramente el artículo siguiente está ya reseñado en ellas.

VERTEX-TRANSITIVE GRAPHS WHICH ARE NOT CAYLEY GRAPHS,

http://www.researchgate.net/publication/240395649_Vertex-transitive_graphs_which_are_not_Cayley_graphs_II

Pero esto otro sobre el  mismo tema, algo antiguo ya, del 96 no me suena haberlo  leído.

http://ajc.maths.uq.edu.au/pdf/10/ocr-ajc-v10-p105.pdf

A construction of vertex-transitive non-Cayley graphs Robert Jajcay Department of Mathematics University of Nebraska Lincoln, NE 68588-0323 jajcay@helios.unl.edu J ozef Sir

c4) http://arxiv.org/pdf/1509.03125.pdf

Este segundo artículo, muy reciente (2015) y relevante para la relación de los grafos de johnson con los grafos de cayley. Es muy técnico.

Autor. Gareth Jones.

d) http://www.academia.edu/896372/Finite_Transitive_Permutation_Groups_and_Finite_Vertex-Transitive_Graphs_C_E_Praeger_with_assistance_of_C_H_Li_and_A_C_Niemeyer

No hablan de los grafos de Johnson pero tiene interés por sus comentarios sobre el problema de isomorfismo en Grafos de Cayley.

e) http://www.combinatorics.org/ojs/index.php/eljc/article/viewFile/v20i1p56/pdf

In this paper, we present an infinite family of half-transitive graphs. These graphs were originated from Johnson graphs J(n, i) where i = 1, 2 or 3, the vertex set of which consists of the i-element subsets of an n-element set such that two vertices are adjacent when they meet in (i − 1)-elements. It is known that the automorphism group of J(n, i) is Sn, see [9] or [15, Theorem 1].

f)

http://ac.els-cdn.com/S0195669804000630/1-s2.0-S0195669804000630-main.pdf?_tid=9fd15ce4-8932-11e5-b9c2-00000aacb361&acdnat=1447328802_8d5bad427fe0776ac1181548bcafa850

En este artículo nos definen a la clase más general de Merged Johnson graphs y determinan sus grupos de autormorfismo.

Here we consider a class of graphs based on the Johnson graphs. The vertices of a Johnson graph J (n, m) are the m-element subsets of an n-element set (2 ≤ m ≤ n/2), adjacent if their intersection has m −1 elements. Given a nonempty subset I ⊆ {1,…, m}, we define the merged Johnson graph J (n, m)I to be the union of the distance i graphs J (n, m)i of J (n, m) for all i ∈ I, so two m-element subsets are adjacent in J (n, m)I if their intersection has m − i elements for some i ∈ I.

The graphs J (n, m)I include many interesting graphs, such as the Johnson graphs J (n, m) = J (n, m)1, the line graphs L(Kn) = J (n, 2)1 of the complete graphs, their complements J (n, 2)2, and the odd graphs Om+1 = J (2m + 1, m)m.

g) Este resultado es más algorítmico. Compara el método de refinamiento de colores que creo utiliza Babai con un método de álgebra lineal.

http://arxiv.org/pdf/1502.01255.pdf

El autor presenta primero una jerarquía.

Taking a finer look at the inclusion Compact ⊂ Refinable, in Section 8 we discuss algorithmic and algebraic graph properties that were introduced by Tinhofer [24] and Godsil [11]. We note that, along with the other graph classes under consideration, the corresponding classes Tinhofer and Godsil form a hierarchy under inclusion:

Discrete ⊂ Amenable ⊂ Compact ⊂ Godsil ⊂ Tinhofer ⊂ Refinable.

(1) We show the following results on these graph classes:

–The hierarchy (1) is strict.

–Testing membership in any of these graph classes is P-hard.

Resulta que los Grafos de Johnson separan la clase Godsil de la clase Tinhofer.

Separation of Godsil and Tinhofer: These classes are separated by the Johnson graphs J(n, 2) for n ≥ 7. The Johnson graph J(n, k) has the k-element subsets of [n] = {1, . . . , n} as vertices; any two of them are adjacent if their intersection consists of k−1 elements. Note that J(n, 1) = Kn. Furthermore, the graph J(n, 2) is the line graph of Kn: it has all 2-element subsets of [n] as vertices and any two of them are adjacent if their intersection is non-empty. It is noticed in [9] that J(n, 2) is not Godsil for n ≥ 7. For establishing the separation, we show that J(n, 2) is indeed Tinhofer. The proof is given in Section A.2

h) Sobre los grupos de automorfismos de grafos.

http://www.designtheory.org/library/preprints/auts.pdf

Un artículo muy informativo al respecto de Cameron. Creo que es el borrador del capítulo de un libro de Beineke. Hay grafos todavía más supersimetricos que aquellos sobre los que estamos hablando: los que tienen la propiedad de ser homogéneos.

An even stronger symmetry condition is homogeneity: a graph G is homogeneous if any isomorphism between (finite) induced subgraphs extends to an automorphism of G. The finite homogeneous graphs were determined by Sheehan and Gardiner (see [22]):

Theorem 8.1 A finite homogeneous graph is one of the following:

• a disjoint union of complete graphs of the same size;

• a regular complete multipartite graph;

• the 5-cycle C5;

• the line graph of K3,3.

Son tan restringidos que no parecen muy interesantes, salvo quizás la segunda clase.

Este autor nos explica con una claridad meridiana la relación entre los problemas  de isomorfismo de dos grafos H y G, y dar los generadores del grupo de automorfismos de un grafo.

The two problems are closely related. Indeed, the first has a polynomial reduction to the second. For suppose that we are given two graphs G and H. By complementing if necessary, we may assume that both G and H are connected. Now suppose that we can find generating permutations for Aut(K), where K is the disjoint union of G and H. Then G and H are isomorphic if and only if some generator interchanges the two connected components. Conversely, if we can solve the graph isomorphism problem, we can at least check whether a graph has a non-trivial automorphism, by attaching distinctive “gadgets” at each of its vertices and checking whether any pair of the resulting graphs are isomorphic. (Finding generators for the automorphism group may be harder.)

El teorema clave, como no de Erdos (y Renyi), es el siguiente:

Theorem 3.1 Almost all graphs have no non-trivial automorphisms.

Los casos más interesantes son aquellos que tengan un grupo de automorfismos lomás grande posible, los grafos de johnson.

En relación a los grafos de Cayley existe el problema DRR y GRR sobre el que enlazamos  el siguiente artículo.

http://arxiv.org/pdf/1306.3747.pdf

CAYLEY GRAPHS ON ABELIAN GROUPS EDWARD DOBSON, PABLO SPIGA, AND GABRIEL VERRET Abstract. Let A be an abelian group and let ι be the automorphism of A defined by ι : a 7→ a −1 . A Cayley graph Γ = Cay(A, S) is said to have an automorphism group as small as possible if Aut(Γ) = A ⋊ hιi. In this paper, we show that almost all Cayley graphs on abelian groups have automorphism group as small as possible, proving a conjecture of Babai and Godsil.

Extractos. 

Let G be a group and let S be a subset of G. The Cayley digraph on G with connection set S, denoted Cay(G, S), is the digraph with vertex-set G and with (g, h) being an arc if and only if gh−1 ∈ S. Note that we do not require our Cayley digraphs to be connected and that they may have loops. It is an obvious observation that Cay(G, S) is a graph if and only if S is inverse-closed, in which case it is called a Cayley graph. It is also easy to check that G acts regularly as a group of automorphisms of Cay(G, S) by right multiplication. When studying a Cayley digraph Cay(G, S), a very important question is to determine whether G is in fact the full automorphism group. When it is, Cay(G, S) is called a DRR (for digraphical regular representation). A DRR which is a graph is called a GRR (for graphical regular representation). DRRs and GRRs have been widely studied.

The most natural question is the “GRR problem”: which groups admit GRRs?

The answer to this question was completed by Godsil [9, 1979], after a long series of partial results by various authors (see [11, 12, 24] for example).

The equivalent problem for digraphs was solved by Babai [2, 1980] (curiously, the “DRR problem” was mainly considered after the GRR problem had been solved). In the course of working on these and related problems, Babai and Godsil made the following conjecture [3].

Según este resultado algunos digrafos de cayley de An y Sn tendrán grupos de automorfismos grandes, An o Sn. ¿ Pero son estos abundantes ?.

Cameron nos comenta:

What about random Cayley graphs for G, obtained by including inverse pairs of non-identity elements in S with probability 1 2 ? Babai and Godsil [4] conjectured that, except for the two infinite classes in the theorem, almost all Cayley graphs for G are GRRs (that is, the probability that a random Cayley graph is a GRR tends to 1 as |G| → ∞). They proved that this is true in some cases (for example, non-abelian nilpotent groups of odd order).

¿¿ Y por qué, si tienen un grupo de automorfismos factorial no son casos difíciles para el problema de isomorfismo, a diferencia de los  grafos de johnson ?? ¿ O es que lo que hace difíciles a estos últimos no es el que tengan un grupo de automorfismos grande o no solo eso ?

i). Una presentación:

On Automorphism Groups of Vertex-transitive Graphs

Ted Dobson. 2007.

j) Un artículo que no tiene mucho que ver con los anterior pero me interesa retener (o enlazar) dado que ponen ejemplos prácticos sobre lo que son los Cayley Coset Graphs.

Analysis of interconnection networks based on simple Cayley coset graphs. 

While the concept of Cayley coset graphs has been around for a
long time, it is only recently the present authors derived conditions
for a Cayley coset graph to be simple – not containing self loops and
multiple edges. Building on this result a whole host of Cayley coset
graphs – coset star graph, coset bubblesort graph, coset modified
bubblesort graph, coset complete transposition graph to mention a few, have been identified. This paper represents the first attempt to evaluate the use of Cayley coset graphs in the design of interconnection networks for parallel computers. We first derive conditions for a simple Cayley coset graph to be vertex transitive. We then present a family of Cayley coset star graphs and analyze a number of its properties. It is shown that this family is recursively scalable, contains star graphs as a subgraph, and is Hamiltonian. We derive conditions for this family to bipartite and edge transitive. Finally, a shortest path algorithm and an enumeration of node disjoint paths are given. A number of open questions are listed in the conclusion.

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: