Como me interesé

en Grafos y Grupos

Roberto W. Frucht

UNIVERSIDAD SANTA MARÍA

VALPARAISO. CHILE

Cuando ingresé a la universidad de Berlín en 1924 a la edad de 18 años, no había decidido aún si estudiaría matemáticas o física -- ambos campos me parecían apasionantes y fascinantes. Sin embargo, después de un par de períodos me dí cuenta que no tenía la habilidad manual requerida para física experimental y elegí las matemáticas. Mi "primer amor" fue cálculo tensorial y sus aplicaciones a las grandes dimensiones de la geometría diferencial, pero en ese tiempo había serias dificultades en encontrar a un profesor guía para un doctorado en esta área. Por otra parte, me había convertido en un admirador del estilo lúcido de las charlas del difunto I. Schur, así es que un día le pregunté si me aceptaría como candidato a Ph.D. Me aceptó, pero bajo una condición bien obvia: mi tesis debía ser en una de sus áreas de interés. Así fue cómo me cambié a teoría de grupos y escribí mi tesis [1] bajo su dirección.

Mi padre perdió su empleo al mismo tiempo y tuve que encontrar cómo ganarme la vida. Gente más joven a menudo me pregunta por qué no me metí en computadores; la respuesta es bastante obvia: los computadores aún no existían en 1930, y en ese entonces era bastante difícil para un matemático encontrar empleo en Alemania (quizá con la excepción de enseñar matemáticas en una escuela, para lo cual había que ser ciudadano alemán; yo era ciudadano de Checoeslovaquia).

Así es que acepté empleo como actuario en una compañía de seguros italiana y me trasladé a Trieste (Italia), donde permanecí hasta fines de 1938. Mi trabajo tenía poca relación con matemáticas; en vez de ésto, yo tenía que dictar cartas en alemán a una secretaria italiana, la cual pronto perdió su empleo a pesar de ser muy eficiente -- porque se convirtió en mi esposa. [Este año (1982) es nuestro cincuentenario].

Este período de mi vida fué bastante aburrido desde el punto de vista matemático, hasta que un día en 1936 recibí un catálogo de Akademische Verlagsgesellschaft que contenía una descripción del libro de König [9]. Inmediatamente encargué este libro, ya que el capítulo 8 prometía aplicaciones a teoría de grupos y me convertí en un entusiasta teórico de grafos desde el momento que lo recibí.

Más que en estas "aplicaciones" (que representaban una descripción de los diagramas clásicos de Cayley), me interesé en dos problemas acerca de grupos de automorfismo de grafos que König formula en su libro.

Para empezar con uno de los más fáciles: En la página 194, König pide el grupo de automorfismo del grafo Petersen. Este realmente es un problema fácil -- en [8] éste es el ejercicio 14.11 en la página 176 -- ya que König mismo da una pista que ya es un paso esencial de la solución (específicamente, representar los diez puntos del grafo Petersen con los pares no ordenados 12, 13, ..., 45, donde dos puntos son adyacentes si y sólo si los pares de números correspondientes no tienen un número en común).

Así es que no tuve dificultad en resolver este problema demostrando que el grupo en cuestión es isomórfico a S_5. Pero ésto no me pareció suficiente para justificar publicación, así es que también determiné los grupos de automorfismo de otros grafos que se me ocurrieron, específicamente aquéllos formados por los vértices y arcos de los sólidos platónicos (ver [2]).

Después pasé al problema más difícil formulado en la página 5 del libro de König: ¿ Cuándo es posible representar un grupo abstracto dado como el grupo de automorfismo de un grafo y -- si éste fuese el caso -- cómo puede construírse este grafo?

Sólo después de varios meses de infructuosos esfuerzos tuve la suerte de encontrar una solución que parece bastante fácil una vez encontrada: sólo es necesario comenzar con el ya mencionado diagrama de Cayley para un grupo dado. Es cierto que éste no es un grafo ordinario ya que sus líneas son dirigidas y "coloreadas", pero puede transformarse en un grafo ordinario (sin alterar el grupo de automorfismo) por medio de un truco descrito en [3] o también en [8, pp. 168, 169]. Así es que la respuesta a la pregunta de König es afirmativa para cualesquier grupo de orden finito mayor que 1.

Es curioso que no me dí cuenta que el mismo truco también funciona para el grupo de orden 1, de modo que no noté el grafo de identidad más pequeño con 6 puntos y en vez de éso dí un árbol con 7 puntos como ejemplo de un grafo de identidad. (Ambos pueden verse en [8, Fig. 14.1]). El lector también podrá preguntarse por qué no noté el grafo trivial con un punto. No es que no lo haya notado, sino que de acuerdo con la definición de "grafo" restrictiva de König, K₁ no era un grafo (ver [3, p.249]), donde hice notar que Pólya [12, p 182] ya había reconocido la conveniencia de admitir K_1.)

En 1939 escapé de Italia a Sudamérica antes del comienzo de la Segunda Guerra Mundial, y después de trabajar brevemente como actuario en Argentina llegué a la Universidad Santa María. Tenía la esperanza que mi nueva profesión de profesor universitario me dejaría suficiente tiempo para continuar con mi investigación acerca de grafos con grupo de automorfismo dado, pero éste no fué el caso por diversas razones. Después de unos años, el profesor H.S.M. Coxeter me invitó a contribuír un artículo a la nueva revista Canadian Journal of Mathematics. En [4] me apuré en considerar el mismo problema de encontrar grafos con grupo dado, pero agregando la condición de que los grafos debían ser regulares de grado 3 (o cúbicos), no obstante con la esperanza de obtener grafos con un número menor de puntos. Desgraciadamente escribí este artículo con demasiado apuro, y como fué señalado por Milgram [11], los límites dados en [4, Teorema 4.1] no son correctos -- por lo menos si se admiten generadores redundantes. Y si digo [4, p.371] que "no logré encontrar un grafo con 9 vértices (o menos)" para el grupo de orden 3, fué culpa mía -- hay sólo un grafo con 9 puntos y 15 líneas. (En la literatura a veces se encuentra la aserción errada de que hay más de un grafo de ese tipo). Dicho de otra manera, el teorema 3.2 en [4] (Para un grupo cíclico H de orden h>3 hay un grafo con 3h puntos cuyo grupo es isomórfico a H) es cierto también para h = 3, y no sólo para h>3 como dicho. Mejores límites fueron obtenidos más adelante por Meriwether [10] y otros.

Mi próximo artículo de teoría de grafos [5] es ahora sólo de interés histórico. Después de escribir su famoso artículo [14] acerca de jaulas en el cual Tutte introdujo la idea de grafos cúbicos s-regulares, éste preguntó si existían grafos de ese tipo con s=1. (Estos son grafos simétricos cuyo grupo de automorfismo tiene un orden igual a tres veces el número de puntos del grafo). Tuve el orgullo de encontrar tal grafo con 432 puntos y lo describí en [5]. En ese tiempo se pensaba que estos grafos eran algo excepcional, pero 15 años más adelante C. C. Sims [13] descubrió que otros grafos bien conocidos eran 1-regular, con el más pequeño de sólo 26 puntos.

No aburriré al lector con descripciones de mis otros artículos acerca de grafos y grupos -- la mayoría siendo artículos escritos junto con otros autores, donde es difícil saber cuánto mérito (si hubiese alguno) le corresponde a mi persona.

Quisiera terminar haciendo notar que mi interés en la teoría de grafos no se ha limitado a grupos de automorfismo; en los últimos doce años me ha atraído un problema más general, específicamente el de una descripción económica de grafos especiales o familias de grafos. Dos soluciones han sido propuestas para este problema en [6] y [7].

REFERENCIAS

[1] R. Frucht, Über die Darstellung endlicher Abelscher Gruppen durch

Kollineationen. J. Reine Angew. Math. 166 (1931) 16-29.

[2] R. Frucht, Die Gruppe des Petersenschen Graphen und der Kantensysteme der

regulären Polyeder. Comment. Math. Helv. 9 (1936) 217-223.

[3] R. Frucht, Herstellung von Graphen mit vorgegebener abstrakter Gruppe.

Compositio Math, 6 (1938) 239-250.

[4] R. Frucht, Graphs of degree three with given abstract group. Canad. J. Math,1

(1949) 365-378.

[5] R. Frucht, A one-regular graph of degree three. Canad, J. Math, 4 (1952) 240-247.

[6] R. Frucht, How to describe a graph. Ann. N. Y. Acad, Sci, 175 (1970) 159-167.

[7] R. Frucht, A canonical representation of trivalent hamiltonian graphs.

J. Graph Theory 1 (1977) 45-60.

[8] F. Harary, Graph Theory. Addison-Wesley, Reading, Mass. (1969)

[9] D. König, Theorie der endlichen und unendlichen Graphen (Kombinatorische Topologie der

Streckenkomplexe). Akademische Verlagsgesellschaft, Leipzig (1936).

[10] R.L. Meriwether, unpublished. (See Exercise 14.7 in [8, p. 176]).

[11] M. Milgram, written communication to the author (unpublished).

[12] G. Pólya, Kombinatorische Anzahlbestimmungen fur Gruppen, Graphen und chemische

Verbindungen, Acta Math. 68 (1937) 145-254.

[13] C.C. Sims, written communication to R.M. Foster.

[14] W.T. Tutte, A family of cubical graphs. Proc. Cambridge Philos. Soc, 43(1947) 459-474.