En el campo matemático de la teoría de grafos , el gráfico de Clebsch es cualquiera de dos gráficos complementarios en 16 vértices, un gráfico de 5 regulares con 40 aristas y un gráfico de 10 regulares con 80 aristas. El gráfico de 80 aristas es el gráfico de cubo dividido por la mitad de dimensión 5 ; Seidel (1968) [2] lo llamó gráfico de Clebsch debido a su relación con la configuración de 16 líneas en la superficie cuártica descubierta en 1868 por el matemático alemán Alfred Clebsch . La variante de 40 aristas es el gráfico de cubo plegado de dimensión 5 ; también se conoce como gráfico de Greenwood-Gleason por el trabajo de Robert E. Greenwood y Andrew M. Gleason (1955), quienes lo utilizaron para evaluar el número de Ramsey R (3,3,3) = 17. [3] [ 4] [5]
El gráfico de cubo plegado de 5 dimensiones (el gráfico de Clebsch de 5 dimensiones regulares) se puede construir agregando aristas entre pares opuestos de vértices en un gráfico de hipercubo de 4 dimensiones. (En un hipercubo de n dimensiones, un par de vértices son opuestos si el camino más corto entre ellos tiene n aristas). Alternativamente, se puede formar a partir de un gráfico de hipercubo de 5 dimensiones identificando juntos (o contrayendo) cada par de vértices opuestos. .
Otra construcción, que lleva al mismo gráfico, es crear un vértice para cada elemento del campo finito GF(16) y conectar dos vértices por una arista siempre que la diferencia entre los dos elementos del campo correspondientes sea un cubo perfecto . [6]
La gráfica del cubo dividido por la mitad de dimensión 5 (la gráfica de Clebsch de 10 regulares) es el complemento de la gráfica de 5 regulares. También se puede construir a partir de los vértices de un hipercubo de 5 dimensiones, conectando pares de vértices cuya distancia de Hamming sea exactamente dos. Esta construcción es un ejemplo de la construcción de gráficos de Frankl-Rödl . Produce dos subconjuntos de 16 vértices que están desconectados entre sí; Ambos semicuadrados del hipercubo son isomorfos al gráfico de Clebsch de 10 regulares. Se pueden producir dos copias del gráfico de Clebsch de 5 regulares de la misma manera a partir de un hipercubo de 5 dimensiones, conectando pares de vértices cuya distancia de Hamming sea exactamente cuatro.
La gráfica de Clebsch de 5 regulares es una gráfica fuertemente regular de grado 5 con parámetros . [7] [8] Su complemento, el gráfico de Clebsch de 10 regulares, es por lo tanto también un gráfico fuertemente regular, [1] [4] con parámetros .
El gráfico de Clebsch de 5 regulares es hamiltoniano , no plano y no euleriano . También está conectado por 5 vértices y por 5 aristas . El subgrafo inducido por los diez no vecinos de cualquier vértice en este gráfico forma una copia isomórfica del gráfico de Petersen .
Tiene un grosor de libro 4 y una cola número 3. [9]
Los bordes del gráfico completo K 16 se pueden dividir en tres copias separadas del gráfico de Clebsch de 5 regulares. Debido a que el gráfico de Clebsch es un gráfico sin triángulos , esto muestra que hay una coloración tricolor sin triángulos de los bordes de K 16 ; es decir, que el número de Ramsey R (3,3,3) que describe el número mínimo de vértices en un gráfico completo sin tres colores sin triángulos es al menos 17. Greenwood y Gleason (1955) utilizaron esta construcción como parte de su prueba de que R (3,3,3) = 17. [5] [10]
El gráfico de Clebsch de 5 regulares se puede colorear con cuatro colores, pero no con tres: su conjunto independiente más grande tiene cinco vértices, lo que no es suficiente para dividir el gráfico en tres clases de colores independientes. Contiene como subgrafo inducido el gráfico de Grötzsch , el gráfico de cuatro cromáticos sin triángulos más pequeño , y cada subgrafo inducido de cuatro cromáticos del gráfico de Clebsch es un supergrafo del gráfico de Grötzsch. Más claramente, cada gráfico cuatrocromático sin triángulos sin camino inducido de longitud seis o más es un subgrafo inducido del gráfico de Clebsch y un supergrafo inducido del gráfico de Grötzsch. [11]
El gráfico de Clebsch de 5 regulares es el gráfico de Keller de dimensión dos, parte de una familia de gráficos utilizados para encontrar mosaicos de espacios euclidianos de alta dimensión mediante hipercubos de los cuales no hay dos que se encuentren cara a cara.
El gráfico de Clebsch de 5 regulares se puede incrustar como un mapa regular en la variedad orientable del género 5, formando caras pentagonales; y en la superficie no orientable del género 6, formando caras tetragonales.
El polinomio característico del gráfico de Clebsch de 5 regulares es . Debido a que este polinomio se puede factorizar completamente en términos lineales con coeficientes enteros, el gráfico de Clebsch es un gráfico integral : su espectro se compone enteramente de números enteros. [4] El gráfico de Clebsch es el único gráfico con este polinomio característico, lo que lo convierte en un gráfico determinado por su espectro.
El gráfico de Clebsch de 5 regulares es un gráfico de Cayley con un grupo de automorfismo de orden 1920, isomorfo al grupo de Coxeter . Como gráfico de Cayley, su grupo de automorfismo actúa transitivamente sobre sus vértices, lo que lo convierte en un vértice transitivo . De hecho, es transitivo de arco , por lo tanto transitivo de arista y transitivo de distancia . También es conexo-homogéneo , lo que significa que cada isomorfismo entre dos subgrafos inducidos conectados se puede extender a un automorfismo de todo el grafo.
