Dígrafos de Cayley (2,3)-generados (y otros similares): sus propiedades de hamiltonicidad.

Entrada en construcción. Estará terminada cuando desaparezca este mensaje.

Actualizado 18 de agosto 2016: se han añadido datos a los C2C4 generados. A falta de los de S6, la información está completa (todos los casos dibujados; no he añadido de momento los dibujos). Fin de actualización.

Actualización 8 de mayo de 2016.

Añadida información relativa a casos C2C4 de S4 (3 casos) y un dibujo más (que ya tenía realizados de hace años y he encontrado ayer revisando mis archivos) de 1 caso de S5.

Fin actualización.

http://www.famnit.upr.si/files/zakljucna_dela_repo/48

https://books.google.es/books?id=d5PLBQAAQBAJ&pg=PA224&lpg=PA224&dq=solvable+groups+permutation+generators&source=bl&ots=CGTnfchuwD&sig=i16JVQOO-SlCyuJMv0HgTVqVFpY&hl=es&sa=X&ved=0ahUKEwiP07-asfHMAhWJ2RoKHRUvAUM4FBDoAQgzMAM#v=onepage&q=solvable%20groups%20permutation%20generators&f=false

 

En base a las entradas anteriores en esta entrada quiero analizar las propiedades de hamiltonicidad de todos los casos de que dispongo (2-3) generados.

También analizaremos otros casos (2-n) generados de S5 cuyas propiedades estructurales no analicé en detalle en su momento. El factor común de todos ellos es,

–primero, que uno de los generadores es una involución y por ello en la base de datos que elaboré aparecían como entrelazados o entangled. Pero algunos de ellos o incluso que no haya recorridos en ninguno es posible

–segundo que el tamaño del IAS es “grande” en relación con el número de vértices o bien el orden del generador que no es de orden 2 es grande también.

–tercero, son casos problemáticos, en el sentido de que tienen algunos vértices finales posibles sin recorridos hamiltonianos, o incluso ninguno de ellos los tiene.

La motivación de esta entrada es la siguiente:

quiero averiguar si, como pienso, las propiedades estructurales que hemos reflejado en la patente (2º solicitud de patente) explican todos los casos complicados. Si no he analizado mal el caso de la entrada anterior (el PSL(2,7), que tengo pendiente de reanalizar) podría ser smooth y no tener recorridos hamiltonianos en ninguno de los vértices finales posibles. Realmente no hace falta analizarlo con mayor profundidad: es twisted, como todos aquellos cuya circunferencia es de orden 2 (4 IASES) si el IAS es par o de orden 4 (4 IASES) si el IAS es impar.

No obstante sí me interesa analizar varios otros de estos casos y similares, dado que es posible que tengan propiedades estructurales que nos permitan predecir mejor sus propiedades de hamiltonicidad.

Nota. El lector que haya seguido estas entradas a lo mejor se habrá realizado algunas preguntas sobre la propiedad smooth/twisted. Por ejemplo:

–si un caso es twisted entonces ¿ no hay necesariamente IASes de la circunferencia que tienen permutaciones en común (al margen de las que tienen que tener por ser IASes adyacentes). Es decir el test smooth/twisted, que ya es bastante laborioso  ¿ no se puede reducir a un test con la circunferencia, más sucinto ?

–no puede darse el caso de  que haya casos twisted que pasen el test de ser smooth localmente (en el entorno de la identidad tal y como lo hemos definido).

–y si se diese el caso anterior, ¿ cuales serían las propiedades de hamiltonicidad de estos casos twisted, aunque smooth localmente ?.

En la imagen siguiente un ejemplo ficticio pero ilustrativo de este hipótetico tipo de casos.

smoothes twisted

El ejemplo ni está basado en ningún caso real ni pretende ser realista (como veremos en esta misma entrada la circunferencia no tiene por qué tener la forma circular indicada). Sólo quiero ilustrar la idea. Los IASES de la circunferencia numerados del 1 al 15. La parte de la circunferencia que pertenece al entorno de la identidad en rojo. Como se ve un vértice del IAS de la identidad que enlaza con otro IAS fuera del entorno de la identidad. ¿ Existen este tipo de casos ? ¿ Cuan numerosos serían ? ¿ Cuales serían sus propiedades de hamiltonicidad ? ¿ Se necesita que los IASes estén contiguos al IAS de la identidad para que las causas de obstáculos a la hamiltonicidad de los casos twisted sean operativas ? . Muchas preguntas que no vamos a contestar de momento en esta entrada.

Fin de nota.

Algunas abreviaturas que utilizamos en lo que sigue.

S=Grupo Simétrico.

G=grado de las permutaciones.

C=orden de los generadores

RH o RHs=recorridos hamiltonianos.

VF o VFs = vértices finales posibles.

1.(2-3) generados.

Sobre grupos (2-3) generados, muy interesante:

http://www.math.nsc.ru/conference/groups2013/slides/MaximVsemirnov_slides.pdf

Y también muy interesante:

https://arxiv.org/pdf/1605.04276.pdf

Comentar que cuando tenga claro su alcance, intentaré en cada uno de estos casos averiguar si aplica o no el teorema de Milnor.

Nota. Parece que hay dos resultados de Milnor sobre este tema:

El primero se aplica a grupos solubles:

Milnor Counter example 3.4 shows the analogue of theorem 3.3 is not true for the class-of all solvable groups.

  1. 34, Counter Example (John Milnor). Choose natural numbers n and r so that n divides 3 -r+l. Let G = <a,b: a^2 =b^3 = c^n = 1; cb-bc^r-1), where c = a^-1b^-1ab is the commutator of a and b. Then G/<c> is cyclic, so G is solvable. The orders of a,b and ab are 2,3,6 respectively, so one can show there is no hamiltonian path in Cay(a,b) when n is large. This example refutes a conjecture of Nijenhuis and Wilf (resp. Witte [33]) that there is a hamiltonian path in every Cayley Graph on a solvable group, (req. metacyclic group).

Y el segundo, más general, es el que ya hemos citado. A continuación en otra fuente.

2) Remark. One can show quite easily that if S = {a, b} is a 2-element generating set of a group G, such that |a| = 2, |b| = 3, and |G| > 9|ab^2 |, then→Cay(G; a, b) does not have a hamiltonian path. (This observation is attributed to J. Milnor [2, p. 267].)

La fuente citada en este caso (2, p276) es

W. Holsztynski and R. F. E. Strube: Paths and circuits in finite groups, Discrete Math. 22 (1978), no. 3, 263–272. (nos ha costado bastante encontrar un enlace a este artículo descargable).

Not every finite group is sequential. Nijenhuis and Wilf showed that if S5 is the symmetric group on 5 letters and if A consists of a 5-cycle and a 2-cycle, then there does not exist a sequence (g,, . . . , g,,,) with distinct partial products, and hence (by our remarks in Section 1) S, does not have a complete A -path. Since S5 is not solvable, they conjectured (in our terminology) that all solvable groups are sequential.

3) J. Milnor (unpublished) constructed the following counterexample. Let G = (a, b |  a^2 = b^3 = (ab)^6 = ((abab)^2)^n = 1) and A = {a, b}. Then G is solvable and for all sufficiently large n there does not exist a complete A -path (see Example 3).

A  no ser que sean el  mismo…

Así, a primera vista en realidad ahora parecen ser tres que, a simple vista, no me parecen equivalentes. Cuanto más leo sobre esto más confundido estoy.

Repito la cita de la fuente donde primero leí sobre este resultado atribuido a Milnor, On Cayley Digraphs That Do Not Have Hamiltonian Paths.

It has been conjectured that every (nontrivial) connected Cayley graph has a hamiltonian cycle. (See the bibliography of [1] for some of the literature on this problem.) This conjecture does not extend to the directed case, because there are many examples of connected Cayley digraphs that do not have hamiltonian cycles. In fact, infinitely many Cayley digraphs do not even have a hamiltonian path.

Proposition 2 (attributed to Milnor [2, p. 201]). Assume the finite group G is generated by two elements a and b, such that a^2=b^2=e. If |G|> 9|ab^2|, then the Cayley digraph G{a,b} does not have a hamiltonian path.

The examples in the above proposition are very constrained, because the order of one generator must be exactly 2 and the order of the other generator must be exactly 3. In this note, we provide an infinite family of examples in which the orders of the generators are not restricted in this way. In fact, and can both be of arbitrarily large order.

La fuente que citan en este caso es Partial Products in Finite Groups (Nathanson, 1976), y este parece ser el primer artículo (por la fecha) que habla de este resultado. Nos comentan:

Milnor (unpublished) constructed a counterexample to this conjecture. Let G be a group defined by the generators T=(a,b) and the relations a^2=b^3=(ab)^6=(abab^2)^n = e. Milnor showed that G is  solvable and that, for all sufficiently large n, there does not exist a sequence of elements in T with distinct partial products (es decir un hamiltonian path).     

Entonces, la pregunta es si la primera formulación “a^2=b^2=e. If |G|> 9|ab^2|” es equivalente a la segunda “a^2=b^3=(ab)^6=(abab^2)^n = e…for all sufficiently large n, there does not exist a sequence of elements in T with distinct partial products“.

Una fuente de confusión adicional es la siguiente (ya aclarada):

Orders of non-solvable groups are

60, 120, 168, 180, 240, 300, 336, 360, 420, 480, 504, 540, 600, 660, 672, 720, 780, 840, 900, 960, 1008, 1020, 1080, 1092, 1140, 1176, 1200, 1260, 1320, 1344, 1380, 1440, 1500,

Si las dos formulaciones son equivalentes y el teorema de Milnor se refiere siempre a grupos solubles, entonces en lo que sigue hemos considerado que se cumplia en casos en los que no es de aplicación (los de tamaños 60, 120, 168, 504 o 720). O quizás en el  comentario de wikipedia sólo quieran decir que  los ordenes indicados contienen grupos no solubles, pero no que todos los grupos de estos ordenes sean no solubles. Efectivamente  de orden 60 hay 13 grupos no isomorfos, 12 son solubles y 1 es no soluble (concretamente A5).  De la misma manera, de los 840 grupos no isomorfos de orden 720, 817 son solubles y los 23 restantes son no solubles (incluido S6; entiendo que en general los grupos simétricos superiores a S4 son no solubles). Y se puede confirmar que all group of order less than 60 are all solvable.

Y me  surge una duda sobre la notación (ya aclarada): ¿¿ el exponente 2 de |ab^2| se aplica a todo el producto o sólo a “b” ?? Es decir hablamos de a(b^2), tal y como he interpretado yo en lo que sigue o hablamos de (ab)^2.

Joer…

Dia siguiente: he estado leyendo algo sobre el tema. Los grupos nilpotents se pueden caracterizar por que su orden se puede expresar como  la potencia de un primo. Y los solubles porque su orden se puede expresar como la potencia de un numero finito de primos. Algunos datos destacados:

Theorem 6.18 Let G be a group. The following conditions are equivalent: (i) G is a finite soluble group; (ii) G has a composition series with all composition factors cyclic of prime order. Recall that the abelian simple groups are precisely the cyclic groups of (various) prime orders. Thus part (ii) describes the groups with abelian composition factors.

–Sn is not solvable for n > 4.

–También: every finite group of odd order is solvable. In particular this implies that if a finite group is simple, it is either a prime cyclic or of even order. 

–Teorema de Burnside:

Burnside’s theorem states that if G is a finite group of order

p^a q^b\

where p and q are prime numbers, and a and b are non-negative integers, then G is solvable.

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

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

También se puede caracterizar los grupos no solubles:

–Any finite simple non-abelian group is a finite group that is not solvable.

–Further, any group that contains a finite simple non-abelian group as a subgroup, has a finite simple non-abelian group as aquotient group, or admits a finite simple non-abelian group as a subquotient must be non-solvable.

Mañana veremos si con esta nueva info vemos con mayor claridad lo comentado en la nota. Y también profundizaremos sobre las propiedades de hamiltonicidad de los grupos solubles y nilpotentes, y otros de la serie que hemos dado antes.

Actualización día siguiente a día siguiente:

Ya tengo algunos temas más claros. Por ejemplo está clara la segunda duda: el exponente se aplica sólo al último generador. Es decir hablamos de a(b^2). Y por lo tanto, de la misma manera abab^2=ababb=1.

Y ya veo algún muy leve destello sobre por dónde pueden ir los tiros de la demostración aunque para nada la tengo clara.   

Tercer día de actualización:

Tras darle alguna vuelta más ya tengo casi todo claro. Si no estoy equivocado la demostración de Milnor se basa en el argumento que veníamos barajando desde la primera entrada sobre este tema: la forma de un RH, tras un determinado comienzo, tiene que contener necesariamente (ab^2) repetidas veces hasta llegar a la identidad.  ¿ Un numero entero de veces y por ello el exponente n ?.

Por ejemplo ejemplo, el caso que veremos luego  en detalle de 18 vértices, con generadores 214365 y 521436  tiene al menos un ciclo hamiltoniano (ya se que Milnor habla de caminos, pero da igual) y tiene la forma siguiente:

bbabbabbabbabbabb o bb(ab^2)^5 (he omitido el arco que lleva del vértice final a la identidad para obtener el ciclo). Esto nos hace ver que para cada vértice final posible, si existe un RH, será único o serán muy pocos.

Sin embargo, en otro caso, de 24 vértices, con generadores 4123 y 3421, que tiene un sólo RH (camino), este tiene la forma siguiente: abbabbabb(abab)abbabbabba  o (ab^2)^3(ab)^2(ab^2)^3a, que aunque contiene la forma indicada no es exactamente como decíamos.

El motivo de la disparidad entre el primer tipo y el segundo está claro: en el primer caso, al ser un ciclo, el IAS de la identidad se activa de manera  uniforme (todos los arcos de este IAS se activan por el mismo generador); en el segundo caso no se activa de manera uniforme (parte se activa por un generadory parte por el otro). Al pasar el RH por este IAS de la identidad se altera el patrón abb. ¿ Cuando el RH recorre los IASes que no sean el de la identidad lo recorren con el patrón abb ? Si esto es necesariamente así, es posible que se pueda generalizar el teorema de Milnor: si el n de (ab^2)^n=1 es < G-|IAS identidad| entonces no podría haber RHs. En estos casos cuando el IAS sea grande más posibilidades habrá de que el caso tenga RHs, dado que se evitará que se repita el patrón el número de veces necesario para que  no hay RHs. Tema a estudiar más a fondo.

En fin, si esta interpretación fuese correcta, tema que no está tan claro, no entiendo muy bien la constante 9 salvo que se refiera a una familia infinita en la que el numero de veces que se repite ab^2 está acotado necesariamente por esta constante, en cuyo caso se entiendo que referiría a una clase muy concreta de grupos solubles, no a todos ellos tampoco. ¿ Concretamente se referirá a grupos solubles con el IAS=9 ?. Si todo esto es correcto, con el teorema de Milnor se vendría a decir que existe una clase infinita de grupos solubles que no tienen caminos hamiltonianos. En el artículo dónde vi primero este tema presentan todo esto con la máxima ambigüedad, omitiendo el comentario que relacionaría el resultado con grupos solubles…

Ahora mismo me oriento a pensar que esto es así pero todavía no estoy 100% seguro. Paso a eliminar las referencias al teorema de Milnor en los casos analizados, hasta que no esté el tema 100% claro. Y me pregunto si no se puede generalizar este teorema a más casos…

Fin de nota.

–A4 (orden 12) with generators s = (12)(34) and t = (123). IAS3 y Circunferencia 3. Entangled sólo por ser un generador de orden 2. Twisted. Tiene 1 único RH en el único VF. Se encuentra tras una opción. Es fácil encontrarlo manualmente. Incluso visualmente.

–The group C3, x S3 of order 18 with generators s = (12)(34)(56) and t = (135). IAS6. El caso es entangled y ¡¡ la circunferencia de orden 2 pero contiene 3 IASES !!. Luego veremos que hay otros casos de este tipo.

Nota importante. con el caso anterior y otros analizados anteriormente queda claro que cuando calculamos el orden de la circunferencia en un caso de IAS par, y obtenemos que esta es de orden 2, pueden darse tres casos:

–cuando la circunferencia es de orden 2 y el caso es 1/2 entangled, y entonces la circunferencia contiene dos IASes, el IAS y el DAS de la identidad, y entonces al parecer la permutación (con la que se calcula el orden de la circunferencia comparandola con la identidad) es del tipo 123…(n)(n-1) o 21….(n-1)n, es decir con todos lospuntos fijos menos 2, es decir  una transposición.

–Cuando la circunferencia es de orden 2 y el caso es n-entangled (y por lo tanto ni 1/2 entangled ni 2-entangled), entonces esta contiene 3 IASes y la permutación es del tipo 123456->456123. Es decir sin puntos fijos. Esta es la primera anotación sobre este asunto.

–cuando la circunferencia es de orden 2 y el caso es 2-entangled, en cuyo caso la circunferencia contendrá 4 IASes y la permutación es del tipo 123456->132465, es decir con 2 o más puntos fijos.

Tema a investigar con más casuística.

Fin de nota.

–S4 (order 24), G4. 1243 (C2), 2314 (C3). IAS 4. Entangled sólo por ser un generador de orden 2 (a partir de ahora expresaremos esta propiedad de manera sucinta como “Sólo por C2” o “sólo x C2”. Tiene recorridos hamiltonianos en sólo 1 de los vértices finales posibles. Este caso demuestra que no en todos los casos de tipo C2C3 se da la circunstancia de que no tienen RHs en ninguno de los vértices finales posibles. En la imagen siguiente presentamos este digrafo.

24 1 RH

Como se ve la circunferencia es de orden 2 (y como el IAS es de orden par, contiene 4 IASES). Hay cuatro vértices finales posibles (rodeados por un rectángulo). Se puede demostrar fácilmente que sólo hay uno recorrido hamiltoniano en uno de los vértices finalmes posibles (marcado Si, 1). En los otros tres no hay ninguno: en dos de ellos sin opción, es decir una vez marcados como vértices finales posibles, se genera una contradicción (marcados no 0). En el restante, si hay una opción y por lo tanto determinar que no tiene recorridos hamiltonianos es más costoso.

El lector podrá encontrar (fácilmente si aplica nuestras técnicas) el único recorrido hamiltoniano del caso.

–S4 (order 24), G6. 123465 (C2), 254613 (C3). IAS 6. Este caso es 1/2 entangled y ello explica que no tenga recorridos hamiltonianos en ninguno de los vértices finales posibles.

–S5 (order 120), G7. 1234675 (C2), 2156347 (C3 aquí hay algún error). Este caso es 1/2 entangled y ello explica que no tenga recorridos hamiltonianos en ninguno de los vértices finales posibles.

–S5 (order 120), G8. 12436587 (C2), 23156478 (C3). Este caso es 1/2 entangled lo cual explica que no tenga recorridos hamiltonianos en ninguno de los vértices finales posibles.

–S5 (order 120), G9. 132547698 (C2), 243156789 (C3). IAS10. 1/2 entangled. Ningún RH. Se explica por ser 1/2 entangled.

–S6 (order 720), G9. 132547698 (C2), 243156897 (C3). IAS15. Circunferencia 15. Sólo x C2. Teniendo en cuenta sus parámetros, posiblemente twisted. Este de momento no lo he puesto a prueba con el algoritmo para determinar sus propiedades de hamiltonicidad, pero lo voy a hacer. He decidido ponerlo a prueba (sábado por la tarde). Este puede tardar horas (calculo que al menos un par de ellas). Ya informaré mañana del tiempo en concreto cuando pruebe otros VFs, pues estaré fuera. Ha tardado menos de lo que esperaba (unos 45 minutos, en realidad era lógico pues si el de 504 con una IAS de orden inferior ha tardado tan poco, este no podía tardar mucho más): el VF {6, 5, 2, 4, 3, 10, 8, 7, 9} no tiene RHs. El resto irán tardando menos, pero habrá que esperar a mañana. Confirmado que  no tiene RHs en ninguno del resto de los VFs posibles: 436527(10)89; 5243687(10)9; 36524(10)879; 243657(10)89; 6524387(10)9;43652(10)879. En todos sin opción (con la posible excepción del primero, que no anoté  sobre este tema).  Todos han tardado aproximadamente media hora. 

En lo que sigue copiamos los casos señalados en la entrada anterior sobre grupos 2-3 generados.  Analizaremos en breve cada uno de estos casos.

–The group S4 (order 24) with generators of G4 s=(14) and t=(123). Es decir generadores 4231 y 2314. IAS 4. Circunferencia de orden 2 (y como el IAS es par, contiene 4 IASES). Teniendo en cuenta los parámetros anteriores, es muy posible que este sea isomorfo al señalado anteriormente, también C2C3, IAS4 y cicunferencia 2.

–The group of order 42 with generators of G7, s = (24)(35)(67) and t = (123)(467). Es decir, generadores 1452376 (orden 2) y 2316574 (orden 3).  C2C3, IAS 6. Entangled sólo por ser de orden 2. No es cycle-entangled. Según el programa que he realizado para computar la circunferencia ¡¡ tiene una circunferencia de orden 7 !! ¿ Puede ser esto posible teniendo en cuenta el orden del dígrafo y el orden del IAS ?. Si esto se confirma seguramente es twisted. Lo estamos dibujando…Se confirma  que es twisted. Aun así no me cuadra una circunferencia tan grande: contiene 14 IASes y cada uno de ellos 12 permutaciones. Si no tuviesen ninguna en común tendríamos 168 permutaciones, cifra que supera en mucho el orden. He comprobado que la traducción de la notación en ciclos a la notación lineal de cada una de las permutaciones es correcta. Según he leído hay 5 grupos no conmutativos con este orden. En fin, poniendo a prueba este caso en el algoritmo. Dadas sus propiedades, me espero que no tenga recorridos hamiltonianos en ninguno de los VFs. ¡¡ Confirmado !!. Sin RHs en ninguno de los VFs. En dos vértices una opción y en el resto 0 opciones. En cualquier caso este caso tiene unas propiedades interesantes y lo analizaremos con más detalle cuando tengamos más tiempo…Confirmo también que el caso es correcto, es decir que estos dos generadores producen un dígrafo de 42 vértices.  Si no el algoritmo se hubiese colgado. He estado reflexionando más a fondo sobre este caso y resulta que sólo tiene 42/6=7 IASes. ¿¿¿ Como es posible que la circunferencia contenga entonces 14 ???. Entiendo que esto sólo es posible si un mismo IAS se repite varias veces en la circunferencia. Mañana veremos. Un caso sin duda fascinante, como todos estos que estamos viendo. Muy diferentes en estructura a Sn o An, entiendo que asíntoticamente también.

–The group of order 54 with generators of G9, s = (18)(27)(36)(45) and t = (126)(345)(789). Es decir generadores 876543219 (orden 2) y 264531897 (orden 3). El IAS es de orden 6. La circunferencia es de orden 3 (y por lo tanto contiene 6 IASES; 6 x12=72 vértices si fuesen todos disjuntos). Probablemente Twisted (pdte de averiguarlo). Propiedades de hamiltonicidad: sin RHs en todos los VFs. Excepto en los dos últimos (empezando por el generador de orden 2, como en los anteriores casos), sin opción. En este pasa algo similar que en el anterior: nº de IASES de la circunferencia x nº vertices por IAS > noº de vértices del caso. Habrá que verlo en profundidad.  Sobre los grupos de orden 54: There are 15 groups of order 54.

Nota. Determinar el nº de grupos (no isomorfos) dado un orden para estos tamaños pequeños es posible. Pero para tamaños no mucho mayores, enseguida empieza a ser un reto computacional:

How many distinct abstract groups have a given finite order n? We shall call this number the group number of n, and denote it by gnu(n). Given the long history of group constructions, a study initiated by Cayley [4] in 1854, it is perhaps surprising that only in this decade has a sizeable table of group numbers become available. The table in the appendix, adapted and slightly extended from that which appeared in [2], tabulates gnu(n) for 0 < n < 2048. The next value, gnu(2048), is still not precisely known, but it strictly exceeds 1774274116992170, which is the exact number of groups of order 2048 that have exponent-2 class 2, and can confidently be expected to agree with that number in its first 3 digits.

Y otra cosa es determinar, dado un grupo bigenerable, el número de Digrafos de Cayley (pares de permutaciones) no isomorfos que lo generan. Entiendo que este problema tampoco es sencillo desde el punto de vista computacional. Y entiendo que nuestras técnicas serían aplicables para acelerarlo.

Fin de nota.

–The group A5 of order 60 with generators of G5, s = (12)(34) and t = (135). Es decir generadores 21435 y 32541 e IAS5. Entangled sólo por C2. Circunferencia 5. No RH en el VF46325 (una opción, y ha tardado bastante, ha tenido que realizar bastantes comprobaciones, digamos 1 minuto en determinar  que no existe); tampoco hay RH en el VF 25463. Sin opción y rápido. En la imagen siguiente aparece el dibujo de este caso, que por cierto es planar, lo cual demuestra que la propiedad de hamiltonicidad es ortogonal a la de empotramiento en superficies:

Caso 60 twisted

En la imagen anterior en azul los IASes que pertenecen a la circunferencia y al entorno de la identidad. En verde los que pertenecen al entorno de la identidad y a la circunferencia. La conexión del IAS numerado como 6º hace que este caso sea twisted.

–The group C3 x S4 of order 72 with generators s = (12)(34)(56) and t = (125)(347). Es decir generadores de G7, 2143657  y 2547163. Entangled sólo x C2. No es cycle-entangled. IAS 6, Circunferencia 3. En este caso, el nº de IASES de la circunferencia (6) * nº vértices por IAS (12) = nº de vértices del caso. Testado con el algoritmo: sin RHs en ninguno de los vértices finales posibles.

(–The solvable group of order 96 with generators of G12 s = (34)(57)(68)(9 10), t = (123)(456)(789)(10 11 12). No vamos a analizarlo de momento dado que no tengo extendido el programa a estos grados de permutaciones)

–PSL(2,7) (order 168) also has a permutation representation with generators of G7 s = (12)(34) and t = (135)(267). ¿ Es esto lo que estábamos buscando ?. Generadores 2143567  (de orden 2) y 3654172 (de orden 3). Sólo x C2. No es cycle-entangled. Es posible que sea isomorfo o el mismo que ya hemos analizado superficialmente en una entrada anterior y cuya imagen aparece a continuación. Desde luego los generadores anteriores producen un IAS de orden 7, al igual que el del dígrafo que aparece en la imagen.

psl(2,7) (2)

Este caso (el de la imagen anterior) tiene una circunferencia  de orden 4 (que cuando el IAS es impar contiene 4 IASES) y por lo tanto es twisted. Para ver si son isomorfos queda por comprobar que los generadores dados tienen la circunferencia indicada. Mañana lo sabremos. Bueno, ya tengo a punto de nuevo el programa que hice hace bastantes años y que llevaba sin utilizar otros tantos, paara encontrar recorridos hamiltonianos dado el par de generadores (de grados 5,6,7 y 8, para cualquier tamaño de digrafo; en principio se puede adaptar fácilmente para cualquier grado pero de momento sólo lo he realizado para los grados indicados, que son aquellos de los que tenía generadores; lo voy a extender al grado 9 dado que hay casos en esta entrada:¡¡HECHO!!). Me ha costado al menos un par de horas poder volver a utilizarlo: para determinar el vértice final posible con el que se quiere trabajar, hay que hacerlo manualmente y no encontraba la variable que se debe de cambiar en cada caso y eso que la tenía bien marcada y documentada. Es un código de 31 páginas (cuando lo copio a Word), 1500 lineas (idem) y 2700 palabras. Por lo visto el número de lineas de código no es una buena métrica para determinar el esfuerzo. En cualquier caso era la primera vez que programaba, ya tenía una cierta edad y todavía me dura el dolor de cabeza…:-). Tras aplicar el algoritmo se confirma que este caso no tiene recorridos hamiltonianos en ninguno de los vértices finales posibles. No le he enseñado el teorema de ranking y lo he aplicado a los 7 posibles. En 5 de ellos lo identifica en la fase inicial cuando marca el vértice inicial y final y extrae las consecuencias de marcar estos vértices (tal y como era de esperar). Pero en dos de ellos (4782563, que no está excluido por el teorema de Rankin y 6825437, sí excluido por este mismo teorema) lo determina tras una opción, lo cual da que pensar…¿ La demostración improvisada y advirtiendo que podría ser incorrecta, que hicimos en la entrada anterior, que en teoría era válida para todos los VFs de paths tenía algún bug ?. Me fio más del algoritmo que de la demostración de hace unos días. En cualquier caso no ha tardado ni un minuto en ninguno de ellos. Con el teorema de Rankin nos podíamos haber ahorrado este minuto.

(–The group C2 x A5 of order 120 with generators of G10, s = (12)(35)(46)(79)(810) and t = (234)(678). No vamos a analizarlo de momento dado que no tengo extendido el programa a estos grados de permutaciones).

–The solvable group G of order 324 with generators of G9, s = (15)(38) and t = (123)(456)(789), es decir 528416739 y 231564897. IAS de orden 9 (18 vértices) y circunferencia 9 (9 IASES, 18×9=162 vértices si fuesen todos disjuntos). En principio todo normal. Posiblemente twisted, pero pendiente de comprobarlo. Vamos a poner este caso a prueba en el algoritmo. Tengo curiosidad por ver cuanto puede tardar. Ya está testado: no tiene RHs en ninguno de los VFs posibles. En este caso he omitido los descartables por el teorema de Rankin y quedaban 4. Como era de esperar ha tardado más que en los anteriores. Y como era de esperar ha tardado no mucho más: unos 3-4 minutos en cada VFs. Ya hemos comentado antes que estos digrafos tan restringidos suelen ser casos fáciles desde el punto de vista algorítmico, incluso cuando no tienen RHs en ninguno de los VFs posibles. En uno de los VFs una opción. En el resto sin opción. Siempre opción en el que se relaciona con la identidad por  un generador de orden mayor y de ahí al siguiente hasta que en alguno ya no haya opción. Ya hemos explicado que cuantos más IASes estén activados por el generador de orden 2, más restringido.

Nota. PSL(2,2) es isomorfo a S3, orden 6; PSL(2,3) es isomorfo a A4, 12 elementos, PSL(2,5) es isomorfo a A5, orden 60; PSL(2,9) es isomorfo a A6, orden 360; PSL(2,11) es de orden 660; PSL(2,13) es de orden 1092; PSL(2,17) tiene orden 2448. Fin de nota.

–The group PSL(2,8) has order 504 has a permutation representation with generators of G9, s = (24)(35)(68)(79) and t = (123)(467)(589). s= 145238967 y t= 231687495. Me he animado y voy a poner a prueba este también.  IAS9 (18 vértices). Circunferencia7 (7 IASES). Si todos los IASES fuesen disjuntos la circunferencia debería de contener aproximadamente 18×7=126 vértices (obviamente menos, se trata de una cota superior). 504/126 = 4. Probablemente twisted, pero tengo mis dudas. Lo he puesto a prueba y he visto que aparecían unos mensajes de error de la aplicación que no recordaba como interpretar y lo he parado. De momento he visto que no son mensajes vinculados a este caso sino que aparecen también en otros (de mucho menor tamaño por ejemplo) y que no afectan al resultado final. Pero estoy comprobando su causa. He visto que también aparecieron en casos que probé de 720 vértices así que entiendo que son falsas interpretaciones de la aplicación y en base a éstas lanza sugerencias. Lo vuelvo a poner en marcha. El vértice final posible 10,48972635 no tiene recorridos hamiltonianos. Se encontró este resultado tras 40 minutos y una opción. Este es el que tiene que tardar más tiempo. El vértice final posible {6, 7, 5, 2, 3, 10, 8, 9, 4} no tiene recorridos hamiltonianos. Se encontró este resultado tras unos 25 minutos, sin opción. Faltan dos, el tercero está ya en marcha. El vértice final posible {8, 3, 4, 10, 9, 6, 5, 2, 7} no tiene tampoco recorridos hamiltonianos. Lo sabemos tras unos 20 minutos, sin opción. Terminamos con el  último.supongo que como yo nadie espera que haya RH en este VF tampoco. Confirmamos, {5, 9, 7, 6, 2, 8, 4, 10, 3} tampoco tiene RH. En un poco más de 15 minutos, sin opción.

A la espera de los resultados del caso de 720 vértices, Todos los testados (con la excepción de uno de 24 vértices) han resultado no tener RHs en ningún vértice final posible. Y nos falta por determinar las propiedades estructurales de la  mayoría de ellos.

Notese que todos estos casos, que no están teniendo RHs en ninguno de los VFs posibles, los hemos extraído de un artículo en el que nos comentaban que cuando se convierten en grafos (añadiendo el generador inverso correspondiente) sí tienen ciclos hamiltonianos. ¿ que consecuencias puede tener esto para la conjetura correspondiente ?. Yo realmente cada vez me oriento más a que debe de ser cierta.

En los puntos siguientes revisamos otros casos similares a los (2-3) Generados. Damos de momento solo los parámetros y daremos las permutaciones más adelante. Algunos de los que aparecen en la siguiente lista han sido ya dibujados para determinar sus propiedades estructurales e incluiremos la gráfica en la entrada puntualmente. Del resto también los iremos dibujando e iremos incluyendo  sus correspondientes gráficas puntualmente.

2. (2-4) generados. 

Resumen.

de S4 hay 3. 1 twisted, 1 cycle entangled y 1 entangled.

de S5 hay 12. 3 de grado 9,  1 entangled y los otros 2 twisted; 3 de grado 8, 1 twisted y 2 entangled (los dos con IAS12); 2 de grado 7, los dos twisted; 2 de grado 6, los dos twisted; 2 de grado 5, los 2 twisted.  En total 9 twisted. Todos ellos sin RHs en ninguno de los VFs posibles.

de S6 hay 4. 2 1/2 entangled y 2 de propiedades desconocidas.

Actualización 8 de mayo 2016.

En la descripción de la patente ya dabamos un método para tratar, algorítmicamente, este tipo de casos. Se trata de activar los ciclos (de orden4) de todas las maneras posibles compatibles con la existencia de un RH. En los casos que tratamos, 2-4 generados, esto es posible, pero a medida que crezca el orden de los ciclos, será un método cada vez más ineficiente. Por ello de alguna manera nos resulta insatisfactorio. Y por ello, animados por la solución muy general que existe para los casos (2-3) generados le damos una vuelta más.

Fin de actualización.

a) RHs en todos los VFs. 

HAY 2.

–S4, 4, C2C4, IAS3, Circunferencia 2, (4 IASES). Por definición es twisted, sin embargo a la hora de dibujarlo se ve bastante smooth. Tiene RH en el único vértice final posible. Caso con total seguridad tiene varios. DIBUJADO.

–S5,G8.C2C4. IAS4. Sólo x C2. RH en todos los VFs. Esperable, teniendo en cuenta el tamaño del IAS. DIBUJADO.

b) RHs en algunos de los VFs.

HAY EN TOTAL 3, TODOS ENTANGLED.

–S4, C2C4, IAS12, Circunfrencia  2 (2 IAESes) y por lo tanto 1/2 entangled. Este caso tiene RHs en algunos VFs posibles y en otros no. DIBUJADO.

–S4, S4, 7, IAS6, Circunferencia 2 (4 IASes). Es entangled (pero no 1/2 entangled). Tiene RHs en alguno de los VFs posibles y en otros no. DIBUJADO.

–S5,G9. C2C4. IAS15. Entangled. Con algunos VFs sin RHs. Este caso ilustra que no se debe de dar nada por supuesto. Teniendo en cuenta los parámetros y las propiedades estructurales, hubiese dicho que no tenía RHs en ningún VF de los posibles. Sin embargo sí existen en dos de ellos.

VF={3, 6, 9, 2, 5, 7, 10, 4, 8}

{vi, {2, 3, 4, 6, 5, 8, 7, 10, 9}, {3, 6, 8, 5, 2, 4, 10, 7, 9}, {6,
5, 4, 2, 3, 8, 7, 10, 9}, {5, 2, 8, 3, 6, 4, 10, 7, 9}, {5,
2, 8, 6, 3, 10, 4, 9, 7}, {2, 6, 10, 3, 5, 8, 9, 4, 7}, {6,
3, 8, 5, 2, 10, 4, 9, 7}, {3, 5, 10, 2, 6, 8, 9, 4, 7}, {3,
5, 10, 6, 2, 9, 8, 7, 4}, {5, 6, 9, 2, 3, 10, 7, 8, 4}, {6,
2, 10, 3, 5, 9, 8, 7, 4}, {2, 3, 9, 5, 6, 10, 7, 8, 4}, {2,
3, 9, 6, 5, 7, 10, 4, 8}, {3, 6, 7, 5, 2, 9, 4, 10, 8}, {6,
5, 9, 2, 3, 7, 10, 4, 8}, {5, 2, 7, 3, 6, 9, 4, 10, 8}, {5,
2, 7, 6, 3, 4, 9, 8, 10}, {2, 6, 4, 3, 5, 7, 8, 9, 10}, {6,
3, 7, 5, 2, 4, 9, 8, 10}, {3, 5, 4, 2, 6, 7, 8, 9, 10}, {3,
5, 4, 6, 2, 8, 7, 10, 9}, {5, 6, 8, 2, 3, 4, 10, 7, 9}, {6,
2, 4, 3, 5, 8, 7, 10, 9}, {2, 3, 8, 5, 6, 4, 10, 7, 9}, {2,
3, 8, 6, 5, 10, 4, 9, 7}, {3, 6, 10, 5, 2, 8, 9, 4, 7}, {6,
5, 8, 2, 3, 10, 4, 9, 7}, {5, 2, 10, 3, 6, 8, 9, 4, 7}, {5,
2, 10, 6, 3, 9, 8, 7, 4}, {2, 6, 9, 3, 5, 10, 7, 8, 4}, {6,
3, 10, 5, 2, 9, 8, 7, 4}, {3, 5, 9, 2, 6, 10, 7, 8,
4}, {3, 5, 9, 6, 2, 7, 10, 4, 8}, {5, 6, 7, 2, 3, 9, 4, 10, 8}, {
6, 2, 9, 3, 5, 7, 10, 4, 8}, {2, 3, 7, 5, 6, 9, 4, 10, 8}, {
2, 3, 7, 6, 5, 4, 9, 8, 10}, {3, 6, 4, 5, 2, 7, 8, 9, 10}, {
6, 5, 7, 2, 3, 4, 9, 8, 10}, {5, 2, 4, 3, 6, 7, 8, 9, 10}, {
5, 2, 4, 6, 3, 8, 7, 10, 9}, {2, 6, 8, 3, 5, 4, 10, 7, 9}, {
6, 3, 4, 5, 2, 8, 7, 10, 9}, {3, 5, 8, 2, 6, 4, 10, 7, 9}, {
3, 5, 8, 6, 2, 10, 4, 9, 7}, {5, 6, 10, 2, 3, 8, 9, 4, 7}, {
6, 2, 8, 3, 5, 10, 4, 9, 7}, {2, 3, 10, 5, 6, 8, 9, 4, 7}, {
2, 3, 10, 6, 5, 9, 8, 7, 4}, {3, 6, 9, 5, 2, 10, 7, 8, 4}, {
6, 5, 10, 2, 3, 9, 8, 7, 4}, {5, 2, 9, 3, 6, 10, 7, 8, 4}, {
5, 2, 9, 6, 3, 7, 10, 4, 8}, {2, 6, 7, 3, 5, 9, 4, 10, 8}, {
6, 3, 9, 5, 2, 7, 10, 4, 8}, {3, 5, 7, 2, 6, 9, 4, 10, 8}, {
3, 5, 7, 6, 2, 4, 9, 8, 10}, {5, 6, 4, 2, 3, 7, 8, 9, 10}, {
6, 2, 7, 3, 5, 4, 9, 8, 10}, {6, 2, 7, 5, 3, 9, 4, 10, 8}, {
2, 5, 9, 3, 6, 7, 10, 4, 8}, {2, 5, 9, 6, 3, 10, 7,
8, 4}, {5, 6, 10, 3, 2, 9, 8, 7, 4}, {6, 3, 9, 2, 5, 10, 7,
8, 4}, {3, 2, 10, 5, 6, 9, 8, 7, 4}, {3, 2, 10, 6, 5, 8, 9,
4, 7}, {2, 6, 8, 5, 3, 10, 4, 9, 7}, {6, 5, 10, 3, 2, 8, 9,
4, 7}, {5, 3, 8, 2, 6, 10, 4, 9, 7}, {5, 3, 8, 6, 2, 4, 10, 7,
9}, {3, 6, 4, 2, 5, 8, 7, 10, 9}, {6, 2, 8, 5, 3, 4, 10, 7,
9}, {2, 5, 4, 3, 6, 8, 7, 10, 9}, {2, 5, 4, 6, 3, 7, 8, 9, 10}, {5, 6, 7,
3, 2, 4, 9, 8, 10}, {6, 3, 4, 2, 5, 7, 8, 9, 10}, {3, 2, 7, 5, 6, 4, 9,
8, 10}, {3, 2, 7, 6, 5, 9, 4, 10,
8}, {2, 6, 9, 5, 3, 7, 10, 4, 8}, {6, 5, 7, 3, 2, 9, 4, 10,
8}, {5, 3, 9, 2, 6, 7, 10, 4, 8}, {5, 3, 9, 6, 2, 10, 7, 8,
4}, {3, 6, 10, 2, 5, 9, 8, 7, 4}, {6, 2, 9, 5, 3, 10, 7, 8,
4}, {2, 5, 10, 3, 6, 9, 8, 7, 4}, {2, 5, 10, 6, 3, 8, 9, 4,
7}, {5, 6, 8, 3, 2, 10, 4, 9, 7}, {6, 3, 10, 2, 5, 8, 9, 4,
7}, {3, 2, 8, 5, 6, 10, 4, 9, 7}, {3, 2, 8, 6, 5, 4, 10, 7,
9}, {2, 6, 4, 5, 3, 8, 7, 10, 9}, {6, 5, 8, 3, 2, 4,
10, 7, 9}, {5, 3, 4, 2, 6, 8, 7, 10, 9}, {5, 3, 4, 6, 2, 7,
8, 9, 10}, {3, 6, 7, 2, 5, 4, 9, 8, 10}, {6, 2, 4, 5, 3, 7,
8, 9, 10}, {2, 5, 7, 3, 6, 4, 9, 8, 10}, {2, 5, 7, 6, 3, 9,
4, 10, 8}, {5, 6, 9, 3, 2, 7, 10, 4, 8}, {6, 3, 7, 2, 5, 9, 4, 10,
8}, {3, 2, 9, 5, 6, 7, 10, 4, 8}, {3, 2, 9, 6, 5, 10, 7, 8,
4}, {2, 6, 10, 5, 3, 9, 8, 7, 4}, {6, 5, 9, 3, 2, 10, 7,
8, 4}, {5, 3, 10, 2, 6, 9, 8, 7, 4}, {5, 3, 10, 6, 2, 8, 9,
4, 7}, {3, 6, 8, 2, 5, 10, 4, 9, 7}, {6, 2, 10, 5, 3, 8, 9,
4, 7}, {2, 5, 8, 3, 6, 10, 4, 9, 7}, {2, 5, 8, 6, 3, 4, 10,
7, 9}, {5, 6, 4, 3, 2, 8, 7, 10, 9}, {6, 3, 8, 2, 5, 4, 10,
7, 9}, {3, 2, 4, 5, 6, 8, 7, 10, 9}, {3, 2, 4, 6, 5, 7, 8,
9, 10}, {2, 6, 7, 5, 3, 4, 9, 8, 10}, {6, 5, 4, 3, 2, 7, 8,
9, 10}, {5, 3, 7, 2, 6, 4, 9, 8, 10}, {5, 3, 7, 6, 2, 9, 4, 10, 8}, vf}

Lo ha encontrado tras dos opciones.

VF={6, 2, 8, 3, 5, 10, 4, 9, 7}.Sin RH. Sin opción.

VF={2, 3, 7, 6, 5, 4, 9, 8, 10}. Sin RH. Sin opción.

VF={3, 6, 10, 2, 5, 9, 8, 7, 4}. Sin RH. Sin opción.

VF= {6, 2, 4, 3, 5, 8, 7, 10, 9}. Sin RH. Sin opción.

VF= {2, 3, 9, 6, 5, 7, 10, 4, 8}. Sin RH. Sin opción.

VF={3, 6, 8, 2, 5, 10, 4, 9, 7}.

{vi, {3, 5, 7, 6, 2, 4, 9, 8, 10}, {3, 5, 7, 2, 6, 9, 4, 10, 8}, {5,
2, 9, 6, 3, 7, 10, 4, 8}, {5, 2, 9, 3, 6, 10, 7, 8, 4}, {2,
3, 10, 6, 5, 9, 8, 7, 4}, {2, 3, 10, 5, 6, 8, 9, 4, 7}, {3,
5, 8, 6, 2, 10, 4, 9, 7}, {3, 5, 8, 2, 6, 4, 10, 7, 9}, {5,
2, 4, 6, 3, 8, 7, 10, 9}, {5, 2, 4, 3, 6, 7, 8, 9, 10}, {2,
3, 7, 6, 5, 4, 9, 8, 10}, {2, 3, 7, 5, 6, 9, 4, 10, 8}, {3,
5, 9, 6, 2, 7, 10, 4, 8}, {3, 5, 9, 2, 6, 10, 7, 8, 4}, {5,
2, 10, 6, 3, 9, 8, 7, 4}, {5, 2, 10, 3, 6, 8, 9, 4, 7}, {2,
3, 8, 6, 5, 10, 4, 9, 7}, {2, 3, 8, 5, 6, 4, 10, 7, 9}, {3,
5, 4, 6, 2, 8, 7, 10, 9}, {3, 5, 4, 2, 6, 7, 8, 9, 10}, {5,
2, 7, 6, 3, 4, 9, 8, 10}, {5, 2, 7, 3, 6, 9, 4, 10, 8}, {2,
3, 9, 6, 5, 7, 10, 4, 8}, {2, 3, 9, 5, 6, 10, 7, 8, 4}, {3,
5, 10, 6, 2, 9, 8, 7, 4}, {3, 5, 10, 2, 6, 8, 9, 4, 7}, {5,
2, 8, 6, 3, 10, 4, 9, 7}, {5, 2, 8, 3, 6, 4, 10, 7, 9}, {2,
3, 4, 6, 5, 8, 7, 10, 9}, {3, 6, 8, 5, 2, 4, 10, 7, 9}, {6,
5, 4, 2, 3, 8, 7, 10, 9}, {6, 5, 4, 3, 2, 7, 8, 9, 10}, {5, 3, 7, 2, 6,
4, 9, 8, 10}, {3, 2, 4, 6, 5, 7, 8, 9, 10}, {
2, 6, 7, 5, 3, 4, 9, 8, 10}, {2, 6, 7, 3, 5, 9, 4, 10, 8}, {
6, 3, 9, 5, 2, 7, 10, 4, 8}, {6, 3, 9, 2, 5, 10, 7, 8, 4}, {
3, 2, 10, 5, 6, 9, 8, 7, 4}, {2, 5, 9, 6, 3, 10, 7, 8, 4}, {
5, 6, 10, 3, 2, 9, 8, 7, 4}, {5, 6, 10, 2, 3, 8, 9, 4, 7}, {
6, 2, 8, 3, 5, 10, 4, 9, 7}, {6, 2, 8, 5, 3, 4, 10, 7, 9}, {
2, 5, 4, 3, 6, 8, 7, 10, 9}, {5, 3, 8, 6, 2, 4, 10, 7, 9}, {
3, 6, 4, 2, 5, 8, 7, 10, 9}, {3, 6, 4, 5, 2, 7, 8, 9, 10}, {
6, 5, 7, 2, 3, 4, 9, 8, 10}, {6, 5, 7, 3, 2, 9, 4, 10, 8}, {
5, 3, 9, 2, 6, 7, 10, 4, 8}, {3, 2, 7, 6, 5, 9, 4, 10, 8}, {
2, 6, 9, 5, 3, 7, 10, 4, 8}, {2, 6, 9, 3, 5, 10, 7, 8, 4}, {
6, 3, 10, 5, 2, 9, 8, 7, 4}, {6, 3, 10, 2, 5, 8, 9, 4, 7}, {
3, 2, 8, 5, 6, 10, 4, 9, 7}, {2, 5, 10, 6, 3, 8, 9, 4, 7}, {
5, 6, 8, 3, 2, 10, 4, 9, 7}, {5, 6, 8, 2, 3, 4, 10, 7, 9}, {
6, 2, 4, 3, 5, 8, 7, 10, 9}, {6, 2, 4, 5, 3, 7, 8,
9, 10}, {2, 5, 7, 3, 6, 4, 9, 8, 10}, {5, 3, 4, 6, 2, 7, 8,
9, 10}, {3, 6, 7, 2, 5, 4, 9, 8, 10}, {3, 6, 7, 5, 2, 9, 4,
10, 8}, {6, 5, 9, 2, 3, 7, 10, 4, 8}, {6, 5, 9, 3, 2, 10, 7,
8, 4}, {5, 3, 10, 2, 6, 9, 8, 7, 4}, {3, 2, 9, 6, 5, 10, 7, 8,
4}, {2, 6, 10, 5, 3, 9, 8, 7, 4}, {2, 6, 10, 3, 5, 8, 9, 4,
7}, {6, 3, 8, 5, 2, 10, 4, 9, 7}, {6, 3, 8, 2, 5, 4, 10, 7,
9}, {3, 2, 4, 5, 6, 8, 7, 10, 9}, {2, 5, 8, 6, 3, 4, 10, 7,
9}, {5, 6, 4, 3, 2, 8, 7, 10, 9}, {5, 6, 4, 2, 3, 7, 8, 9, 10}, {6, 2, 7,
3, 5, 4, 9, 8, 10}, {6, 2, 7, 5, 3, 9, 4, 10,
8}, {2, 5, 9, 3, 6, 7, 10, 4, 8}, {5, 3, 7, 6, 2, 9, 4, 10,
8}, {3, 6, 9, 2, 5, 7, 10, 4, 8}, {3, 6, 9, 5, 2, 10, 7, 8,
4}, {6, 5, 10, 2, 3, 9, 8, 7, 4}, {6, 5, 10, 3, 2, 8, 9, 4,
7}, {5, 3, 8, 2, 6, 10, 4, 9, 7}, {3, 2, 10, 6, 5, 8, 9, 4,
7}, {2, 6, 8, 5, 3, 10, 4, 9, 7}, {2, 6, 8, 3, 5, 4, 10, 7,
9}, {6, 3, 4, 5, 2, 8, 7, 10, 9}, {6, 3, 4, 2, 5, 7,
8, 9, 10}, {3, 2, 7, 5, 6, 4, 9, 8, 10}, {2, 5, 4, 6, 3, 7,
8, 9, 10}, {5, 6, 7, 3, 2, 4, 9, 8, 10}, {5, 6, 7, 2, 3, 9,
4, 10, 8}, {6, 2, 9, 3, 5, 7, 10, 4, 8}, {6, 2, 9, 5, 3, 10,
7, 8, 4}, {2, 5, 10, 3, 6, 9, 8, 7, 4}, {5, 3, 9, 6, 2, 10, 7, 8,
4}, {3, 6, 10, 2, 5, 9, 8, 7, 4}, {3, 6, 10, 5, 2, 8, 9, 4,
7}, {6, 5, 8, 2, 3, 10, 4, 9, 7}, {6, 5, 8, 3, 2, 4, 10,
7, 9}, {5, 3, 4, 2, 6, 8, 7, 10, 9}, {3, 2, 8, 6, 5, 4, 10,
7, 9}, {2, 6, 4, 5, 3, 8, 7, 10, 9}, {2, 6, 4, 3, 5, 7, 8,
9, 10}, {6, 3, 7, 5, 2, 4, 9, 8, 10}, {6, 3, 7, 2, 5, 9, 4,
10, 8}, {3, 2, 9, 5, 6, 7, 10, 4, 8}, {2, 5, 7, 6, 3, 9, 4,
10, 8}, {5, 6, 9, 3, 2, 7, 10, 4, 8}, {5, 6, 9, 2, 3, 10, 7,
8, 4}, {6, 2, 10, 3, 5, 9, 8, 7, 4}, {6, 2, 10, 5, 3, 8, 9,
4, 7}, {2, 5, 8, 3, 6, 10, 4, 9, 7}, {5, 3, 10, 6, 2, 8, 9, 4, 7}, vf}.

Encontrado tras una opción.

c) Sin RHs en ninguno de los VFs.

Hay 9 en total. Todos dibujados. Todos twisted.

–S5, G5. C2C4 IAS6. Circunferecnia de orden 3 (6 IASes9). Sólo x C2. No RH en ninguno de los VFs. Encuentro a este caso especialmente interesante, ya que ni el generador que no es de orden 2 ni el IAS son de un orden especialmente elevado. Pese a esto mi expectativa es que sea  sea Twisted. Confirmado, es twisted (realmente lo tenía dibujado desde hacía años pero no lo recodaba).

caso c2 c4 circ 3 twisted

–S5, G5. C2C4 IAS5. Sólo x C2. Es  un caso en el que aplica el teorema de Rankin y su generalización. No RH en ningún vértice final posible (incluso tras descartar los casos Rankin). Idem anterior, especialmente interesante. Expectativa Twisted.

Actualización 8 de mayo: Pdte de dibujar este caso. Lo he pasado otra vez con el algoritmo programado y en cada uno de los 2 VFs tarda bastante en determinar que no tiene RH: en el que más unos 10 minutos, con unas 18 llamadas de backtraking. El otro está más restringido y son 11 llamadas de backtraking.

DIBUJADO. Confirmado, es twisted, tal y como se ve en la imagen siguiente, elaborada hoy. La imagen tiene interés pues muestra también todo lo que hemos definido entorno de la identidad (los IAES numerados de 1 a 16, algunos incompletos; aparece un IAS incompleto coloreado en rojo, que no está numerado y que forma parte de la circunferencia pero no del entorno de la identidad). Como se puede ver, ya antes de dibujar el entorno completo hasta encontrar la permutación que hace el caso twisted, se podía ver  que lo iba a ser con un simple cálculo numérico. Estas mismas consideraciones nos hacen ver que muy posiblemente los otros casos que nos quedan por analizar de S5 también lo sean. Ahora se debería de estudiar este caso en concreto para determinar el mecanismo que hace imposible que tenga RHs. Se ve que precisamente es twisted en el IAS que conecta con uno de los VFs posibles.

s5 c2c4 twisted

Fin actualización.

–S5, G6. C2C4 IAS5. Sólo x C2. No RH en ninguno de los vértices finales posibles. Este es especialmente interesante dado que los órdenes de los generadores ni del IAS son especialmente elevados. ¿ Twisted ?

–S5,G6. C2C4, IAS6. Sólo x C2. Sin RH en ninguno de los VF.

–S5, G7. C2C4, IAS5. Sólo x C2. Sin RH en ninguno de los VFs.

–S5, G7. C2C4. IAS6. Circunferencia 3. Sólo x C2. Sin RHs en ninguno de los VFs posibles. En la imagen siguiente vemos este caso (que dibujé hace años). Como se aprecia el IAS azul que sale del IAS de la identidad, y que forma parte de la circunferencia, conecta con otros IASes que salen del IAS de  la identidad. Es twisted. 

C2C4 TWISTED

–S5,G8, C2C4. IAS12. Entangled not cycle entangled. Sin RH en ninguno de los VFs. También muy restringido.

–S5,G9. C2C4. IAS5. Sólo x c2. Sin RHs en ninguno de los VFs. Caso interesante. Como se ve en la imagen siguiente, Twisted.

g9c2c4

–S5,G9. C2C4. CF6. Sólo x C2. Sin RHs en ninguno de los VFs. Caso interesante. DIBUJADO.

d) Casos (2-4) generados, de S6 Pdtes de clasificar.

–S6, G8, C2C4, IAS10. 1/2 entangled. sin ciclos s/R y E.  Lo ponemos como  contraste. Comprobar si tiene paths.

s6 c2c4half entangled 1

 

–S6, G8, C2C4, IAS 10, 1/2 entangled, Sin ciclos s/RyE. Idem. Comprobar si tiene paths. ¿ en que se diferencia del anterior ?

s6 c2c4 half entangled 2

–S6, G8, C2C4, IAS5, Circunferencia 5. Sólo x C2. Pendiente de Comprobar si tiene paths.

–S6, G8, C2C4, IAS6. Circunferecnia 3 (6 IASES). Sólo x C2. Tiene ciclos s/RyE. Comprobar si tiene paths.

e) A continuación algunos casos reseñados en la entrada anterior del tipo (2,4). A continuación los que me interesan.

–XVII. As a (2,4)-group S4 has generators s=(l4) and x=(1234).

–XVIII. The group of order 48 with generators s = (35)(46) and x = (1243)(5687), es decir 12563478 y 24136857. C2C4. IAS6. Es 1/2 entangled (y por lo tanto la circunferencia es de orden 1, contiene 2 IASes).

VF= 42568397. Sin RH.

VF=84629573. Sí.

{vi, {2, 3, 6, 7, 4, 5, 8, 9}, {3, 7, 2, 6, 5, 9, 4, 8}, {7,
6, 3, 2, 9, 8, 5, 4}, {6, 2, 7, 3, 8, 4, 9, 5}, {6,
2, 8, 4, 7, 3, 9, 5}, {2, 4, 6, 8, 3, 5, 7, 9}, {4,
8, 2, 6, 5, 9, 3, 7}, {8, 6, 4, 2, 9, 7, 5, 3}, {8,
6, 9, 7, 4, 2, 5, 3}, {6, 7, 8, 9, 2, 3, 4, 5}, {7,
9, 6, 8, 3, 5, 2, 4}, {9, 8, 7, 6, 5, 4, 3, 2}, {9,
8, 5, 4, 7, 6, 3, 2}, {8, 4, 9, 5, 6, 2, 7, 3}, {4,
5, 8, 9, 2, 3, 6, 7}, {5, 9, 4, 8, 3, 7, 2, 6}, {5,
9, 3, 7, 4, 8, 2, 6}, {9, 7, 5, 3, 8, 6, 4, 2}, {7,
3, 9, 5, 6, 2, 8, 4}, {3, 5, 7, 9, 2, 4, 6, 8}, {3,
5, 2, 4, 7, 9, 6, 8}, {5, 4, 3, 2, 9, 8, 7, 6}, {4,
2, 5, 3, 8, 6, 9, 7}, {4, 2, 8, 6, 5, 3, 9, 7}, {2,
6, 4, 8, 3, 7, 5, 9}, {2, 6, 3, 7, 4, 8, 5, 9}, {6,
7, 2, 3, 8, 9, 4, 5}, {7, 3, 6, 2, 9, 5, 8, 4}, {3,
2, 7, 6, 5, 4, 9, 8}, {3, 2, 5, 4, 7, 6, 9, 8}, {2,
4, 3, 5, 6, 8, 7, 9}, {4, 5, 2, 3, 8, 9, 6, 7}, {5,
3, 4, 2, 9, 7, 8, 6}, {5, 3, 9, 7, 4, 2, 8, 6}, {3,
7, 5, 9, 2, 6, 4, 8}, {7, 9, 3, 5, 6, 8, 2, 4}, {9,
5, 7, 3, 8, 4, 6, 2}, {9, 5, 8, 4, 7, 3, 6, 2}, {5,
4, 9, 8, 3, 2, 7, 6}, {4, 8, 5, 9, 2, 6, 3, 7}, {8, 9, 4, 5, 6, 7, 2,
3}, {8, 9, 6, 7, 4, 5, 2, 3}, {9, 7, 8, 6, 5, 3, 4,
2}, {7, 6, 9, 8, 3, 2, 5, 4}, {6, 8, 7, 9, 2, 4, 3,
5}, {6, 8, 2, 4, 7, 9, 3, 5}, vf}.

VF= 98765432. Sin RH.

VF= {7, 9, 6, 8, 3, 5, 2, 4}. Sí.

{vi, {3, 5, 2, 4, 7, 9, 6, 8}, {5, 4, 3, 2, 9, 8, 7, 6}, {4,
2, 5, 3, 8, 6, 9, 7}, {4, 2, 8, 6, 5, 3, 9, 7}, {2,
6, 4, 8, 3, 7, 5, 9}, {2, 6, 3, 7, 4, 8, 5, 9}, {6,
7, 2, 3, 8, 9, 4, 5}, {7, 3, 6, 2, 9, 5, 8, 4}, {3,
2, 7, 6, 5, 4, 9, 8}, {3, 2, 5, 4, 7, 6, 9, 8}, {2,
4, 3, 5, 6, 8, 7, 9}, {2, 4, 6, 8, 3, 5, 7, 9}, {4,
8, 2, 6, 5, 9, 3, 7}, {8, 6, 4, 2, 9, 7, 5, 3}, {6,
2, 8, 4, 7, 3, 9, 5}, {6, 2, 7, 3, 8, 4, 9, 5}, {2,
3, 6, 7, 4, 5, 8, 9}, {3, 7, 2, 6, 5, 9, 4, 8}, {7,
6, 3, 2, 9, 8, 5, 4}, {7, 6, 9, 8, 3, 2, 5, 4}, {6,
8, 7, 9, 2, 4, 3, 5}, {6, 8, 2, 4, 7, 9, 3, 5}, {8,
4, 6, 2, 9, 5, 7, 3}, {8, 4, 9, 5, 6, 2, 7, 3}, {4,
5, 8, 9, 2, 3, 6, 7}, {4, 5, 2, 3, 8, 9, 6, 7}, {5,
3, 4, 2, 9, 7, 8, 6}, {5, 3, 9, 7, 4, 2, 8, 6}, {3,
7, 5, 9, 2, 6, 4, 8}, {7, 9, 3, 5, 6, 8, 2, 4}, {9,
5, 7, 3, 8, 4, 6, 2}, {9, 5, 8, 4, 7, 3, 6, 2}, {5,
4, 9, 8, 3, 2, 7, 6}, {4, 8, 5, 9, 2, 6, 3, 7}, {8,
9, 4, 5, 6, 7, 2, 3}, {8, 9, 6, 7, 4, 5, 2, 3}, {9,
7, 8, 6, 5, 3, 4, 2}, {9, 7, 5, 3, 8, 6, 4, 2}, {7,
3, 9, 5, 6, 2, 8, 4}, {3, 5, 7, 9, 2, 4, 6, 8}, {5, 9, 3, 7, 4, 8, 2,
6}, {5, 9, 4, 8, 3, 7, 2, 6}, {9, 8, 5, 4, 7, 6, 3,
2}, {9, 8, 7, 6, 5, 4, 3, 2}, {8, 6, 9, 7, 4, 2, 5,
3}, {6, 7, 8, 9, 2, 3, 4, 5}, vf}.

VF={3, 7, 5, 9, 2, 6, 4, 8}. No, 1 opción.

VF={2, 3, 6, 7, 4, 5, 8, 9}. No, 2 opciones.

XIX. The group of order 64 with generators s = (23)(67) and x = (12)(3465)(78). 13245768 y 21463587. C2C4. IAS8. 1/2 entangled. Como vamos a ver 1 resultado muy interesante. Excepto en un VF, RHs en todos los VFs. En la mayoría de ellos sólo 1 RH. 

VF={3, 2, 6, 4, 7, 5, 9, 8}. Sí, con opciones.

{vi, {2, 4, 3, 5, 6, 8, 7, 9}, {4, 2, 5, 8, 3, 6, 9, 7}, {2,
4, 8, 6, 5, 3, 7, 9}, {4, 2, 6, 3, 8, 5, 9, 7}, {4,
6, 2, 3, 8, 9, 5, 7}, {6, 4, 3, 9, 2, 8, 7, 5}, {6,
3, 4, 9, 2, 7, 8, 5}, {3, 6, 9, 7, 4, 2, 5, 8}, {3,
9, 6, 7, 4, 5, 2, 8}, {9, 3, 7, 5, 6, 4, 8, 2}, {3,
9, 5, 4, 7, 6, 2, 8}, {9, 3, 4, 6, 5, 7, 8, 2}, {9,
4, 3, 6, 5, 8, 7, 2}, {4, 9, 6, 8, 3, 5, 2, 7}, {4,
6, 9, 8, 3, 2, 5, 7}, {6, 4, 8, 2, 9, 3, 7, 5}, {6,
8, 4, 2, 9, 7, 3, 5}, {8, 6, 2, 7, 4, 9, 5, 3}, {6,
8, 7, 9, 2, 4, 3, 5}, {8, 6, 9, 4, 7, 2, 5, 3}, {8,
9, 6, 4, 7, 5, 2, 3}, {9, 8, 4, 5, 6, 7, 3, 2}, {9,
4, 8, 5, 6, 3, 7, 2}, {4, 9, 5, 3, 8, 6, 2, 7}, {4,
5, 9, 3, 8, 2, 6, 7}, {5, 4, 3, 2, 9, 8, 7, 6}, {4,
5, 2, 8, 3, 9, 6, 7}, {5, 4, 8, 9, 2, 3, 7, 6}, {5,
8, 4, 9, 2, 7, 3, 6}, {8, 5, 9, 7, 4, 2, 6, 3}, {8,
9, 5, 7, 4, 6, 2, 3}, {9, 8, 7, 6, 5, 4, 3, 2}, {9,
7, 8, 6, 5, 3, 4, 2}, {7, 9, 6, 3, 8, 5, 2, 4}, {9,
7, 3, 5, 6, 8, 4, 2}, {7, 9, 5,
8, 3, 6, 2, 4}, {7, 5, 9, 8, 3, 2, 6, 4}, {5, 7, 8,
2, 9, 3, 4, 6}, {5, 8, 7, 2, 9, 4, 3, 6}, {8, 5, 2, 4, 7, 9, 6, 3}, {8, 2,
5, 4, 7, 6, 9, 3}, {2, 8, 4, 6, 5, 7, 3, 9}, {8, 2, 6, 7, 4, 5, 9,
3}, {2, 8, 7, 5, 6, 4, 3, 9}, {2, 7, 8, 5, 6, 3, 4,
9}, {7, 2, 5, 3, 8, 6, 9, 4}, {7, 5, 2, 3, 8, 9, 6,
4}, {5, 7, 3, 9, 2, 8, 4, 6}, {5, 3, 7, 9, 2, 4, 8,
6}, {3, 5, 9, 4, 7, 2, 6, 8}, {5, 3, 4, 2, 9, 7, 8,
6}, {3, 5, 2, 7, 4, 9, 6, 8}, {3, 2, 5, 7, 4, 6, 9,
8}, {2, 3, 7, 6, 5, 4, 8, 9}, {2, 7, 3, 6, 5, 8, 4,
9}, {7, 2, 6, 8, 3, 5, 9, 4}, {7, 6, 2, 8, 3, 9, 5,
4}, {6, 7, 8, 9, 2, 3, 4, 5}, {7, 6, 9, 3, 8, 2, 5,
4}, {6, 7, 3, 2, 9, 8, 4, 5}, {6, 3, 7, 2, 9, 4, 8,
5}, {3, 6, 2, 4, 7, 9, 5, 8}, vf}

VF={6, 3, 7, 2, 9, 4, 8, 5}. Sí, con opciones.

{vi, {2, 4, 3, 5, 6, 8, 7, 9}, {4, 2, 5, 8, 3, 6, 9, 7}, {2,
4, 8, 6, 5, 3, 7, 9}, {4, 2, 6, 3, 8, 5, 9, 7}, {4,
6, 2, 3, 8, 9, 5, 7}, {6, 4, 3, 9, 2, 8, 7, 5}, {4,
6, 9, 8, 3, 2, 5, 7}, {6, 4, 8, 2, 9, 3, 7, 5}, {6,
8, 4, 2, 9, 7, 3, 5}, {8, 6, 2, 7, 4, 9, 5, 3}, {6,
8, 7, 9, 2, 4, 3, 5}, {8, 6, 9, 4, 7, 2, 5, 3}, {8,
9, 6, 4, 7, 5, 2, 3}, {9, 8, 4, 5, 6, 7, 3, 2}, {8,
9, 5, 7, 4, 6, 2, 3}, {9, 8, 7, 6, 5, 4, 3, 2}, {9,
7, 8, 6, 5, 3, 4, 2}, {7, 9, 6, 3, 8, 5, 2, 4}, {9,
7, 3, 5, 6, 8, 4, 2}, {7, 9, 5, 8, 3, 6, 2, 4}, {7,
5, 9, 8, 3, 2, 6, 4}, {5, 7, 8, 2, 9, 3, 4, 6}, {7,
5, 2, 3, 8, 9, 6, 4}, {5, 7, 3, 9, 2, 8, 4, 6}, {5,
3, 7, 9, 2, 4, 8, 6}, {3, 5, 9, 4, 7, 2, 6, 8}, {5,
3, 4, 2, 9, 7, 8, 6}, {3, 5, 2, 7, 4, 9, 6, 8}, {3,
2, 5, 7, 4, 6, 9, 8}, {2, 3, 7, 6, 5, 4, 8, 9}, {3,
2, 6, 4, 7, 5, 9, 8}, {3, 6, 2, 4, 7, 9, 5, 8}, {6,
3, 4, 9, 2, 7, 8, 5}, {3, 6, 9, 7, 4, 2, 5, 8}, {3,
9, 6, 7, 4, 5, 2, 8}, {9, 3, 7,
5, 6, 4, 8, 2}, {3, 9, 5, 4, 7, 6, 2, 8}, {9, 3, 4,
6, 5, 7, 8, 2}, {9, 4, 3, 6, 5, 8, 7, 2}, {4, 9, 6, 8, 3, 5, 2, 7}, {9, 4,
8, 5, 6, 3, 7, 2}, {4, 9, 5, 3, 8, 6, 2, 7}, {4, 5, 9, 3, 8, 2, 6,
7}, {5, 4, 3, 2, 9, 8, 7, 6}, {4, 5, 2, 8, 3, 9, 6,
7}, {5, 4, 8, 9, 2, 3, 7, 6}, {5, 8, 4, 9, 2, 7, 3,
6}, {8, 5, 9, 7, 4, 2, 6, 3}, {5, 8, 7, 2, 9, 4, 3,
6}, {8, 5, 2, 4, 7, 9, 6, 3}, {8, 2, 5, 4, 7, 6, 9,
3}, {2, 8, 4, 6, 5, 7, 3, 9}, {8, 2, 6, 7, 4, 5, 9,
3}, {2, 8, 7, 5, 6, 4, 3, 9}, {2, 7, 8, 5, 6, 3, 4,
9}, {7, 2, 5, 3, 8, 6, 9, 4}, {2, 7, 3, 6, 5, 8, 4,
9}, {7, 2, 6, 8, 3, 5, 9, 4}, {7, 6, 2, 8, 3, 9, 5,
4}, {6, 7, 8, 9, 2, 3, 4, 5}, {7, 6, 9, 3, 8, 2, 5,
4}, {6, 7, 3, 2, 9, 8, 4, 5}, vf}.

VF={7, 6, 9, 3, 8, 2, 5, 4}. Sí, sin opción, 1 sólo RH.

{vi, {3, 2, 5, 7, 4, 6, 9, 8}, {3, 5, 2, 7, 4, 9, 6, 8}, {5,
3, 7, 9, 2, 4, 8, 6}, {5, 7, 3, 9, 2, 8, 4, 6}, {7,
5, 9, 8, 3, 2, 6, 4}, {7, 9, 5, 8, 3, 6, 2, 4}, {9,
7, 8, 6, 5, 3, 4, 2}, {7, 9, 6, 3, 8, 5, 2, 4}, {9,
7, 3, 5, 6, 8, 4, 2}, {9, 3, 7, 5, 6, 4, 8, 2}, {3,
9, 5, 4, 7, 6, 2, 8}, {3, 5, 9, 4, 7, 2, 6, 8}, {5,
3, 4, 2, 9, 7, 8, 6}, {5, 4, 3, 2, 9, 8, 7, 6}, {4,
5, 2, 8, 3, 9, 6, 7}, {5, 4, 8, 9, 2, 3, 7, 6}, {4,
5, 9, 3, 8, 2, 6, 7}, {4, 9, 5, 3, 8, 6, 2, 7}, {9,
4, 3, 6, 5, 8, 7, 2}, {9, 3, 4, 6, 5, 7, 8, 2}, {3,
9, 6, 7, 4, 5, 2, 8}, {3, 6, 9, 7, 4, 2, 5, 8}, {6,
3, 7, 2, 9, 4, 8, 5}, {6, 7, 3, 2, 9, 8, 4, 5}, {7,
6, 2, 8, 3, 9, 5, 4}, {7, 2, 6, 8, 3, 5, 9, 4}, {2,
7, 8, 5, 6, 3, 4, 9}, {2, 8, 7, 5, 6, 4, 3, 9}, {8,
2, 5, 4, 7, 6, 9, 3}, {8, 5, 2, 4, 7, 9, 6, 3}, {5,
8, 4, 9, 2, 7, 3, 6}, {8, 5, 9, 7, 4, 2, 6, 3}, {5,
8, 7, 2, 9, 4, 3, 6}, {5, 7, 8, 2, 9, 3, 4, 6}, {7,
5, 2, 3, 8, 9, 6, 4}, {7, 2, 5,
3, 8, 6, 9, 4}, {2, 7, 3, 6, 5, 8, 4, 9}, {2, 3, 7,
6, 5, 4, 8, 9}, {3, 2, 6, 4, 7, 5, 9, 8}, {3, 6, 2, 4, 7, 9, 5, 8}, {6, 3,
4, 9, 2, 7, 8, 5}, {6, 4, 3, 9, 2, 8, 7, 5}, {4, 6, 9, 8, 3, 2, 5,
7}, {4, 9, 6, 8, 3, 5, 2, 7}, {9, 4, 8, 5, 6, 3, 7,
2}, {9, 8, 4, 5, 6, 7, 3, 2}, {8, 9, 5, 7, 4, 6, 2,
3}, {9, 8, 7, 6, 5, 4, 3, 2}, {8, 9, 6, 4, 7, 5, 2,
3}, {8, 6, 9, 4, 7, 2, 5, 3}, {6, 8, 4, 2, 9, 7, 3,
5}, {6, 4, 8, 2, 9, 3, 7, 5}, {4, 6, 2, 3, 8, 9, 5,
7}, {4, 2, 6, 3, 8, 5, 9, 7}, {2, 4, 3, 5, 6, 8, 7,
9}, {4, 2, 5, 8, 3, 6, 9, 7}, {2, 4, 8, 6, 5, 3, 7,
9}, {2, 8, 4, 6, 5, 7, 3, 9}, {8, 2, 6, 7, 4, 5, 9,
3}, {8, 6, 2, 7, 4, 9, 5, 3}, {6, 8, 7, 9, 2, 4, 3,
5}, {6, 7, 8, 9, 2, 3, 4, 5}, vf}.

VF=   {9, 7, 8, 6, 5, 3, 4, 2} . Sí, sin opción y por lo tanto un sólo RH.

{vi, {3, 2, 5, 7, 4, 6, 9, 8}, {3, 5, 2, 7, 4, 9, 6, 8}, {5,
3, 7, 9, 2, 4, 8, 6}, {3, 5, 9, 4, 7, 2, 6, 8}, {5,
3, 4, 2, 9, 7, 8, 6}, {5, 4, 3, 2, 9, 8, 7, 6}, {4,
5, 2, 8, 3, 9, 6, 7}, {5, 4, 8, 9, 2, 3, 7, 6}, {4,
5, 9, 3, 8, 2, 6, 7}, {4, 9, 5, 3, 8, 6, 2, 7}, {9,
4, 3, 6, 5, 8, 7, 2}, {4, 9, 6, 8, 3, 5, 2, 7}, {9,
4, 8, 5, 6, 3, 7, 2}, {9, 8, 4, 5, 6, 7, 3, 2}, {8,
9, 5, 7, 4, 6, 2, 3}, {9, 8, 7, 6, 5, 4, 3, 2}, {8,
9, 6, 4, 7, 5, 2, 3}, {8, 6, 9, 4, 7, 2, 5, 3}, {6,
8, 4, 2, 9, 7, 3, 5}, {8, 6, 2, 7, 4, 9, 5, 3}, {6,
8, 7, 9, 2, 4, 3, 5}, {6, 7, 8, 9, 2, 3, 4, 5}, {7,
6, 9, 3, 8, 2, 5, 4}, {7, 9, 6, 3, 8, 5, 2, 4}, {9,
7, 3, 5, 6, 8, 4, 2}, {9, 3, 7, 5, 6, 4, 8, 2}, {3,
9, 5, 4, 7, 6, 2, 8}, {9, 3, 4, 6, 5, 7, 8, 2}, {3,
9, 6, 7, 4, 5, 2, 8}, {3, 6, 9, 7, 4, 2, 5, 8}, {6,
3, 7, 2, 9, 4, 8, 5}, {6, 7, 3, 2, 9, 8, 4, 5}, {7,
6, 2, 8, 3, 9, 5, 4}, {7, 2, 6, 8, 3, 5, 9, 4}, {2,
7, 8, 5, 6, 3, 4, 9}, {7, 2, 5,
3, 8, 6, 9, 4}, {2, 7, 3, 6, 5, 8, 4, 9}, {2, 3, 7,
6, 5, 4, 8, 9}, {3, 2, 6, 4, 7, 5, 9, 8}, {3, 6, 2, 4, 7, 9, 5, 8}, {6, 3,
4, 9, 2, 7, 8, 5}, {6, 4, 3, 9, 2, 8, 7, 5}, {4, 6, 9, 8, 3, 2, 5,
7}, {6, 4, 8, 2, 9, 3, 7, 5}, {4, 6, 2, 3, 8, 9, 5,
7}, {4, 2, 6, 3, 8, 5, 9, 7}, {2, 4, 3, 5, 6, 8, 7,
9}, {4, 2, 5, 8, 3, 6, 9, 7}, {2, 4, 8, 6, 5, 3, 7,
9}, {2, 8, 4, 6, 5, 7, 3, 9}, {8, 2, 6, 7, 4, 5, 9,
3}, {2, 8, 7, 5, 6, 4, 3, 9}, {8, 2, 5, 4, 7, 6, 9,
3}, {8, 5, 2, 4, 7, 9, 6, 3}, {5, 8, 4, 9, 2, 7, 3,
6}, {8, 5, 9, 7, 4, 2, 6, 3}, {5, 8, 7, 2, 9, 4, 3,
6}, {5, 7, 8, 2, 9, 3, 4, 6}, {7, 5, 2, 3, 8, 9, 6,
4}, {5, 7, 3, 9, 2, 8, 4, 6}, {7, 5, 9, 8, 3, 2, 6,
4}, {7, 9, 5, 8, 3, 6, 2, 4}, vf}

VF={8, 9, 5, 7, 4, 6, 2, 3}. Sí, sin opción un sólo RH.

{vi, {3, 2, 5, 7, 4, 6, 9, 8}, {3, 5, 2, 7, 4, 9, 6, 8}, {5,
3, 7, 9, 2, 4, 8, 6}, {5, 7, 3, 9, 2, 8, 4, 6}, {7,
5, 9, 8, 3, 2, 6, 4}, {7, 9, 5, 8, 3, 6, 2, 4}, {9,
7, 8, 6, 5, 3, 4, 2}, {9, 8, 7, 6, 5, 4, 3, 2}, {8,
9, 6, 4, 7, 5, 2, 3}, {8, 6, 9, 4, 7, 2, 5, 3}, {6,
8, 4, 2, 9, 7, 3, 5}, {6, 4, 8, 2, 9, 3, 7, 5}, {4,
6, 2, 3, 8, 9, 5, 7}, {4, 2, 6, 3, 8, 5, 9, 7}, {2,
4, 3, 5, 6, 8, 7, 9}, {4, 2, 5, 8, 3, 6, 9, 7}, {2,
4, 8, 6, 5, 3, 7, 9}, {2, 8, 4, 6, 5, 7, 3, 9}, {8,
2, 6, 7, 4, 5, 9, 3}, {8, 6, 2, 7, 4, 9, 5, 3}, {6,
8, 7, 9, 2, 4, 3, 5}, {6, 7, 8, 9, 2, 3, 4, 5}, {7,
6, 9, 3, 8, 2, 5, 4}, {7, 9, 6, 3, 8, 5, 2, 4}, {9,
7, 3, 5, 6, 8, 4, 2}, {9, 3, 7, 5, 6, 4, 8, 2}, {3,
9, 5, 4, 7, 6, 2, 8}, {3, 5, 9, 4, 7, 2, 6, 8}, {5,
3, 4, 2, 9, 7, 8, 6}, {5, 4, 3, 2, 9, 8, 7, 6}, {4,
5, 2, 8, 3, 9, 6, 7}, {5, 4, 8, 9, 2, 3, 7, 6}, {4,
5, 9, 3, 8, 2, 6, 7}, {4, 9, 5, 3, 8, 6, 2, 7}, {9,
4, 3, 6, 5, 8, 7, 2}, {9, 3, 4,
6, 5, 7, 8, 2}, {3, 9, 6, 7, 4, 5, 2, 8}, {3, 6, 9,
7, 4, 2, 5, 8}, {6, 3, 7, 2, 9, 4, 8, 5}, {6, 7, 3, 2, 9, 8, 4, 5}, {7, 6,
2, 8, 3, 9, 5, 4}, {7, 2, 6, 8, 3, 5, 9, 4}, {2, 7, 8, 5, 6, 3, 4,
9}, {2, 8, 7, 5, 6, 4, 3, 9}, {8, 2, 5, 4, 7, 6, 9,
3}, {8, 5, 2, 4, 7, 9, 6, 3}, {5, 8, 4, 9, 2, 7, 3,
6}, {8, 5, 9, 7, 4, 2, 6, 3}, {5, 8, 7, 2, 9, 4, 3,
6}, {5, 7, 8, 2, 9, 3, 4, 6}, {7, 5, 2, 3, 8, 9, 6,
4}, {7, 2, 5, 3, 8, 6, 9, 4}, {2, 7, 3, 6, 5, 8, 4,
9}, {2, 3, 7, 6, 5, 4, 8, 9}, {3, 2, 6, 4, 7, 5, 9,
8}, {3, 6, 2, 4, 7, 9, 5, 8}, {6, 3, 4, 9, 2, 7, 8,
5}, {6, 4, 3, 9, 2, 8, 7, 5}, {4, 6, 9, 8, 3, 2, 5,
7}, {4, 9, 6, 8, 3, 5, 2, 7}, {9, 4, 8, 5, 6, 3, 7,
2}, {9, 8, 4, 5, 6, 7, 3, 2}, vf}.

VF={5, 8, 4, 9, 2, 7, 3, 6}. Sí, sin opción y por lo tantoun sólo RH.

{vi, {3, 2, 5, 7, 4, 6, 9, 8}, {3, 5, 2, 7, 4, 9, 6, 8}, {5,
3, 7, 9, 2, 4, 8, 6}, {3, 5, 9, 4, 7, 2, 6, 8}, {5,
3, 4, 2, 9, 7, 8, 6}, {5, 4, 3, 2, 9, 8, 7, 6}, {4,
5, 2, 8, 3, 9, 6, 7}, {5, 4, 8, 9, 2, 3, 7, 6}, {4,
5, 9, 3, 8, 2, 6, 7}, {4, 9, 5, 3, 8, 6, 2, 7}, {9,
4, 3, 6, 5, 8, 7, 2}, {4, 9, 6, 8, 3, 5, 2, 7}, {9,
4, 8, 5, 6, 3, 7, 2}, {9, 8, 4, 5, 6, 7, 3, 2}, {8,
9, 5, 7, 4, 6, 2, 3}, {8, 5, 9, 7, 4, 2, 6, 3}, {5,
8, 7, 2, 9, 4, 3, 6}, {5, 7, 8, 2, 9, 3, 4, 6}, {7,
5, 2, 3, 8, 9, 6, 4}, {5, 7, 3, 9, 2, 8, 4, 6}, {7,
5, 9, 8, 3, 2, 6, 4}, {7, 9, 5, 8, 3, 6, 2, 4}, {9,
7, 8, 6, 5, 3, 4, 2}, {9, 8, 7, 6, 5, 4, 3, 2}, {8,
9, 6, 4, 7, 5, 2, 3}, {8, 6, 9, 4, 7, 2, 5, 3}, {6,
8, 4, 2, 9, 7, 3, 5}, {8, 6, 2, 7, 4, 9, 5, 3}, {6,
8, 7, 9, 2, 4, 3, 5}, {6, 7, 8, 9, 2, 3, 4, 5}, {7,
6, 9, 3, 8, 2, 5, 4}, {7, 9, 6, 3, 8, 5, 2, 4}, {9,
7, 3, 5, 6, 8, 4, 2}, {9, 3, 7, 5, 6, 4, 8, 2}, {3,
9, 5, 4, 7, 6, 2, 8}, {9, 3, 4,
6, 5, 7, 8, 2}, {3, 9, 6, 7, 4, 5, 2, 8}, {3, 6, 9,
7, 4, 2, 5, 8}, {6, 3, 7, 2, 9, 4, 8, 5}, {6, 7, 3, 2, 9, 8, 4, 5}, {7, 6,
2, 8, 3, 9, 5, 4}, {7, 2, 6, 8, 3, 5, 9, 4}, {2, 7, 8, 5, 6, 3, 4,
9}, {7, 2, 5, 3, 8, 6, 9, 4}, {2, 7, 3, 6, 5, 8, 4,
9}, {2, 3, 7, 6, 5, 4, 8, 9}, {3, 2, 6, 4, 7, 5, 9,
8}, {3, 6, 2, 4, 7, 9, 5, 8}, {6, 3, 4, 9, 2, 7, 8,
5}, {6, 4, 3, 9, 2, 8, 7, 5}, {4, 6, 9, 8, 3, 2, 5,
7}, {6, 4, 8, 2, 9, 3, 7, 5}, {4, 6, 2, 3, 8, 9, 5,
7}, {4, 2, 6, 3, 8, 5, 9, 7}, {2, 4, 3, 5, 6, 8, 7,
9}, {4, 2, 5, 8, 3, 6, 9, 7}, {2, 4, 8, 6, 5, 3, 7,
9}, {2, 8, 4, 6, 5, 7, 3, 9}, {8, 2, 6, 7, 4, 5, 9,
3}, {2, 8, 7, 5, 6, 4, 3, 9}, {8, 2, 5, 4, 7, 6, 9,
3}, {8, 5, 2, 4, 7, 9, 6, 3}, vf}.

VF={4, 5, 2, 8, 3, 9, 6, 7}. Este VF no tiene RH tras una opción.

VF= {2, 4, 3, 5, 6, 8, 7, 9}. Sí, tras una opción.

{vi, {3, 2, 5, 7, 4, 6, 9, 8}, {2, 3, 7, 6, 5, 4, 8, 9}, {3,
2, 6, 4, 7, 5, 9, 8}, {3, 6, 2, 4, 7, 9, 5, 8}, {6,
3, 4, 9, 2, 7, 8, 5}, {6, 4, 3, 9, 2, 8, 7, 5}, {4,
6, 9, 8, 3, 2, 5, 7}, {4, 9, 6, 8, 3, 5, 2, 7}, {9,
4, 8, 5, 6, 3, 7, 2}, {4, 9, 5, 3, 8, 6, 2, 7}, {9,
4, 3, 6, 5, 8, 7, 2}, {9, 3, 4, 6, 5, 7, 8, 2}, {3,
9, 6, 7, 4, 5, 2, 8}, {3, 6, 9, 7, 4, 2, 5, 8}, {6,
3, 7, 2, 9, 4, 8, 5}, {6, 7, 3, 2, 9, 8, 4, 5}, {7,
6, 2, 8, 3, 9, 5, 4}, {6, 7, 8, 9, 2, 3, 4, 5}, {7,
6, 9, 3, 8, 2, 5, 4}, {7, 9, 6, 3, 8, 5, 2, 4}, {9,
7, 3, 5, 6, 8, 4, 2}, {9, 3, 7, 5, 6, 4, 8, 2}, {3,
9, 5, 4, 7, 6, 2, 8}, {3, 5, 9, 4, 7, 2, 6, 8}, {5,
3, 4, 2, 9, 7, 8, 6}, {3, 5, 2, 7, 4, 9, 6, 8}, {5,
3, 7, 9, 2, 4, 8, 6}, {5, 7, 3, 9, 2, 8, 4, 6}, {7,
5, 9, 8, 3, 2, 6, 4}, {7, 9, 5, 8, 3, 6, 2, 4}, {9,
7, 8, 6, 5, 3, 4, 2}, {9, 8, 7, 6, 5, 4, 3, 2}, {8,
9, 6, 4, 7, 5, 2, 3}, {9, 8, 4, 5, 6, 7, 3, 2}, {8,
9, 5, 7, 4, 6, 2, 3}, {8, 5, 9,
7, 4, 2, 6, 3}, {5, 8, 7, 2, 9, 4, 3, 6}, {5, 7, 8,
2, 9, 3, 4, 6}, {7, 5, 2, 3, 8, 9, 6, 4}, {7, 2, 5, 3, 8, 6, 9, 4}, {2, 7,
3, 6, 5, 8, 4, 9}, {7, 2, 6, 8, 3, 5, 9, 4}, {2, 7, 8, 5, 6, 3, 4,
9}, {2, 8, 7, 5, 6, 4, 3, 9}, {8, 2, 5, 4, 7, 6, 9,
3}, {8, 5, 2, 4, 7, 9, 6, 3}, {5, 8, 4, 9, 2, 7, 3,
6}, {5, 4, 8, 9, 2, 3, 7, 6}, {4, 5, 9, 3, 8, 2, 6,
7}, {5, 4, 3, 2, 9, 8, 7, 6}, {4, 5, 2, 8, 3, 9, 6,
7}, {4, 2, 5, 8, 3, 6, 9, 7}, {2, 4, 8, 6, 5, 3, 7,
9}, {2, 8, 4, 6, 5, 7, 3, 9}, {8, 2, 6, 7, 4, 5, 9,
3}, {8, 6, 2, 7, 4, 9, 5, 3}, {6, 8, 7, 9, 2, 4, 3,
5}, {8, 6, 9, 4, 7, 2, 5, 3}, {6, 8, 4, 2, 9, 7, 3,
5}, {6, 4, 8, 2, 9, 3, 7, 5}, {4, 6, 2, 3, 8, 9, 5,
7}, {4, 2, 6, 3, 8, 5, 9, 7}, vf}

XX. The group of order 72 with generators s = (23) and x = (12)(3465). 132456 y 214645. C2C4. IAS6. Sólo x C2. Circunferencia 2 (4 IASES) y por lo tanto es twisted. Resultado interesante también que mostramos a continuación. DIBUJADO. ES TWISTED. Caso interesante, ya que siendo Twisted tiene RHs  en algunos vértices finales posibles y en otros no. Es 2-twisted.

72 twisted

VF= {2, 4, 3, 5, 6, 7}. Sí 1 opción.

{vi, {3, 2, 5, 7, 4, 6}, {2, 3, 7, 6, 5, 4}, {3,
2, 6, 4, 7, 5}, {3, 6, 2, 4, 7, 5}, {6,
3, 4, 5, 2, 7}, {6, 4, 3, 5, 2, 7}, {4,
6, 5, 7, 3, 2}, {4, 5, 6, 7, 3, 2}, {5,
4, 7, 2, 6, 3}, {5, 7, 4, 2, 6, 3}, {7,
5, 2, 3, 4, 6}, {7, 2, 5, 3, 4, 6}, {2,
7, 3, 6, 5, 4}, {7, 2, 6, 4, 3, 5}, {2,
7, 4, 5, 6, 3}, {2, 4, 7, 5, 6, 3}, {4,
2, 5, 3, 7, 6}, {4, 5, 2, 3, 7, 6}, {5,
4, 3, 6, 2, 7}, {5, 3, 4, 6, 2, 7}, {3,
5, 6, 7, 4, 2}, {3, 6, 5, 7, 4, 2}, {6,
3, 7, 2, 5, 4}, {6, 7, 3, 2, 5, 4}, {7,
6, 2, 4, 3, 5}, {6, 7, 4, 5, 2, 3}, {7,
6, 5, 3, 4, 2}, {7, 5, 6, 3, 4, 2}, {5,
7, 3, 2, 6, 4}, {5, 3, 7, 2, 6, 4}, {3,
5, 2, 4, 7, 6}, {3, 2, 5, 4, 7, 6}, {2,
3, 4, 6, 5, 7}, {2, 4, 3, 6, 5, 7}, {4,
2, 6, 7, 3, 5}, {4, 6, 2, 7, 3, 5}, {6,
4, 7, 5, 2, 3}, {4, 6, 5, 3, 7, 2}, {6,
4, 3, 2, 5, 7}, {6, 3, 4, 2, 5, 7}, {3,
6, 2, 7, 4, 5}, {3, 2, 6, 7, 4, 5}, {2,
3, 7, 5, 6, 4}, {2, 7, 3, 5, 6, 4}, {7,
2, 5, 4, 3, 6}, {7, 5, 2, 4, 3, 6}, {5,
7, 4, 6, 2, 3}, {5, 4, 7, 6, 2, 3}, {4,
5, 6, 3, 7, 2}, {5, 4, 3, 2, 6, 7}, {4, 5, 2, 7, 3, 6}, {
4, 2, 5, 7, 3, 6}, {2, 4, 7, 6, 5, 3}, {
2, 7, 4, 6, 5, 3}, {7, 2, 6, 3, 4, 5}, {
7, 6, 2, 3, 4, 5}, {6, 7, 3, 5, 2, 4}, {
6, 3, 7, 5, 2, 4}, {3, 6, 5, 4, 7, 2}, {
3, 5, 6, 4, 7, 2}, {5, 3, 4, 2, 6, 7}, {
3, 5, 2, 7, 4, 6}, {5, 3, 7, 6, 2, 4}, {
5, 7, 3, 6, 2, 4}, {7, 5, 6, 4, 3, 2}, {
7, 6, 5, 4, 3, 2}, {6, 7, 4, 2, 5, 3}, {
6, 4, 7, 2, 5, 3}, {4, 6, 2, 3, 7, 5}, {4, 2, 6, 3, 7, 5}, vf}

VF={4, 5, 2, 7, 3, 6}. No, tras tres opciones.

VF= {5, 7, 4, 6, 2, 3}. Sí tras tres opciones.

{vi, {3, 2, 5, 7, 4, 6}, {3, 5, 2, 7, 4, 6}, {5,
3, 7, 6, 2, 4}, {3, 5, 6, 4, 7, 2}, {5,
3, 4, 2, 6, 7}, {5, 4, 3, 2, 6, 7}, {4,
5, 2, 7, 3, 6}, {5, 4, 7, 6, 2, 3}, {4,
5, 6, 3, 7, 2}, {4, 6, 5, 3, 7, 2}, {6,
4, 3, 2, 5, 7}, {4, 6, 2, 7, 3, 5}, {6,
4, 7, 5, 2, 3}, {6, 7, 4, 5, 2, 3}, {7,
6, 5, 3, 4, 2}, {7, 5, 6, 3, 4, 2}, {5,
7, 3, 2, 6, 4}, {5, 3, 7, 2, 6, 4}, {3,
5, 2, 4, 7, 6}, {3, 2, 5, 4, 7, 6}, {2,
3, 4, 6, 5, 7}, {2, 4, 3, 6, 5, 7}, {4,
2, 6, 7, 3, 5}, {2, 4, 7, 5, 6, 3}, {4,
2, 5, 3, 7, 6}, {4, 5, 2, 3, 7, 6}, {5,
4, 3, 6, 2, 7}, {5, 3, 4, 6, 2, 7}, {3,
5, 6, 7, 4, 2}, {3, 6, 5, 7, 4, 2}, {6,
3, 7, 2, 5, 4}, {6, 7, 3, 2, 5, 4}, {7,
6, 2, 4, 3, 5}, {7, 2, 6, 4, 3, 5}, {2,
7, 4, 5, 6, 3}, {7, 2, 5, 3, 4, 6}, {2,
7, 3, 6, 5, 4}, {2, 3, 7, 6, 5, 4}, {3,
2, 6, 4, 7, 5}, {3, 6, 2, 4, 7, 5}, {6,
3, 4, 5, 2, 7}, {6, 4, 3, 5, 2, 7}, {4,
6, 5, 7, 3, 2}, {4, 5, 6, 7, 3, 2}, {5,
4, 7, 2, 6, 3}, {5, 7, 4, 2, 6, 3}, {7,
5, 2, 3, 4, 6}, {5, 7, 3, 6, 2, 4}, {7,
5, 6, 4, 3, 2}, {7, 6, 5, 4, 3, 2}, {6, 7, 4, 2, 5, 3}, {
6, 4, 7, 2, 5, 3}, {4, 6, 2, 3, 7, 5}, {
4, 2, 6, 3, 7, 5}, {2, 4, 3, 5, 6, 7}, {
4, 2, 5, 7, 3, 6}, {2, 4, 7, 6, 5, 3}, {
2, 7, 4, 6, 5, 3}, {7, 2, 6, 3, 4, 5}, {
7, 6, 2, 3, 4, 5}, {6, 7, 3, 5, 2, 4}, {
6, 3, 7, 5, 2, 4}, {3, 6, 5, 4, 7, 2}, {
6, 3, 4, 2, 5, 7}, {3, 6, 2, 7, 4, 5}, {
3, 2, 6, 7, 4, 5}, {2, 3, 7, 5, 6, 4}, {
2, 7, 3, 5, 6, 4}, {7, 2, 5, 4, 3, 6}, {7, 5, 2, 4, 3, 6}, vf}

VF= {7, 6, 5, 3, 4, 2}. No, tras 2 opciones.

VF= {6, 3, 7, 2, 5, 4}. Sí, tras 2 opciones.

   {vi, {2, 4, 3, 5, 6, 7}, {4, 2, 5, 7, 3, 6}, {2,
4, 7, 6, 5, 3}, {4, 2, 6, 3, 7, 5}, {4,
6, 2, 3, 7, 5}, {6, 4, 3, 5, 2, 7}, {4,
6, 5, 7, 3, 2}, {6, 4, 7, 2, 5, 3}, {6,
7, 4, 2, 5, 3}, {7, 6, 2, 3, 4, 5}, {6,
7, 3, 5, 2, 4}, {7, 6, 5, 4, 3, 2}, {7,
5, 6, 4, 3, 2}, {5, 7, 4, 2, 6, 3}, {7,
5, 2, 3, 4, 6}, {5, 7, 3, 6, 2, 4}, {5,
3, 7, 6, 2, 4}, {3, 5, 6, 4, 7, 2}, {5,
3, 4, 2, 6, 7}, {3, 5, 2, 7, 4, 6}, {3,
2, 5, 7, 4, 6}, {2, 3, 7, 6, 5, 4}, {3,
2, 6, 4, 7, 5}, {3, 6, 2, 4, 7, 5}, {6,
3, 4, 5, 2, 7}, {3, 6, 5, 7, 4, 2}, {3,
5, 6, 7, 4, 2}, {5, 3, 7, 2, 6, 4}, {5,
7, 3, 2, 6, 4}, {7, 5, 2, 4, 3, 6}, {7,
2, 5, 4, 3, 6}, {2, 7, 4, 6, 5, 3}, {7,
2, 6, 3, 4, 5}, {2, 7, 3, 5, 6, 4}, {2,
3, 7, 5, 6, 4}, {3, 2, 5, 4, 7, 6}, {3,
5, 2, 4, 7, 6}, {5, 3, 4, 6, 2, 7}, {5,
4, 3, 6, 2, 7}, {4, 5, 6, 7, 3, 2}, {5,
4, 7, 2, 6, 3}, {4, 5, 2, 3, 7, 6}, {4,
2, 5, 3, 7, 6}, {2, 4, 3, 6, 5, 7}, {2,
3, 4, 6, 5, 7}, {3, 2, 6, 7, 4, 5}, {3,
6, 2, 7, 4, 5}, {6, 3, 7, 5, 2, 4}, {3,
6, 5, 4, 7, 2}, {6, 3, 4, 2, 5, 7}, {6, 4, 3, 2, 5, 7}, {
4, 6, 2, 7, 3, 5}, {4, 2, 6, 7, 3, 5}, {
2, 4, 7, 5, 6, 3}, {2, 7, 4, 5, 6, 3}, {
7, 2, 5, 3, 4, 6}, {2, 7, 3, 6, 5, 4}, {
7, 2, 6, 4, 3, 5}, {7, 6, 2, 4, 3, 5}, {
6, 7, 4, 5, 2, 3}, {6, 4, 7, 5, 2, 3}, {
4, 6, 5, 3, 7, 2}, {4, 5, 6, 3, 7, 2}, {
5, 4, 3, 2, 6, 7}, {4, 5, 2, 7, 3, 6}, {
5, 4, 7, 6, 2, 3}, {5, 7, 4, 6, 2, 3}, {
7, 5, 6, 3, 4, 2}, {7, 6, 5, 3, 4, 2}, {6, 7, 3, 2, 5, 4}, vf} .

VF= {3, 2, 6, 4, 7, 5}. Sí, tras 2 opciones.

{vi, {2, 4, 3, 5, 6, 7}, {4, 2, 5, 7, 3, 6}, {2,
4, 7, 6, 5, 3}, {4, 2, 6, 3, 7, 5}, {4,
6, 2, 3, 7, 5}, {6, 4, 3, 5, 2, 7}, {6,
3, 4, 5, 2, 7}, {3, 6, 5, 7, 4, 2}, {3,
5, 6, 7, 4, 2}, {5, 3, 7, 2, 6, 4}, {5,
7, 3, 2, 6, 4}, {7, 5, 2, 4, 3, 6}, {7,
2, 5, 4, 3, 6}, {2, 7, 4, 6, 5, 3}, {7,
2, 6, 3, 4, 5}, {2, 7, 3, 5, 6, 4}, {2,
3, 7, 5, 6, 4}, {3, 2, 5, 4, 7, 6}, {3,
5, 2, 4, 7, 6}, {5, 3, 4, 6, 2, 7}, {5,
4, 3, 6, 2, 7}, {4, 5, 6, 7, 3, 2}, {4,
6, 5, 7, 3, 2}, {6, 4, 7, 2, 5, 3}, {6,
7, 4, 2, 5, 3}, {7, 6, 2, 3, 4, 5}, {6,
7, 3, 5, 2, 4}, {7, 6, 5, 4, 3, 2}, {7,
5, 6, 4, 3, 2}, {5, 7, 4, 2, 6, 3}, {5,
4, 7, 2, 6, 3}, {4, 5, 2, 3, 7, 6}, {4,
2, 5, 3, 7, 6}, {2, 4, 3, 6, 5, 7}, {2,
3, 4, 6, 5, 7}, {3, 2, 6, 7, 4, 5}, {3,
6, 2, 7, 4, 5}, {6, 3, 7, 5, 2, 4}, {3,
6, 5, 4, 7, 2}, {6, 3, 4, 2, 5, 7}, {6,
4, 3, 2, 5, 7}, {4, 6, 2, 7, 3, 5}, {4,
2, 6, 7, 3, 5}, {2, 4, 7, 5, 6, 3}, {2,
7, 4, 5, 6, 3}, {7, 2, 5, 3, 4, 6}, {7,
5, 2, 3, 4, 6}, {5, 7, 3, 6, 2, 4}, {5,
3, 7, 6, 2, 4}, {3, 5, 6, 4, 7, 2}, {5, 3, 4, 2, 6, 7}, {
3, 5, 2, 7, 4, 6}, {3, 2, 5, 7, 4, 6}, {
2, 3, 7, 6, 5, 4}, {2, 7, 3, 6, 5, 4}, {
7, 2, 6, 4, 3, 5}, {7, 6, 2, 4, 3, 5}, {
6, 7, 4, 5, 2, 3}, {6, 4, 7, 5, 2, 3}, {
4, 6, 5, 3, 7, 2}, {4, 5, 6, 3, 7, 2}, {
5, 4, 3, 2, 6, 7}, {4, 5, 2, 7, 3, 6}, {
5, 4, 7, 6, 2, 3}, {5, 7, 4, 6, 2, 3}, {
7, 5, 6, 3, 4, 2}, {7, 6, 5, 3, 4, 2}, {
6, 7, 3, 2, 5, 4}, {6, 3, 7, 2, 5, 4}, {3, 6, 2, 4, 7, 5}, vf}

3. (2-5) Generados. 

Los ordenamos en función de sus propiedades de hamiltonicidad: primero con RHs en todos los Vfs posibles; luego con RHs en algunos de los VFs posibles y finalmente sin RHs en ninguno de los VFs posibles.

a) Con RHs en todos los VFs posibles.

–S5, G5. C2C5 IAS4. Sólo x C2. Lo pongo como contraste. RHs en todos los vértices finales posibles. ¿ Smooth ?

–S5, G6. C2C5 IAS4. Sólo x C2. Contraste. RH en todos los vértices finales posibles.

–S5, G7. C2C5. IAS4. Sólo x C2. RHs en todos los VFs. Contraste.

–S5,G9. C2c5. IAS4. Sólo x C2. RHs en todos los VFs posibles.

b) RHs en algunos de los VFs posibles.

–S5, G5. C2C5 IAS 6. Sólo x C2. RHs en dos vértices finales posibles. Interesante. ¿ Twisted ?.

–S5, G6. C2C5 IAS6. Sólo x C2. Algunos de los vértices finales posibles, tienen RH otros no.

–S5, G7. C2C5. IAS6. RH en algunos de los VFs.

–S5, G7. C2C5. IAS 6. 1/2 entangled y RH en algunos de los VF posibles (pero en ninguno de los dos ciclos). Este caso es interesante pues demuestra que ser 1/2 entangled no excluye tener RH en alguno de los VFs.

–S5,G8. C2C5.IAS6. Sólo x C2. RHs en algunos de los VFs.

–S5,G8. C2C5.IAS6. 1/2 Entangled. RHs en algunos de los VFS. Lo mismo que comentado anteriormente.

–S5,G9.C2C5, IAS6. 1/2 Entangled. RHs sólo en algunos VFs.

–S5,G9. C2C5. IAS6. Sólo x C2. RHs sólo en un VF. Caso interesante.

c) Sin RHs en todos los VFs posibles. 

–S5, G7. C2C5. IAS10. 1/2 entangled. Sin RHs.

–S5, G8. C2C5. IAS10. 1/2 entangled. Sin RHs.

–S5,G9. C2C5, IAS10. 1/2 entangled. Sin RHs.

d) Pendientes de testar en el algoritmo para luego ser clasificados.

–S6, G6, C2C5, IAS6. Sólo x C2. Dibujado(en parte). Circunferencia 2 de 4 IASES. Tiene ciclos según Effler y Ruskey.  Quedaría por comprobar si tiene paths.

–S6, G8, C2C5, IAS4. Circunferencia 5. Sólo x C2. Tiene ciclos según Ruskey y Effler.

4. (2-6) Generados.

–S5,G5. C2C6 IAs6. Sólo x C2. Tiene un RH en sólo un vértice final posible. Expectativa Twisted.

c2c6ias6 twisted

–S5, G5. C2C6 IAS5. Sólo x C2. Idem anterior. ¿ Smooth ?.

–S5, G6. C2C6. IAS5. Sólo x C2. Contraste. RH en todos los VF.

–S5, G6. C2C6, IAS4. Sólo x C2. Contraste. RH en todos los VF.

–S5,G6. C2C6, IAS6. Sólo x C2. RH en sólo 1 de los VFs.

–S5, G7. C2C6. IAS5. Sólo x C2. Idem anterior.

–S5, G7. C2C6. IAS5. RH en todos los VFs.

–S5, G7. C2C6. IAS4. Sólo x C2. RHs en todos los VFs.

–S5, G7. C2C6. IAS6. Sólo x C2. RH en uno de los VFs posibles. No en el resto.

–S5,G8. C2C6. IAS5. RHS en todos los VFs.

–S5,G8, C2C6. IAS6. Sólo x C2. RH en sólo  un VF.

–S5,G8, C2C6. IAS5. Sólo x C2. RHs en todos los VFs.

–S5,G9. C2C6, IAS15. Entangled. RHs sólo en algunos VFs.

–S5,G9. C2C6, IAS5. Sólo x C2. RHs en todos los VFs.

–S5,G9. C2C6. IAS4. Sólo x C2. RHs en todos los VFs posibles.

–S5,G9. C2C6. IAS6. Sólo x C2. RHs en al menos un VF. Revisar. Caso interesante.

–S5,G9. C2C6. IAS10. CE-1. Siin RHs pero revisar.

–S5,G9. C2C6. IAS5. Sólo x C2. RHs en todos los VFs.

–S5,G9. C2C6. IAS10. Cycle Entangled. Sin RHs pero quiero revisarlo.

5. (2-10) Generados y similares.

a). RHs en todos los VFs posibles. 

–S5, G7. C2C10, IAS 3. Sólo x C2. RH en todos los VFs. Contraste.

–S5, G7. C2C10. IAS 5. Sólo x c2. RH en todos los VFs. Contraste.

–S5,G8, C2C10. IAS3. Sólo x C2. RHs en todos los VFs.

–S5,G9. C2C10, IAS3. Sólo x C2. RHs en todos los VFs.

–S5, G8, C2C10.IAS5. Sólo x C2. RHs en todos los VFs.

–S5,G8, C2C12. IAS4. Sólo x C2. RHs en todos los VFs.

–S5,G8, C2C12. IAS4. Sólo x C2. RHs en todos los VFs.

–S5,G9. C2C10. IAS5. Sólo x C2. RHs en todos los VFs.

b). RHs en algunos de los VFs posibles.

–S5,G9. C2C20. IAS15. Cycle entangled. Tiene RHs en algunos de los VF posibles. De lo que anoté en la base de datos, no me quedan claras sus propiedades de hamiltonicidad.

–S5,G9. C2C10. IAS6. Cycle entangled. RHs en sólo 1 de los VFs posibles. Tengo que revisar este caso.

–S5,G9. C2C15. IAS4. Sólo x C2. RHs en todos los VFs.

c) Sin RHs. 

–S5,G8.C2C10. IAS6. Sólo x C2. Sin RHs.

–S5,G9. C2C15, IAS6. Sólo x C2. Sin RHs según anoté pero debería comprobarlo. ¿ Twisted ? La circunferencia es de orden 5 y como el IAS es par contiene 10 IASES. 

–S5,G8, C2C10. IAS12. Entangled not cycle entangled. Sin RH en ninguno de los VFs. Según anoté en mis base de datos, 2 opciones máximo. Es decir es muy restringido.

–S5,G9. C2C15. IAS20. Cycle entangled. Sin RHs.

6. Otros casos pendientes de ordenar.

–PSL(2,7). C2 C7 de orden 168. Generadores 1327564 y 7123456 (extraigo este caso de un input que puse a prueba en el programa hace ya varios años…).

–A5: cada par de permutaciones del conjunto siguiente lo genera:

EXAMPLE
µ(Alt(5)) = 8. We can consider
X := {(1, 2, 3), (3, 4, 5), (1, 2, 3, 4, 5), (1, 2, 3, 5, 4), (1, 2, 4, 3, 5),
(1, 2, 4, 5, 3), (1, 2, 5, 3, 4), (1, 2, 5, 4, 3)}

7. Casos de S6 pendientes de ordenar en los puntos anteriores.

En varias entradas anteriores hemos revisado casos de S6 cuyas propiedades de hamiltonicidad nos sorprendieron. En este presentamos los casos cuyo uno de los generadores es de orden 2 sobre los que (pienso) no hemos comentado en esas entradas. Pero puede haber duplicaciones, es decir casos que aparezcan aquí y en las anteriores entradas.

–S6, G6, C2C6, IAS5. Circunferencia 5. RHs en todos los vértices finales posibles.

–S6, G6, C2C6 IAS6, Circunferencia 2 (de 4 IASES). Tienen ciclos según Ruskey y Effler.

–S6, G6, C2C6, IAS 6. Circunferencia 3 (6 IASES). Tiene ciclos según Ruskey y Effler.

–S6, G6, C2C6, IAS 6. Circunferencia 3. Tiene ciclos según Ruskey y Effler.  ¿ En que se diferencia este del anterior ?

–S6, G8, C2C6, IAS12, Entangled, Tiene ciclos según Ruskey y Effler.

–S6, G8, C2C6, IAS6, Sólo x C2. Ciclos según R y E.

–S6, G8, C2C6, IAS4, Sólo x C2. Cicloe según R y E.

–S6, G8, C2C6, IAS6, Sólo x C2, con ciclos según R y Effler.

–S6, G8, C2C6, IAS12, Sólo xC2. con ciclos s/ R y E.

–S6, G9, C2C15, IAS3.

–S6, G9, C2C15, IAS15.

En la lista anterior aparecen todos los de C2c4, c2c5 (ya se han copiado a sus respectivos sitios). Faltan los casos de C2c6 y de c2 c10 de G8.

Anexo. (2-3) generadores para An y Sn.

1.Artículo de GA Miller que da la forma de los (2-3) generadores de Sn y An para todo n>8.

ON THE GBOUPS GENEEATED BY TWO OPEKATOKS. BY DE. G. A. MILLER.

Aclara que los grupos 2-2 generados son siempre dihédricos.

Extracto.

We proceed to prove that Sx and S2 may be so chosen that they generate the alternating group and also so that they generate the symmetric group of every degree n > 8.

Let s1 = (a1a2a3) (a4a5a6) (a(d-2)a(d-1)ad) (con d el grado de la permutación) y s´2= (a3a4)(a5a6)(a(d-2)a(d-1)).  It is clear that s1s´2 is a circular substitution of degree d. We shall form s2 by adding suitable transpositions to s’2. In what follows p= n — a will be used to represent a prime number such that n — 2 > p > n/2  and it will be assumed that n > 11 unless the contrary is stated. When n = d and a is odd, we may obtain generators of the alternating and the symmetric group by multiplying s´2 by a1*asubindice(3a+1)/2 y and a1*asubindice((3a-1)/2*a(n-4)a(n-1) respectively….

Luego continua con más casuística y recomendamos leer el artículo. Como conclusión:

When n < 12, it is easy to examine the cases directly and thus prove that every alternating group with the exception of those of degrees 3, 6, 7, 8 ‘is generated by two of its substitutions of orders two and three respectively, and every symmetric group with the exception of those of degrees 5, 6, S is generated by two of its substitutions of the same orders. Hence 6 and 8 are the only degrees for which neither the symmetric nor the alternating group is generated by two of its substitutions of orders two and three respectively. 

2. En la  misma linea y muy interesante también:

GENERATING SETS. KEITH CONRAD. 

In this handout, we look at generating sets of the groups Sn, An, SL2(Z), GLn(R), and SLn(R). The following table summarizes some the generating sets we will obtain for various groups, and indicates where the proofs are found. At the end we discuss minimal generating sets, which have some counterintuitive properties in nonabelian groups.

generating sets

Corollary 2.6. For n ≥ 3, Sn is generated by (12) and the (n − 1)-cycle (23 . . . n).

Proof. This is immediate from Theorem 2.5 since (12 . . . n) = (12)(23 . . . n).

We’ve found a pair of generators for Sn consisting of a transposition and n-cycle, and then a transposition and (n − 1)-cycle. These have orders 2 and n, and then 2 and n − 1.

How small can the orders of a pair of generators of Sn be?

Theorem 2.7. For n ≥ 3 except for n = 5, 6, 8, Sn is generated by an element of order 2 and an element of order 3. We omit the proof of this theorem. It was first proved by G. A. Miller [2] in 1901, and his proof relied on a choice of a prime between n and n/2, so it was not explicit in terms of n.  

An explicit set of generators of order 2 and 3 was given by Dey and Wiegold [1] in 1971, unaware of Miller’s earlier work. As an example, S9 is generated by (14)(28)(59) and (123)(456)(789). While Sn is generated by the particular transposition (12) and n-cycle (12 . . . n), it is usually not true that Sn is generated by an arbitrary transposition and n-cycle. For instance, (13) and (1234) do not generate S4. The reason is that these two permutations preserve congruences mod 2 (if two numbers in 1, 2, 3, 4 are both even or both odd, applying either permutation to them returns values that are both even or both odd), so the subgroup they generate in S4 has this property while S4 does not have this property.

Theorem 3.6.

For n ≥ 3 except for n = 6, 7, 8, An is generated by an element of order 2 and an element of order 3. We omit the proof. As an example, A9 is generated by (14)(29)(37)(56) and (123)(456)(789).

Y el artículo citado que complementa al de Miller.

3. GENERATORS FOR ALTERNATING AND SYMMETRIC GROUPS I. M. S. DEY and JAMES WIEGOLD (Received 15 May 1969) Communicated by G. E. Wall

¡¡¡ Muy interesante !!!.

4.

  1. Marston Conder, Generators for alternating and symmetric groups, J. London Math. Soc. (2) 22 (1980), no. 1, 75–86.[MR]
  2. Marston Conder, More on generators for alternating and symmetric groups, Quart. J. Math. Oxford Ser. (2) 32 (1981), no. 126, 137–163.[MR]

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: