Pensamientos de altos vuelos sobre la Conjetura Restringida de Lovasz.

Parte de lo que sigue puede ser incorrecto. 

1. Toda investigación exige un calentamiento de motores y una vez que estos se han puesto en marcha y luego se apagan, el movimiento mental sigue su propia inercia, hasta que su propio impulso cesa si no lo alimentas.

A raíz de ciertos interrogantes relacionados con los sistemas RH calenté motores sobre un tema de investigación al que hacía tiempo que no le dedicaba atención:  la investigación relacionada con la patente, es decir sobre los Recorridos Hamiltonianos en Dígrafos de Caley Bigenerados.

Tras el calentamiento de motores dediqué un fin de semana muy productivo (de los más productivos en bastante tiempo,  más de un año) justo antes de mi reciente viaje a encontrar una fórmula que permitiese contar el número de Recorridos Hamiltonianos en  Digrafos de Cayley Bigenerados de Grupos Cuaternios. Creo que con buenos resultados (aunque todavía tengo pendiente revisarlo).  

Y finalmente durante un reciente largo viaje en avión (de ahí el título)

experimenté el fenómeno de la inercia mental investigadora: aunque dediqué la mayor parte de mi  energía mental durante este viaje a preparar varias reuniones que tenía que desarrollar durante él, sin provocarlo, al contrario, pese a intentar evitarlos, emergieron durante el vuelo pensamientos sobre un problema sobre el que nunca he investigado explícitamente (mi motivación para estudiar estos objetos era otra), aunque si creo que he realizado al menos una entrada sobre ella: la Conjetura Restringida de Lovasz.

Cómo tenía un  bloc de notas (físico) a mano apunté estos “pensamientos” y en esta entrada quiero resumir lo que escribí, que no se si se sostendrá.

2. Lo que pensé sobre esta Conjetura se resume en las siguientes secuencias de proposiciones, primero relativas a Grupos y luego a Dígrafos / Grafos de Cayley (ambos siempre finitos), que no son los mismos objetos que los grupos (algunas de las proposiciones son teoremas con total seguridad, otros no tengo claro si se pueden expresar cómo teoremas y entonces aparecen entre signos de interrogación, y otras son conjeturas). En lo que sigue utilizamos la palabra producto y expresable de manera no técnica:

a) ¿ Teorema 1? sobre grupos: Todo los grupos finitos son generables cómo “productos” de grupos simples (producto directo, producto semi-directo etc…).

Otra manera de expresarlo es que todo grupo finito se puede descomponer en grupos finitos simples. Esta segunda formulación diría que si es teorema pero lo que no está bien caracterizado es cómo obtener todos los grupos finitos dados los grupos finitos simples (cómo veremos los productos directos, produtos semidirectos no agotan todas las posibilidades de “combinación de grupos finitos simples). Pero quizás para nuestros objetivos nos sirva con esta segunda formulación.

Esto nos lleva a la teoría de extensiones de grupos que desconozco completamente, pero que parece que no está todavía cerrada.

One extension, the direct product, is immediately obvious. If one requires G and Q to be abelian groups, then the set of isomorphism classes of extensions of Q by a given (abelian) group N is in fact a group, which is isomorphic to

\operatorname{Ext}^1_{\mathbb Z}(Q,N);

cf. the Ext functor.

Several other general classes of extensions are known but no theory exists which treats all the possible extensions at one time. Group extension is usually described as a hard problem; it is termed the extension problem.

To consider some examples, if G = H × K, then G is an extension of both H and K. More generally, if G is a semidirect product of Kand H, then G is an extension of H by K, so such products as the wreath product provide further examples of extensions.

Este teorema es clave para todo el asunto y si no es tal, el edificio cae. En un interesante foro sobre esto, en el que por cierto aparecen los grupos cuaternios cómo ejemplo, dicen:

Also, this is probably a horribly naive question, but just like the extension problem has been completely solved for the case of finite abelian groups through the use of direct products, why doesn’t the use of semidirect products solve the problem for all finite groups?.

Y la respuesta en el mismo foro:

Semidirect products are easily classified. The problem is that many group extensions are not semidirect products; in fact, the extensions which are semidirect products are precisely the ones that split. Ver splitting lema.

Otro participante pregunta:

Doesn’t the classification of all finite simple groups essentially classify all finite groups? But group theory wouldn’t be over since we still have infinite groups to contend with..

Y la respuesta:

No. The Jordan-Hölder theorem tells us that any finite group can be built using extensions out of finite simple groups. We have classified the finite simple groups, but we don’t know all of the ways of putting them together (by extensions) in general. Thus, in some sense, the classification of finite groups is only half done.

Más sobre extensiones de grupos aquí. Y también aquí, en una entrada en un blog:

A second major theme in finite group theory is the extension problem for finite groups. If simple groups are analogous to atoms, then it’s worth noting that chemistry was far from finished when the Periodic Table was first published. Chemists wanted to understand the ways in which atoms could combine to form bigger molecules. So what are the equivalents of covalent and ionic bonds in the case of finite groups? What limits are there on the compound structures which can be built? A complete answer to this question would constitute a classification of all finite groups. But this isn’t thought to be a viable goal at present. In full generality it seems inaccessibly hard. However various instances of the extension problem form the focus of much mathematical attention. 

Finalmente señalar la importancia del teorema de Jordan-Holder.

Por lo tanto parece claro que el interrogante es legítimo.

b) Teorema 2 sobre grupos. Todo grupo finito simple es bigenerable.

Esto si es un teorema.

Estas dos proposiciones para grupos nos dan las dos siguientes proposiciones para Dígrafos de Cayley

c)  ¿ Teorema 1 ? relativo a Dígrafos de Cayley (correspondiente al teorema 1 sobre grupos). Todo los Dígrafos de Cayley (relevantes para el problema hamiltoniano, es decir si un Digrafo de Cayley ya se ha demostrado hamiltoniano, añadir arcos entre sus vértices no lo hace más difícil de cara al problema RH) son expresables mediante productos de DC bigenerados.

d) ¿ Teorema 2 ?, correspondiente al teorema 2 sobre grupos y relativo a DC bigenerados. Todo Dígrafo de Cayley de un grupo simple es bigenerable. Diría que esto es teorema pero no estoy seguro.

Que se deben de completar con estas dos conjeturas:

e) Conjetura 1 sobre RH en DC bigenerados. Todo Digrafo de Cayley Bigenerado, cuando se convierte en Grafo (añadiendo el número mínimo correspondiente de arcos) tiene ciclos hamiltonianos. Creo que esto podría ser demostrable con los resultados de la patente.

f) Conjetura 2 sobre RH en DC.  Todo Grafo de Cayley obtenido cómo “producto” de Grafos de Cayley bigenerados (y por lo tanto hamiltonianos), es hamiltoniano. Esto diría que también debería de ser demostrable (ya se ha demostrado para algunos casos restringidos.

Actualización 18/3/2013. 

Primero quede claro que de lo que aquí estamos hablando no es más que una estrategia de ataque a esta conjetura. El punto que tengo menos claro es el ¿ teorema 1?. Por ello he estado leyendo algo sobre productos de grupos finitos.

Queda claro que no todos los grupos se pueden expresar cómo producto directo o producto semidirecto (en el producto directo los dos factores son normales, en el semidirecto sólo se exige que uno sea normal; hay otro tipo de producto, que generaliza a los anteriores  que, llamado bicrossed product o Zappa-Szép product o knit product, en el que ninguno de los dos factores es normal; pero me temo que incluso incluyendo este tercer tipo tampoco se agotan todas las posibilidades…).

Aquí lo dicen claramente con respecto al directo y semidirecto.

Let’s say we have a group G containing a normal subgroup H. What are the possible relationships we can have between G, H, and G/H? Looking at groups of small order, it seems to always be the case that G = G/H x H or G/H x| H. What, if any, other constructions/relations are possible? And why is it the case that there are or aren’t any other possible constructions/relations(if this question admits a relatively elementary answer)?

Y algunas respuestas:

There are other possibilities. Take G=Z/4Z,H=2Z/4Z. Then G/H=Z/2Z is not a subgroup of G, so G can’t be either a direct or semidirect product of H and G/H.

y

Anyway, my understanding is that this is actually fairly nontrivial. Seeen.wikipedia.org/wiki/Group_extension#Extension_problem . For finite groups, seeen.wikipedia.org/wiki/Schur%E2%80%93Zassenhaus_theorem


A %d blogueros les gusta esto: