Grafo lineal local

Los grafos de amistad , grafos formados al unir un conjunto de triángulos en un único vértice común, son localmente lineales. Son los únicos grafos finitos que poseen la propiedad más fuerte de que cada par de vértices (adyacentes o no) comparte exactamente un vecino común. ^{[ 3 ]} De manera más general, todo grafo de cactus triangular , un grafo formado al unir triángulos en vértices comunes sin formar ciclos adicionales, es localmente lineal. ^{[ 4 ]}

Los grafos lineales locales pueden formarse a partir de grafos lineales locales más pequeños mediante la siguiente operación, una forma de la operación de suma de cliques en grafos. Sea${\displaystyle G}$y${\displaystyle H}$Sean dos grafos localmente lineales cualesquiera, seleccione un triángulo de cada uno de ellos y una los dos grafos fusionando los pares de vértices correspondientes en los dos triángulos seleccionados. Entonces, el grafo resultante permanece localmente lineal. ^{[ 5 ]}

El producto cartesiano de dos grafos localmente lineales cualesquiera sigue siendo localmente lineal, porque cualquier triángulo en el producto proviene de triángulos en uno u otro factor. Por ejemplo, el grafo de Paley de nueve vértices (el grafo del duoprismo 3-3 ) es el producto cartesiano de dos triángulos. ^{[ 1 ]} El grafo de Hamming${\displaystyle H(d,3)}$es un producto cartesiano de${\displaystyle d}$triángulos, y de nuevo es localmente lineal. ^{[ 6 ]}

Algunos grafos que no son localmente lineales pueden usarse como marco para construir grafos localmente lineales más grandes. Una de esas construcciones involucra grafos de líneas . Para cualquier grafo${\displaystyle G}$, el gráfico de líneas${\displaystyle L(G)}$es un grafo que tiene un vértice por cada arista de${\displaystyle G}$Dos vértices en${\displaystyle L(G)}$son adyacentes cuando los dos bordes que representan en${\displaystyle G}$tienen un punto final común. Si${\displaystyle G}$es un gráfico 3-regular sin triángulos , entonces su gráfico de líneas${\displaystyle L(G)}$es 4-regular y localmente lineal. Tiene un triángulo por cada vértice.${\displaystyle v}$de${\displaystyle G}$, con los vértices del triángulo correspondientes a las tres aristas incidentes a${\displaystyle v}$Todo grafo localmente lineal 4-regular puede construirse de esta manera. ^{[ 7 ]} Por ejemplo, el grafo del cuboctaedro es el grafo de líneas de un cubo, por lo que es localmente lineal. El grafo de Paley localmente lineal de nueve vértices, construido anteriormente como un producto cartesiano, también puede construirse de una manera diferente como el grafo de líneas del grafo de utilidad.${\displaystyle K_{3,3}}$El grafo de líneas del grafo de Petersen también es localmente lineal por esta construcción. Tiene una propiedad análoga a la de las jaulas : es el grafo más pequeño posible en el que la camarilla más grande tiene tres vértices, cada vértice está en exactamente dos camarillas disjuntas por aristas, y el ciclo más corto con aristas de camarillas distintas tiene longitud cinco. ^{[ 8 ]}

Un proceso de expansión más complicado se aplica a los grafos planares . Sea${\displaystyle G}$ser un grafo planar incrustado en el plano de tal manera que cada cara sea un cuadrilátero, como el grafo de un cubo. Pegar un antiprisma cuadrado en cada cara de${\displaystyle G}$y luego eliminando los bordes originales de${\displaystyle G}$, produce un nuevo grafo planar localmente lineal. El número de aristas y vértices del resultado se puede calcular a partir de la fórmula poliédrica de Euler : si${\displaystyle G}$tiene${\displaystyle n}$vértices, tiene exactamente${\displaystyle n-2}$caras y el resultado de reemplazar las caras de${\displaystyle G}$por antiprismas tiene${\displaystyle 5(n-2)+2}$vértices y${\displaystyle 12(n-2)}$aristas. ^{[ 5 ]} Por ejemplo, el cuboctaedro puede producirse de esta manera, a partir de las dos caras (la interior y la exterior) de un 4-ciclo. El 4-ciclo eliminado de esta construcción puede verse en el cuboctaedro como un ciclo de cuatro diagonales de sus caras cuadradas, que bisecan el poliedro.

Ciertos grafos de Kneser , grafos construidos a partir de los patrones de intersección de conjuntos de igual tamaño, son localmente lineales. Los grafos de Kneser se describen mediante dos parámetros: el tamaño de los conjuntos que representan y el tamaño del universo del que se extraen estos conjuntos. El grafo de Kneser${\displaystyle KG_{a,b}}$tiene${\displaystyle {\tbinom {a}{b}}}$vértices (en la notación estándar para coeficientes binomiales ), que representan los${\displaystyle b}$subconjuntos de elementos de un${\displaystyle a}$Conjunto de elementos. En este grafo, dos vértices son adyacentes cuando los subconjuntos correspondientes son conjuntos disjuntos , sin elementos en común. En el caso especial cuando${\displaystyle a=3b}$, el gráfico resultante es localmente lineal, porque para cada dos disjuntos${\displaystyle b}$subconjuntos de elementos${\displaystyle X}$y${\displaystyle Y}$Hay exactamente otro${\displaystyle b}$subconjunto de elementos disjunto de ambos, que consta de todos los elementos que no están ni en${\displaystyle X}$ni en${\displaystyle Y}$. El gráfico lineal local resultante tiene${\displaystyle {\tbinom {3b}{b}}}$vértices y${\displaystyle {\tfrac {1}{2}}{\tbinom {3b}{b}}{\tbinom {2b}{b}}}$bordes. Por ejemplo, para${\displaystyle b=2}$El gráfico de Kneser${\displaystyle KG_{6,2}}$es localmente lineal con 15 vértices y 45 aristas. ^{[ 2 ]}

También se pueden construir grafos lineales locales a partir de conjuntos de números sin progresión.${\displaystyle p}$Sea un número primo, y sea${\displaystyle A}$ser un subconjunto de los números módulo${\displaystyle p}$de tal manera que no haya tres miembros de${\displaystyle A}$formar una progresión aritmética módulo${\displaystyle p}$. (Eso es,${\displaystyle A}$es un conjunto Salem-Spencer módulo${\displaystyle p}$.) Este conjunto se puede utilizar para construir un grafo tripartito con${\displaystyle 3p}$vértices y${\displaystyle 3p\cdot |A|}$aristas que son localmente lineales. Para construir este grafo, haga tres conjuntos de vértices, cada uno numerado desde${\displaystyle 0}$a${\displaystyle p-1}$. Para cada número${\displaystyle x}$en el rango de${\displaystyle 0}$a${\displaystyle p-1}$y cada elemento${\displaystyle a}$de${\displaystyle A}$, construir un triángulo que conecte el vértice con el número${\displaystyle x}$ en el primer conjunto de vértices, el vértice con número${\displaystyle x+a}$en el segundo conjunto de vértices, y el vértice con número${\displaystyle x+2a}$en el tercer conjunto de vértices. Forme un grafo como la unión de todos estos triángulos. Debido a que es una unión de triángulos, cada arista del grafo resultante pertenece a un triángulo. Sin embargo, no puede haber otros triángulos que los formados de esta manera. Cualquier otro triángulo tendría vértices numerados${\displaystyle (x,x+a,x+a+b)}$dónde${\displaystyle a}$,${\displaystyle b}$, y${\displaystyle c=(a+b)/2}$todos pertenecen a${\displaystyle A}$violando el supuesto de que no existen progresiones aritméticas${\displaystyle (a,c,b)}$en${\displaystyle A}$. ^{[ 9 ]} Por ejemplo, con${\displaystyle p=3}$y${\displaystyle A=\{\pm 1\}}$El resultado de esta construcción es el grafo de Paley de nueve vértices.

Los triángulos en un grafo localmente lineal pueden considerarse equivalentemente como la formación de un hipergrafo 3-uniforme . Dicho hipergrafo debe ser lineal, lo que significa que ningún par de sus hiperaristas (los triángulos) puede compartir más de un vértice. El grafo localmente lineal en sí es el grafo de Gaifman del hipergrafo, el grafo de pares de vértices que pertenecen a una hiperarista común. Desde esta perspectiva, tiene sentido hablar de la circunferencia del hipergrafo. En términos de grafos, esta es la longitud del ciclo más corto que no es uno de los triángulos del grafo. En este contexto, se ha utilizado una construcción algebraica basada en grafos de polaridad (también llamados grafos de Brown) para encontrar grafos localmente lineales densos que no tienen 4-ciclos; su circunferencia de hipergrafo es cinco. Un grafo de polaridad se define a partir de un plano proyectivo finito y una polaridad , una biyección que preserva la incidencia entre sus puntos y sus líneas. Los vértices del grafo de polaridad son puntos, y una arista conecta dos puntos siempre que uno sea polar a una línea que contenga al otro. De forma más algebraica, los vértices del mismo grafo pueden representarse mediante coordenadas homogéneas : estas son ternas de valores.${\displaystyle (x,y,z)}$de un campo finito , no todo cero, donde dos ternas definen el mismo punto en el plano siempre que sean múltiplos escalares entre sí. Dos puntos, representados por ternas de esta manera, son adyacentes cuando su producto interno es cero. El gráfico de polaridad para un campo finito de orden impar${\displaystyle q}$tiene${\displaystyle q^{2}+q+1}$vértices, de los cuales${\displaystyle q+1}$son autoadyacentes y no pertenecen a ningún triángulo. Cuando se eliminan, el resultado es un gráfico localmente lineal con${\displaystyle q^{2}}$vértices,${\displaystyle {\bigl (}{\tfrac {1}{2}}+o(1){\bigr )}q^{3}}$bordes, y circunferencia del hipergrafo cinco, dando el número máximo posible de aristas para un grafo localmente lineal de esta circunferencia hasta términos de orden inferior. ^{[ 10 ]}

Un grafo es regular cuando todos sus vértices tienen el mismo grado , es decir, el número de aristas incidentes. Todo grafo localmente lineal debe tener grado par en cada vértice, ya que las aristas en cada vértice pueden agruparse formando triángulos. El producto cartesiano de dos grafos regulares localmente lineales también es localmente lineal y regular, con un grado igual a la suma de los grados de los factores. Por lo tanto, se pueden tomar productos cartesianos de grafos localmente lineales de grado dos (triángulos) para obtener grafos regulares localmente lineales de cualquier grado par. ^{[ 1 ]}

El${\displaystyle 2r}$-Los grafos lineales locales regulares deben tener al menos${\displaystyle 6r-3}$vértices, porque hay esta cantidad de vértices entre cualquier triángulo y sus vecinos solamente. (Dos vértices del triángulo no pueden compartir un vecino sin violar la linealidad local). Los grafos regulares con exactamente esta cantidad de vértices son posibles solo cuando${\displaystyle r}$es 1, 2, 3 o 5, y están definidos de forma única para cada uno de estos cuatro casos. Los cuatro grafos regulares que cumplen este límite en el número de vértices son el triángulo 2-regular de 3 vértices.${\displaystyle K_{3}}$, el grafo de Paley 4-regular de 9 vértices, el grafo de Kneser 6-regular de 15 vértices${\displaystyle KG_{6,2}}$y el grafo complemento 10-regular de 27 vértices del grafo de Schläfli . El último grafo 10-regular de 27 vértices también representa el grafo de intersección de las 27 líneas en una superficie cúbica . ^{[ 2 ]}

Un grafo fuertemente regular puede caracterizarse por una cuádrupla de parámetros.${\displaystyle (n,k,\lambda,\mu)}$dónde${\displaystyle n}$es el número de vértices,${\displaystyle k}$es el número de aristas incidentes por vértice,${\displaystyle \lambda }$es el número de vecinos compartidos para cada par de vértices adyacentes, y${\displaystyle \mu }$es el número de vecinos compartidos para cada par de vértices no adyacentes. Cuando${\displaystyle \lambda =1}$El gráfico es localmente lineal. Los gráficos localmente lineales ya mencionados anteriormente que son gráficos fuertemente regulares y sus parámetros son ^{[ 11 ].}

• el triángulo (3,2,1,0),
• el grafo de Paley de nueve vértices (9,4,1,2),
• El gráfico de Kneser${\displaystyle KG_{6,2}}$(15,6,1,3) y
• el complemento del grafo de Schläfli (27,10,1,5).

Otros grafos localmente lineales fuertemente regulares incluyen:

• el gráfico de Brouwer-Haemers (81,20,1,6), ^{[ 12 ]}
• el gráfico de Berlekamp-van Lint-Seidel (243,22,1,2), ^{[ 13 ]}
• el gráfico Cossidente–Penttila (378,52,1,8), ^{[ 14 ]} y
• el gráfico de los Juegos (729,112,1,20). ^{[ 15 ]}

Otras combinaciones potencialmente válidas con${\displaystyle \lambda =1}$Se incluyen (99,14,1,2) y (115,18,1,3), pero se desconoce si existen grafos fuertemente regulares con esos parámetros. ^{[ 11 ]} La cuestión de la existencia de un grafo fuertemente regular con parámetros (99,14,1,2) se conoce como el problema del grafo 99 de Conway , y John Horton Conway ha ofrecido un premio de 1000 dólares por su solución. ^{[ 16 ]}

Hay un número finito de grafos regulares en distancia de grado 4 o 6 que son localmente lineales. Además de los grafos fuertemente regulares de los mismos grados, también incluyen el grafo de líneas del grafo de Petersen y el grafo de Hamming.${\displaystyle H(3,3)}$y el gráfico de Foster dividido por la mitad . ^{[ 17 ]}