En el campo matemático de la teoría de grafos , el grafo de Schläfli , que lleva el nombre de Ludwig Schläfli , es un grafo no dirigido regular de 16 con 27 vértices y 216 aristas. Es un gráfico muy regular con parámetros srg (27, 16, 10, 8).
Gráfico de Schläfli | |
---|---|
Vértices | 27 |
Bordes | 216 |
Radio | 2 |
Diámetro | 2 |
Circunferencia | 3 |
Automorfismos | 51840 |
Número cromático | 9 |
Propiedades | Hamiltoniano sin garras muy regular |
Tabla de gráficos y parámetros |
Construcción
El gráfico de intersección de las 27 líneas en una superficie cúbica es un gráfico localmente lineal que es el complemento del gráfico de Schläfli. Es decir, dos vértices son adyacentes en el gráfico de Schläfli si y solo si el par de líneas correspondiente está sesgado . [1]
El gráfico de Schläfli también se puede construir a partir del sistema de vectores de ocho dimensiones
- (1, 0, 0, 0, 0, 0, 1, 0),
- (1, 0, 0, 0, 0, 0, 0, 1) y
- (−1/2, −1/2, 1/2, 1/2, 1/2, 1/2, 1/2, 1/2),
y los otros 24 vectores obtenidos permutando las primeras seis coordenadas de estos tres vectores. Estos 27 vectores corresponden a los vértices del gráfico de Schläfli; dos vértices son adyacentes si y solo si los dos vectores correspondientes tienen 1 como su producto interno . [2]
Alternativamente, este gráfico puede verse como el complemento del gráfico de colinealidad del cuadrángulo generalizado GQ (2, 4).
Subgrafos y barrios
La vecindad de cualquier vértice en el gráfico de Schläfli forma un subgráfico de 16 vértices en el que cada vértice tiene 10 vecinos (los números 16 y 10 provienen de los parámetros del gráfico de Schläfli como un gráfico fuertemente regular). Todos estos subgrafos son isomorfos al grafo de complemento del grafo de Clebsch . [1] [3] Dado que el gráfico de Clebsch no tiene triángulos , el gráfico de Schläfli no tiene garras . Desempeña un papel importante en la teoría de la estructura para gráficos sin garras de Chudnovsky y Seymour (2005) .
Dos líneas oblicuas cualesquiera de estas 27 pertenecen a una configuración única de seis dobles de Schläfli , un conjunto de 12 líneas cuyo gráfico de intersección es un gráfico de corona en el que las dos líneas tienen vecindades disjuntas. En consecuencia, en el gráfico de Schläfli, cada borde uv pertenece únicamente a un subgráfico en forma de producto cartesiano de gráficos completos K 6 K 2 en tal una manera que u y v pertenecen a diferentes K 6 subgraphs del producto. El gráfico de Schläfli tiene un total de 36 subgráficos de esta forma, uno de los cuales consiste en los vectores cero-uno en la representación de ocho dimensiones descrita anteriormente. [2]
Ultrahomogeneidad
Un grafo se define como k -ultrahomogéneo si cada isomorfismo entre dos de sus subgrafos inducidos de como máximo k vértices puede extenderse a un automorfismo de todo el grafo. Si un gráfico es 5-ultrahomogéneo, es ultrahomogéneo para cada k ; las únicas gráficas conectadas finitas de este tipo son gráficas completas , gráficas de Turán , gráficas de torre de 3 × 3 y el ciclo de 5 . El gráfico de Rado infinito es sumamente homogéneo. Solo hay dos gráficos conectados que son 4-ultrahomogéneos pero no 5-ultrahomogéneos: el gráfico de Schläfli y su complemento. La prueba se basa en la clasificación de grupos simples finitos . [4]
Ver también
- Gráfico de Gosset : contiene el gráfico de Schläfli como un subgráfico inducido de la vecindad de cualquier vértice.
Notas
- ↑ a b Holton y Sheehan (1993) .
- ↑ a b Bussemaker y Neumaier (1992) .
- ^ Cameron y van Lint (1991) . Tenga en cuenta que Cameron y van Lint utilizan una definición alternativa de estos gráficos en la que tanto el gráfico de Schläfli como el gráfico de Clebsch se complementan a partir de sus definiciones aquí.
- ^ Buczak (1980) ; Cameron (1980) ; Devillers (2002) .
Referencias
- Buczak, JMJ (1980), Teoría de grupos finitos , Ph.D. tesis, Universidad de Oxford. Como lo cita Devillers (2002) .
- Bussemaker, FC; Neumaier, A. (1992), "Gráficos excepcionales con el valor propio más pequeño-2 y problemas relacionados", Matemáticas de Computación , 59 (200): 583–608, doi : 10.1090 / S0025-5718-1992-1134718-6.
- Cameron, Peter Jephson (1980), "6 gráficos transitivos", Journal of Combinatorial Theory, Serie B , 28 (2): 168–179, doi : 10.1016 / 0095-8956 (80) 90063-5. Como lo cita Devillers (2002) .
- Cameron, Peter Jephson; van Lint, Jacobus Hendricus (1991), Diseños, gráficos, códigos y sus enlaces , textos estudiantiles de la London Mathematical Society, 22 , Cambridge University Press, p. 35, ISBN 978-0-521-41325-1.
- Chudnovsky, Maria ; Seymour, Paul (2005), "La estructura de los gráficos sin garras", Encuestas en combinatoria 2005 (PDF) , London Math. Soc. Lecture Note Ser., 327 , Cambridge: Cambridge Univ. Press, págs. 153-171, MR 2187738.
- Devillers, Alice (2002), Clasificación de algunas estructuras homogéneas y ultrahomogéneas , Ph.D. tesis, Université Libre de Bruxelles.
- Holton, DA; Sheehan, J. (1993), The Petersen Graph , Cambridge University Press , págs. 270–271.
enlaces externos
- Weisstein, Eric W. "Schläfli Graph" . MathWorld .
- Página de Andries E. Brouwer.