En el campo matemático de la teoría de grafos , el grafo de Schläfli , llamado así por Ludwig Schläfli , es un grafo regular no dirigido de 16 elementos con 27 vértices y 216 aristas. Es un grafo fuertemente regular con parámetros srg(27, 16, 10, 8).
El gráfico de intersección de las 27 líneas de 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 correspondientes son oblicuos . [1]
El gráfico de Schläfli también puede construirse a partir del sistema de vectores de ocho dimensiones.
y los otros 24 vectores obtenidos al permutar las primeras seis coordenadas de estos tres vectores. Estos 27 vectores corresponden a los vértices del grafo 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).
El vecindario de cualquier vértice en el grafo de Schläfli forma un subgrafo 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 grafo de Schläfli como un grafo fuertemente regular). Estos subgrafos son todos isomorfos al grafo complementario del grafo de Clebsch . [1] [3] Dado que el grafo de Clebsch no tiene triángulos , el grafo de Schläfli no tiene garras . Desempeña un papel importante en la teoría de la estructura para grafos sin garras de Chudnovsky y Seymour (2005).
Dos líneas oblicuas cualesquiera de estas 27 pertenecen a una única configuración doble seis 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 vecindarios disjuntos. En consecuencia, en el gráfico de Schläfli, cada arista uv pertenece de manera única a un subgrafo en forma de un producto cartesiano de grafos completos K 6 K 2 de tal manera que u y v pertenecen a diferentes K 6 subgrafos del producto. El gráfico de Schläfli tiene un total de 36 subgrafos de esta forma, uno de los cuales consiste en los vectores cero-uno en la representación de ocho dimensiones descrita anteriormente. [2]
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 grafo es 5-ultrahomogéneo, es ultrahomogéneo para cada k ; los únicos grafos conexos finitos de este tipo son los grafos completos , los grafos de Turán , los grafos de torre 3 × 3 y el 5- ciclo . El grafo infinito de Rado es contablemente ultrahomogéneo. Solo hay dos grafos conexos que son 4-ultrahomogéneos pero no 5-ultrahomogéneos: el grafo de Schläfli y su complemento. La prueba se basa en la clasificación de grupos simples finitos . [4]
