Grafo de Tutte-Coxeter
# Grafo de Tutte-Coxeter

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 $_2$ (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. El grafo de Tutte-Coxeter es uno de los 13 grafos de este tipo.

Tiene número de cruces 13, espesor de libro 3 y número de colas 2.

## Construcciones y automorfismos

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_6,$ y cada arista del grafo de Tutte-Coxeter conecta una coincidencia perfecta de $K_6$ con cada una de sus tres aristas componentes. Por simetría, cada arista de $K_6$ 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_6;$ 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.

## El gráfico de Tutte-Coxeter como edificio

Este grafo es el edificio esférico asociado al grupo simpléctico $Sp_{4}(\mathbb {F} _{2})$ (hay un isomorfismo excepcional entre este grupo y el grupo simétrico $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 $V$ sobre $\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 $W\subset V$ si y solo si $v\in W$.

## Galería

* 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.
