Gráfico de Tutte-Coxeter

En el campo matemático de la teoría de grafos , el grafo de Tutte-Coxeter , también conocido como jaula de ocho vértices de Tutte o grafo de Cremona-Richmond, es un grafo 3-regular con 30 vértices y 45 aristas. Como el único grafo cúbico más pequeño de circunferencia 8, es una jaula y un grafo de Moore . Es bipartito y puede construirse como el grafo de Levi del cuadrilátero generalizado W2 (conocido como la configuración de Cremona-Richmond ). El grafo recibe su nombre de William Thomas Tutte y HSM 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).

Se conocen todos los grafos cúbicos regulares en distancia . ^{[ 1 ]} El grafo de Tutte-Coxeter es uno de los 13 grafos de este tipo.

Tiene cruce número 13, ^{[ 2 ] [ 3 ]} grosor del libro 3 y cola número 2. ^{[ 4 ]}

El grafo de Tutte-Coxeter es el grafo bipartito de Levi que conecta los 15 emparejamientos perfectos de un grafo completo K₆ _de 6 vértices con sus 15 aristas, tal como lo describió Coxeter (1958b), basándose en el trabajo de Sylvester (1844). Cada vértice corresponde a una arista o un emparejamiento perfecto, y los vértices conectados representan la estructura de incidencia entre aristas y emparejamientos.

Basándose en esta construcción, Coxeter demostró que el grafo de Tutte-Coxeter es un grafo simétrico ; posee 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 la permutación de los seis vértices del grafo K₆ ; estas permutaciones actúan sobre el grafo de Tutte-Coxeter permutando los vértices de cada lado de su bipartición _, manteniendo fijos ambos lados como conjuntos. Además, los automorfismos externos del grupo de permutaciones intercambian un lado de la bipartición por el otro. Como demostró Coxeter, cualquier camino de hasta cinco aristas en el grafo de Tutte-Coxeter es equivalente a cualquier otro camino de este tipo mediante un automorfismo de este tipo.

Este gráfico es el edificio esférico asociado al grupo simpléctico.${\displaystyle Sp_{4}(\mathbb {F} _{2})}$(existe un isomorfismo excepcional entre este grupo y el grupo simétrico)${\displaystyle S_{6}}$). Más específicamente, es el gráfico de incidencia de un cuadrilátero generalizado .

Concretamente, el grafo de Tutte-Coxeter se puede definir a partir de un espacio vectorial simpléctico de 4 dimensiones.${\displaystyle V}$encima${\displaystyle \mathbb {F} _{2}}$como sigue:

• Los vértices son vectores distintos de cero o subespacios isotrópicos bidimensionales.
• Hay una arista entre un vector no nulo v y un subespacio bidimensional isotrópico.${\displaystyle W\subset V}$si y solo si${\displaystyle v\in W}$.

• 
  El número cromático del gráfico de Tutte-Coxeter es 2.
• 
  El índice cromático del gráfico de Tutte-Coxeter es 3.

• Coxeter, HSM (1958a). "Las cuerdas de la cuádrica no reglada en PG(3,3)" . Can. J. Math . 10 : 484–488 . doi : 10.4153/CJM-1958-047-0 .
• Coxeter, HSM (1958b). "Doce puntos en PG(5,3) con 95040 autotransformaciones". Proceedings of the Royal Society A . 247 (1250): 279– 293. Bibcode : 1958RSPSA.247..279C . doi : 10.1098/rspa.1958.0184 . JSTOR 100667 . S2CID 121676627 .  
• Sylvester, JJ (1844). "Investigaciones elementales en el análisis de la agregación combinatoria" . Phil. Mag . Serie 3. 24 : 285–295 . doi : 10.1080/14786444408644856 .
• Tutte, WT (1947). "Una familia de grafos cúbicos". Proc. Cambridge Philos. Soc . 43 (4): 459– 474. Bibcode : 1947PCPS...43..459T . doi : 10.1017/S0305004100023720 . S2CID 123505185 . 
• Tutte, WT (1958). "Las cuerdas de la cuádrica no reglada en PG(3,3)" . Can. J. Math . 10 : 481–483 . doi : 10.4153/CJM-1958-046-3 .

• François Labelle. "Modelo 3D de la jaula de 8 de Tutte" .
• Weisstein, Eric W. "Grafo de Levi" . MathWorld .
• Exoo, G. "Dibujos rectilíneos de gráficos famosos."