En el campo matemático de la teoría de grafos , el gráfico de Clebsch es uno 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 cúbico dividido por la mitad de dimensión 5 ; Seidel (1968) [2] lo llamó el nombre 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 bordes es el gráfico de cubo plegado de dimensión 5 ; también se conoce como el gráfico de Greenwood-Gleasondespués del trabajo de Robert E. Greenwood y Andrew M. Gleason ( 1955 ), quienes lo usaron para evaluar el número de Ramsey R (3,3,3) = 17. [3] [4] [5]
Gráfico de Clebsch | |
---|---|
![]() | |
Lleva el nombre de | Alfred Clebsch |
Vértices | dieciséis |
Bordes | 40 |
Radio | 2 |
Diámetro | 2 |
Circunferencia | 4 |
Automorfismos | 1920 |
Número cromático | 4 [1] |
Índice cromático | 5 |
Espesor del libro | 4 |
Número de cola | 3 |
Propiedades | Gráfico de Hamiltonian Cayley muy regular Vertex-transitive Edge-transitive Distancia-transitivo . |
Tabla de gráficos y parámetros |
Construcción
El gráfico de cubo plegado de dimensión 5 (el gráfico de Clebsch regular de 5) se puede construir agregando bordes entre pares opuestos de vértices en un gráfico de hipercubo de 4 dimensiones. (En un hipercubo n- dimensional, un par de vértices son opuestos si el camino más corto entre ellos tiene n bordes). Alternativamente, se puede formar a partir de un gráfico de hipercubo de 5 dimensiones identificando juntos (o contrayendo) cada par opuesto de vértices. .
Otra construcción, que conduce 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]
El gráfico de cubo de dimensión 5 dividido por la mitad (el gráfico de Clebsch de 10 regulares) es el complemento del gráfico 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í; ambas de estas medias cuadrados del hipercubo son isomorfos a la gráfica 10-Regular Clebsch. Se pueden producir dos copias del gráfico de Clebsch de cinco dimensiones de la misma manera a partir de un hipercubo de cinco dimensiones, conectando pares de vértices cuya distancia de Hamming sea exactamente cuatro.
Propiedades
El gráfico de Clebsch 5-regular es un gráfico fuertemente regular de grado 5 con parámetros. [7] [8] Su complemento, el gráfico de Clebsch 10-regular, 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 5 por 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 un número de cola 3. [9]
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/5/51/K_16_partitioned_into_three_Clebsch_graphs.svg/160px-K_16_partitioned_into_three_Clebsch_graphs.svg.png)
Los bordes del gráfico completo K 16 se pueden dividir en tres copias separadas del gráfico de Clebsch 5 regular. Debido a que la gráfica de Clebsch es una gráfica sin triángulos , esto muestra que hay tres colores sin triángulos de las aristas 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 puede colorearse 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 un 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 supergráfico del gráfico de Grötzsch. Más claramente, cada gráfico de cuatro cromáticos sin triángulos sin trayectoria inducida de longitud seis o más es un subgráfico inducido del gráfico de Clebsch y un supergráfico 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 teselaciones de espacios euclidianos de alta dimensión mediante hipercubos, ninguno de los cuales se encuentran cara a cara.
El gráfico de Clebsch 5-regular 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.
Propiedades algebraicas
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 consta completamente 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 automorfismos de orden 1920, isomorfo al grupo de Coxeter . Como un gráfico de Cayley, su grupo de automorfismo actúa transitivamente en sus vértices, haciéndolo vértice transitivo . De hecho, es transitivo de arco , por lo tanto, transitivo de borde y transitivo de distancia . También es homogéneo conectado , lo que significa que cada isomorfismo entre dos subgrafos inducidos conectados puede extenderse a un automorfismo de todo el gráfico.
Galería
El gráfico de Clebsch es hamiltoniano .
El número acromático del gráfico de Clebsch es 8.
El número cromático del gráfico de Clebsch es 4.
El índice cromático del gráfico de Clebsch es 5.
Construcción del gráfico de Clebsch a partir de un gráfico de hipercubo .
Referencias
- ^ a b Weisstein, Eric W. "Gráfico de Clebsch" . De MathWorld — Un recurso web de Wolfram . Consultado el 13 de agosto de 2009 .
- ^ JJ Seidel, Gráficos fuertemente regulares con matriz de adyacencia (-1,1,0) que tiene valor propio 3, Lin. Alg. Apl. 1 (1968) 281-298.
- ^ Clebsch, A. (1868), "Ueber die Flächen vierter Ordnung, welche eine Doppelcurve zweiten Grades besitzen", Journal für die reine und angewandte Mathematik , 69 : 142-184.
- ^ a b c El gráfico de Clebsch en la página de inicio de Bill Cherowitzo
- ^ a b Greenwood, RE; Gleason, AM (1955), "Relaciones combinatorias y gráficos cromáticos", Canadian Journal of Mathematics , 7 : 1–7, doi : 10.4153 / CJM-1955-001-4 , MR 0067467.
- ^ De Clerck, Frank (1997). "Construcciones y caracterizaciones de geometrías (semi) parciales" . Escuela de verano de geometrías finitas. pag. 6.
- ^ Godsil, CD (1995). "Problemas en combinatoria algebraica" (PDF) . Revista electrónica de combinatoria . 2 : 3 . Consultado el 13 de agosto de 2009 .
- ^ Peter J. Cameron Gráficos muy regulares en DesignTheory.org, 2001
- ^ Jessica Wolz, Diseños lineales de ingeniería con SAT . Tesis de maestría, Universidad de Tübingen, 2018
- ^ Sun, Hugo S .; Cohen, ME (1984), "Una prueba fácil de la evaluación de Greenwood-Gleason del número de Ramsey R (3,3,3)" (PDF) , The Fibonacci Quarterly , 22 (3): 235-238, MR 0765316.
- ^ Randerath, Bert; Schiermeyer, Ingo; Tewes, Meike (2002), "Tres colores y subgrafos prohibidos. II. Algoritmos polinomiales", Matemáticas discretas , 251 (1-3): 137-153, doi : 10.1016 / S0012-365X (01) 00335-1 , MR 1904597.