El teorema de Frucht es un teorema 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 gráficos conectados simples no isomorfos tales que el grupo de automorfismo de cada uno de ellos es isomorfo a G.
La idea principal de la prueba es observar que el gráfico de Cayley de G , con la adición de colores y orientaciones en sus bordes para distinguir los generadores de G entre sí, tiene el grupo de automorfismo deseado. Por lo tanto, si cada uno de estos bordes se reemplaza por un subgrafo apropiado, de modo que cada subgrafo de reemplazo sea en sí mismo asimétrico y dos reemplazos sean isomórficos si y solo si reemplazan bordes del mismo color, entonces el gráfico no dirigido creado al realizar estos reemplazos también lo será. tener G como su grupo de simetría. [3]
Con tres excepciones (los grupos cíclicos de orden 3, 4 y 5), cada grupo puede representarse como las simetrías de un gráfico cuyos vértices tienen sólo dos órbitas . Por tanto, el número de vértices del gráfico es como máximo el doble del orden del grupo. Con un conjunto más amplio de excepciones, la mayoría de los grupos finitos se pueden representar como las simetrías de un gráfico transitivo de vértices , con un número de vértices igual al orden del grupo. [4]
Existen versiones más sólidas del teorema de Frucht que muestran que ciertas familias restringidas de gráficos todavía contienen suficientes gráficos para realizar cualquier grupo de simetría. Frucht [5] demostró que, de hecho, existen muchos grafos de 3 regulares con la propiedad deseada; por ejemplo, el gráfico de Frucht , un gráfico de 3 regulares 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 un número contable de k - gráficos regulares distintos , k - gráficos conectados por vértices o k - gráficos cromáticos , para todos los valores enteros positivos k (con para gráficos regulares y para k - gráficos cromáticos). [6] Del hecho de que cada gráfico puede reconstruirse a partir del orden parcial de contención de sus aristas y vértices, de que cada orden parcial finito es equivalente según el teorema de representación de Birkhoff a una red distributiva finita , se deduce que cada grupo finito puede realizarse como las simetrías de una red distributiva, y de la gráfica de la red, una gráfica mediana . [3] Es posible realizar cada grupo finito como el grupo de simetrías de un gráfico fuertemente regular . [7] Cada grupo finito también puede realizarse como las simetrías de un gráfico con el número distintivo dos: uno puede colorear (incorrectamente) el gráfico con dos colores para que ninguna de las simetrías del gráfico conserve la coloración. [8]
Sin embargo, algunas clases importantes de gráficos son incapaces de representar todos los grupos como sus simetrías. Camille Jordan caracterizó los grupos de simetría de árboles como el conjunto más pequeño de grupos finitos que contienen el grupo trivial y cerrados bajo productos directos entre sí y productos coronados 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 gráficos planos tampoco son capaces de representar todos los grupos como sus simetrías; por ejemplo, los únicos grupos finitos simples que son simetrías de gráficos planos son los grupos cíclicos y el grupo alterno . [10] De manera más general, cada familia de grafos cerrados menores es incapaz de representar todos los grupos finitos mediante las simetrías de sus grafos. [11] László Babai conjetura, con más fuerza, que cada familia cerrada menor puede representar sólo un número finito de grupos simples finitos no cíclicos. [12]
Izbicki amplió estos resultados en 1959 y demostró que había incontables gráficos infinitos que realizaban cualquier grupo de simetría finito. [13] Finalmente, Johannes de Groot y Sabidussi en 1959/1960 demostraron de forma independiente que cualquier grupo (eliminando el supuesto de que el grupo sea finito, pero con el supuesto del axioma de elección ) podría realizarse como el grupo de simetrías de un gráfico infinito. . [14] [15]
