Conde de Thatta-Coxeter | |
---|---|
Lleva el nombre de |
William TuttHarold Coxeter |
picos | treinta |
costillas | 45 |
Diámetro | cuatro |
Circunferencia | ocho |
automorfismos | 1440 (Aut(S 6 )) |
Número cromático | 2 |
índice cromático | 3 |
Propiedades |
cúbica
Celda distancia transitiva |
El gráfico de Tutt-Coxeter (también Tutt de 8 celdas ) es un gráfico de 3 regulares con 30 vértices y 45 aristas. El único gráfico cúbico más pequeño con una circunferencia de 8 es la celda y el gráfico de Moore . Es bipartito y se puede construir como el gráfico de Levi de un cuadrilátero generalizado W 2 (conocido como la configuración de Cremona-Richmond ). Nombrado por William Thomas Tutt y Harold Coxeter . Encontrado por William Tutte ( Tutte 1947), pero su conexión con la combinación geométrica es explorada por ambos autores en un par de trabajos conjuntos ( Tutte, 1958 , Coxeter (a), 1958 ).
Es uno de los trece gráficos regulares de distancia cúbica [1] .
Coxeter ( Coxeter (b) 1958 ) propuso una construcción combinatoria particularmente simple del gráfico de Tutt-Coxeter y se basa en los primeros trabajos de D. D. Sylvester ( Sylvester 1844 ): formamos un conjunto de seis elementos (por ejemplo, estos son las letras a, b, c, d, e, f); Sylvester definió dos como 15 pares desordenados de elementos: ab, ac, ad, ae, af, bc, bd, be, bf, cd, ce, cf, de, df o ef. También definió conjuntos : particiones de elementos en tres pares: (ab, cd, ef); (ab, ce, df); (ab, cf, de); (ac, bd, ef); (ac, ser, df); (ac, bf, de); (ad, bc, ef); (anuncio, ser, cf); (anuncio, bf, ce); (ae, bc, df); (ae, bd, cf); (ae, bf, cd); (af, bc, de); (af, bd, ce); (af, ser, cd). Cada conjunto contiene 3 2 y cada 2 pertenece a 3 conjuntos. Un gráfico de Tutta-Coxeter se puede considerar como un gráfico en el que cada vértice corresponde a un 2 y un conjunto de 2: un vértice para cada conjunto y los bordes conectan cada conjunto con los tres 2 que contiene.
Con base en esta construcción, Coxeter demostró que el gráfico de Tutt-Coxeter es simétrico . Tiene 1440 automorfismos gráficos , que pueden identificarse con automorfismos del grupo de permutación de seis elementos ( Coxeter(b) 1958 ). Los automorfismos internos de este grupo corresponden a permutaciones de seis elementos a partir de los cuales definimos morfemas y conjuntos. Estas permutaciones actúan sobre el gráfico de Tutte-Coxeter permutando los vértices de cada parte del gráfico bipartito, manteniendo cada parte como un conjunto. Además, los automorfismos externoslos grupos de permutación intercambian las partes de un gráfico bipartito. Como mostró Coxeter, cualquier camino de hasta cinco aristas en el gráfico de Tutt-Coxeter es equivalente a cualquier otro camino (es decir, se trasladan de uno a otro usando uno de estos automorfismos).
El número de intersecciones del gráfico de Tutt-Coxeter es 13.
El número cromático del Conde Tutte-Coxeter es 2.
el índice cromático del gráfico de Tutt-Coxeter es 3.