El teorema de Frucht es un resultado de la teoría de grafos algebraicos , conjeturado por Dénes Kőnig en 1936 [1] y demostrado por Robert Frucht en 1939 [2] . Afirma que todo grupo finito es el grupo de simetrías de un grafo finito no dirigido . Más fuertemente, para cualquier grupo finito G existen infinitos grafos simples conexos no isomorfos tales que el grupo de automorfismos de cada uno de ellos es isomorfo a G.
La idea principal de la prueba es observar que el grafo de Cayley de G , con la adición de colores y orientaciones en sus aristas para distinguir los generadores de G entre sí, tiene el grupo de automorfismos deseado. Por lo tanto, si cada una de estas aristas se reemplaza por un subgrafo apropiado, de modo que cada subgrafo de reemplazo sea en sí mismo asimétrico y dos reemplazos sean isomorfos si y solo si reemplazan aristas del mismo color, entonces el grafo no dirigido creado al realizar estos reemplazos también tendrá a G como su grupo de simetría. [3]
Con tres excepciones –los grupos cíclicos de órdenes 3, 4 y 5– cada grupo puede ser representado como las simetrías de un grafo cuyos vértices tienen sólo dos órbitas . Por lo tanto, el número de vértices en el grafo es como máximo el doble del orden del grupo. Con un conjunto mayor de excepciones, la mayoría de los grupos finitos pueden ser representados como las simetrías de un grafo transitivo de vértices , con un número de vértices igual al orden del grupo. [4]
Existen versiones más fuertes del teorema de Frucht que muestran que ciertas familias restringidas de grafos aún contienen suficientes grafos para realizar cualquier grupo de simetría. Frucht [5] demostró que, de hecho, existen una cantidad contable de grafos 3-regulares con la propiedad deseada; por ejemplo, el grafo de Frucht , un grafo 3-regular con 12 vértices y 18 aristas, no tiene simetrías no triviales, lo que proporciona una realización de este tipo para el grupo trivial . Gert Sabidussi demostró que cualquier grupo puede realizarse como los grupos de simetría de una cantidad contable de grafos k - regulares distintos , grafos k -conexos por vértices o grafos k -cromáticos , para todos los valores enteros positivos k (con para grafos regulares y para grafos k -cromáticos). [6] De los hechos de que cada grafo puede ser reconstruido a partir del orden parcial de contención de sus aristas y vértices, que cada orden parcial finito es equivalente por el teorema de representación de Birkhoff a una red distributiva finita , se sigue que cada grupo finito puede ser realizado como las simetrías de una red distributiva, y del grafo de la red, un grafo mediano . [3] Es posible realizar cada grupo finito como el grupo de simetrías de un grafo fuertemente regular . [7] Cada grupo finito también puede ser realizado como las simetrías de un grafo con número distintivo dos: uno puede (incorrectamente) colorear el grafo con dos colores de modo que ninguna de las simetrías del grafo conserve la coloración. [8]
Sin embargo, algunas clases importantes de grafos son incapaces de realizar todos los grupos como sus simetrías. Camille Jordan caracterizó los grupos de simetría de los árboles como el conjunto más pequeño de grupos finitos que contienen el grupo trivial y cerrado bajo productos directos entre sí y productos de corona con grupos simétricos ; [9] en particular, el grupo cíclico de orden tres no es el grupo de simetría de un árbol. Los grafos planares tampoco son capaces de realizar todos los grupos como sus simetrías; por ejemplo, los únicos grupos simples finitos que son simetrías de grafos planares son los grupos cíclicos y el grupo alternante . [10] De manera más general, cada familia de grafos menores-cerrados es incapaz de representar todos los grupos finitos por las simetrías de sus grafos. [11] László Babai conjetura, más fuertemente, que cada familia menor-cerrada puede representar solo un número finito de grupos simples finitos no cíclicos. [12]
Izbicki amplió estos resultados en 1959 y demostró que había una cantidad incontable de grafos infinitos que realizaban cualquier grupo de simetría finito. [13] Finalmente, Johannes de Groot y Sabidussi en 1959/1960 demostraron independientemente que cualquier grupo (abandonando el supuesto de que el grupo fuera finito, pero con el supuesto del axioma de elección ) podía realizarse como el grupo de simetrías de un grafo infinito. [14] [15]
