Gráfico de Tutte-Coxeter
En el campo matemático de la teoría de grafos , el gráfico de Tutte-Coxeter o gráfico de ocho jaulas de Tutte o gráfico de Cremona-Richmond es un gráfico regular de 3 con 30 vértices y 45 aristas. Como el único gráfico cúbico más pequeño de circunferencia 8, es una jaula y un gráfico de Moore . Es bipartita y se puede construir como el gráfico de Levi del cuadrilátero generalizado W 2 (conocido como la configuración de Cremona-Richmond ). El gráfico lleva el nombre de William Thomas Tutte yHSM Coxeter ; fue descubierto por Tutte (1947), pero su conexión con las configuraciones geométricas fue investigada por ambos autores en un par de artículos publicados conjuntamente (Tutte 1958; Coxeter 1958a).
Una construcción combinatoria particularmente simple del gráfico de Tutte-Coxeter se debe a Coxeter (1958b), basada en el trabajo de Sylvester (1844). En terminología moderna, tome un gráfico completo en 6 vértices K 6 . Tiene 15 aristas y también 15 combinaciones perfectas . Cada vértice del gráfico de Tutte-Coxeter corresponde a una arista o coincidencia perfecta de K 6 , y cada arista del gráfico de Tutte-Coxeter conecta una coincidencia perfecta de K 6 con cada una de sus tres aristas componentes. Por simetría, cada borde del K 6pertenece a tres emparejamientos perfectos. Por cierto, esta partición de vértices en vértices de borde y vértices coincidentes muestra que el gráfico de Tutte-Coxeter es bipartito.
Sobre la base de esta construcción, Coxeter demostró que el gráfico de Tutte-Coxeter es un gráfico simétrico ; tiene un grupo de 1440 automorfismos , que pueden identificarse con los automorfismos del grupo de permutaciones sobre seis elementos (Coxeter 1958b). Los automorfismos internos de este grupo corresponden a permutar los seis vértices del grafo K 6 ; estas permutaciones actúan sobre el gráfico de Tutte-Coxeter al permutar los vértices de cada lado de su bipartición mientras se mantienen fijos cada uno de los dos lados como un conjunto. Además, los automorfismos externosdel grupo de permutaciones intercambian un lado de la bipartición por el otro. Como mostró Coxeter, cualquier camino de hasta cinco aristas en el gráfico de Tutte-Coxeter es equivalente a cualquier otro camino por uno de esos automorfismos.
Este grafo es el edificio esférico asociado al grupo simpléctico (hay un isomorfismo excepcional entre este grupo y el grupo simétrico ). Más específicamente, es el gráfico de incidencia de un cuadrilátero generalizado .
Concretamente, el gráfico de Tutte-Coxeter se puede definir a partir de un espacio vectorial simpléctico de 4 dimensiones de la siguiente manera:
