En el campo matemático de la teoría de grafos , el gráfico de Tutte-Coxeter o el gráfico de ocho jaulas de Tutte o el gráfico de Cremona-Richmond es un gráfico de 3 regulares con 30 vértices y 45 aristas. Como el gráfico cúbico más pequeño único de circunferencia 8, es una jaula y un gráfico de Moore . Es bipartito y puede construirse como el gráfico de Levi del cuadrilátero generalizado W 2 (conocido como configuración Cremona-Richmond ). El gráfico lleva el nombre de William Thomas Tutte y HSM Coxeter ; fue descubierto por Tutte (1947), pero ambos autores investigaron su conexión con las configuraciones geométricas en un par de artículos publicados conjuntamente (Tutte 1958; Coxeter 1958a).
Se conocen todas las gráficas cúbicas de distancia regular . [1] El Tutte-Coxeter es uno de los 13 gráficos de este tipo.
Tiene cruce número 13, [2] [3] espesor de libro 3 y cola número 2. [4]
El gráfico de Tutte-Coxeter es el gráfico de Levi bipartito que conecta las 15 coincidencias perfectas de un gráfico completo de 6 vértices K 6 con sus 15 aristas, como lo describe Coxeter (1958b), basado en el trabajo de Sylvester (1844). Cada vértice corresponde a una arista o una coincidencia perfecta, y los vértices conectados representan la estructura de incidencia entre aristas y coincidencias.
Con base en 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 de seis elementos (Coxeter 1958b). Los automorfismos internos de este grupo corresponden a permutar los seis vértices del gráfico K 6 ; estas permutaciones actúan sobre el gráfico de Tutte-Coxeter permutando los vértices a cada lado de su bipartición mientras mantienen cada uno de los dos lados fijos como un conjunto. Además, los automorfismos externos del 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 (existe un isomorfismo excepcional entre este grupo y el grupo simétrico ). Más concretamente, es la gráfica 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:
