Grafo de Tutte-Coxeter

Grafo de Tutte-Coxeter
Nombre en honor a	W. T. Tutte H. S. M. Coxeter
Vértices	30
Aristas	45
Radio	4
Diámetro	4
Cintura	8
Automorfismos	1440 (Aut(S6))
Número cromático	2
Índice cromático	3
Propiedades	Cúbico Jaula Grafo de Moore Simétrico Distancia-regular Distancia-transitivo Bipartito
[editar datos en Wikidata]

En el campo matemático de la teoría de grafos, el grafo de Tutte-Coxeter o grafo de ocho jaulas 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 cintura 8, es una jaula y un grafo de Moore. Es bipartito y se puede construir como el grafo de Levi del cuadrilátero generalizado W ₂ (conocido como la configuración de Cremona-Richmond). Lleva el nombre de William Thomas Tutte y de H. S. M. Coxeter. Aunque fue descubierto por Tutte (1947), 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 de distancia regular cúbicos.^[1]​ El grafo de Tutte-Coxeter es uno de los 13 grafos de este tipo.

Tiene número de cruces 13,^[2]​^[3]​ espesor de libro 3 y número de colas 2.^[4]​

Una construcción combinatoria particularmente simple del grafo de Tutte-Coxeter se debe a Coxeter (1958b), basada en el trabajo de Sylvester (1844). En terminología moderna, se toma un grafo completo en 6 vértices K_6, que tiene15 aristas y también 15 combinaciones perfectas. Cada vértice del grafo de Tutte-Coxeter corresponde a una arista o coincidencia perfecta de K₆, y cada arista del grafo de Tutte-Coxeter conecta una coincidencia perfecta de K₆ con cada una de sus tres aristas componentes. Por simetría, cada arista de K₆ pertenece a tres coincidencias perfectas. Además, esta partición de vértices en vértices de arista y vértices coincidentes muestra que el grafo de Tutte-Coxeter es bipartito.

Sobre la base de esta construcción, Coxeter demostró que el grafo de Tutte-Coxeter es un grafo 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₆; estas permutaciones actúan sobre el grafo 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 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 grafo 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 ${\displaystyle Sp_{4}(\mathbb {F} _{2})}$ (hay un isomorfismo excepcional entre este grupo y el grupo simétrico ${\displaystyle S_{6}}$). Más específicamente, es el grafo 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}$ sobre ${\displaystyle \mathbb {F} _{2}}$ como sigue:

• Los vértices son vectores distintos de cero o subespacios bidimensionales isotrópicos.
• Hay uns arista entre un vector v distinto de cero 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, H. S. M. (1958a). «The chords of the non-ruled quadric in PG(3,3)». Can. J. Math. 10: 484-488. doi:10.4153/CJM-1958-047-0. 
• Coxeter, H. S. M. (1958b). «Twelve points in PG(5,3) with 95040 self-transformations». Proceedings of the Royal Society A 247 (1250): 279-293. doi:10.1098/rspa.1958.0184. 
• Sylvester, J. J. (1844). «Elementary researches in the analysis of combinatorial aggregation». Phil. Mag. Series 3 24: 285-295. doi:10.1080/14786444408644856. 
• Tutte, W. T. (1947). «A family of cubical graphs». Proc. Cambridge Philos. Soc. 43 (4): 459-474. doi:10.1017/S0305004100023720. 
• Tutte, W. T. (1958). «The chords of the non-ruled quadric in PG(3,3)». Can. J. Math. 10: 481-483. doi:10.4153/CJM-1958-046-3. 

• François Labelle. «3D Model of Tutte's 8-cage». 
• Weisstein, Eric W. «Levi Graph». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 
• Exoo, G. "Rectilinear Drawings of Famous Graphs." [1]