Gráfico lineal local

Gráfico donde cada arista está en un triángulo

El gráfico de Paley de nueve vértices es localmente lineal. Uno de sus seis triángulos está resaltado en verde.

En teoría de grafos , un grafo localmente lineal es un grafo no dirigido en el que cada arista pertenece exactamente a un triángulo. Equivalentemente, para cada vértice del grafo, sus vecinos son cada uno adyacente a exactamente otro vecino, por lo que los vecinos pueden emparejarse en un emparejamiento inducido . ^[1] Los grafos localmente lineales también se han llamado grafos emparejados localmente. ^[2] Sus triángulos forman las hiperaristas de hipergrafos lineales 3-uniformes sin triángulos y los bloques de ciertos sistemas triples de Steiner parciales , y los grafos localmente lineales son exactamente los grafos de Gaifman de estos hipergrafos o sistemas parciales de Steiner.

Se conocen muchas construcciones para grafos localmente lineales. Algunos ejemplos de grafos localmente lineales son los grafos de cactus triangulares , los grafos lineales de grafos libres de triángulos 3-regulares y los productos cartesianos de grafos localmente lineales más pequeños. Ciertos grafos de Kneser y ciertos grafos fuertemente regulares también son localmente lineales.

La cuestión de cuántas aristas pueden tener los grafos localmente lineales es una de las formulaciones del problema de Ruzsa-Szemerédi . Aunque los grafos densos pueden tener una cantidad de aristas proporcional al cuadrado del número de vértices, los grafos localmente lineales tienen una cantidad menor de aristas, que se queda corta al cuadrado al menos por un pequeño factor no constante. También se conocen los grafos planos más densos que pueden ser localmente lineales. Los grafos localmente lineales menos densos son los grafos triangulares de cactus.

Construcciones

Pegado y productos

Gráficos de amistad

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

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

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

Desde gráficos más pequeños

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

El cuboctaedro , un gráfico lineal local plano que se puede formar como el gráfico lineal de un cubo o pegando antiprismas en las caras internas y externas de un cubo de 4 ciclos.

Un proceso de expansión más complicado se aplica a los grafos planares . Sea un grafo planar incrustado en el plano de tal manera que cada cara es un cuadrilátero, como el grafo de un cubo. Pegar un antiprisma cuadrado en cada cara de , y luego eliminar las aristas originales de , produce un nuevo grafo planar localmente lineal. Los números de aristas y vértices del resultado se pueden calcular a partir de la fórmula poliédrica de Euler : si tiene vértices, tiene exactamente caras, y el resultado de reemplazar las caras de por antiprismas tiene vértices y aristas. ^[5] Por ejemplo, el cuboctaedro se puede producir nuevamente 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 se puede ver en el cuboctaedro como un ciclo de cuatro diagonales de sus caras cuadradas, que dividen en dos el poliedro. ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle G}$ ${\displaystyle n}$ ${\displaystyle n-2}$ ${\displaystyle G}$ ${\displaystyle 5(n-2)+2}$ ${\displaystyle 12(n-2)}$

Construcciones algebraicas

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 tiene vértices (en la notación estándar para coeficientes binomiales ), que representan los subconjuntos de elementos de un conjunto de elementos. En este grafo, dos vértices son adyacentes cuando los subconjuntos correspondientes son conjuntos disjuntos , que no tienen elementos en común. En el caso especial cuando , el grafo resultante es localmente lineal, porque para cada dos subconjuntos de elementos disjuntos y hay exactamente otro subconjunto de elementos disjunto de ambos, que consiste en todos los elementos que no están ni en ni en . El grafo localmente lineal resultante tiene vértices y aristas. Por ejemplo, para el grafo de Kneser es localmente lineal con 15 vértices y 45 aristas. ^[2] ${\displaystyle KG_{a,b}}$ ${\displaystyle {\tbinom {a}{b}}}$ ${\displaystyle b}$ ${\displaystyle a}$ ${\displaystyle a=3b}$ ${\displaystyle b}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle b}$ ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle {\tbinom {3b}{b}}}$ ${\displaystyle {\tfrac {1}{2}}{\tbinom {3b}{b}}{\tbinom {2b}{b}}}$ ${\displaystyle b=2}$ ${\displaystyle KG_{6,2}}$

Los grafos localmente lineales también pueden construirse a partir de conjuntos de números sin progresión. Sea un número primo, y sea un subconjunto de los números módulo tal que ningún miembro de forme una progresión aritmética módulo . (Es decir, es un conjunto de Salem-Spencer módulo .) Este conjunto puede usarse para construir un grafo tripartito con vértices y aristas que sea localmente lineal. Para construir este grafo, haz tres conjuntos de vértices, cada uno numerado de a . Para cada número en el rango de a y cada elemento de , construye un triángulo que conecte el vértice con número en el primer conjunto de vértices, el vértice con número en el segundo conjunto de vértices y el vértice con número en el tercer conjunto de vértices. Forma 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 donde , , y todos pertenecen a , violando el supuesto de que no hay progresiones aritméticas en . ^[9] Por ejemplo, con y , el resultado de esta construcción es el gráfico de Paley de nueve vértices. ${\displaystyle p}$ ${\displaystyle A}$ ${\displaystyle p}$ ${\displaystyle A}$ ${\displaystyle p}$ ${\displaystyle A}$ ${\displaystyle p}$ ${\displaystyle 3p}$ ${\displaystyle 3p\cdot |A|}$ ${\displaystyle 0}$ ${\displaystyle p-1}$ ${\displaystyle x}$ ${\displaystyle 0}$ ${\displaystyle p-1}$ ${\displaystyle a}$ ${\displaystyle A}$ ${\displaystyle x}$ ${\displaystyle x+a}$ ${\displaystyle x+2a}$ ${\displaystyle (x,x+a,x+a+b)}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle c=(a+b)/2}$ ${\displaystyle A}$ ${\displaystyle (a,c,b)}$ ${\displaystyle A}$ ${\displaystyle p=3}$ ${\displaystyle A=\{\pm 1\}}$

Los triángulos en un grafo localmente lineal pueden considerarse equivalentemente como formando un hipergrafo 3-uniforme . Tal hipergrafo debe ser lineal, lo que significa que ninguna 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. En esta visión 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. Se ha utilizado una construcción algebraica basada en grafos de polaridad (también llamados grafos de Brown), en este contexto, 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. Más algebraicamente, los vértices del mismo grafo pueden representarse por coordenadas homogéneas : estas son triples de valores de un cuerpo finito , no todos cero, donde dos triples definen el mismo punto en el plano siempre que sean múltiplos escalares uno del otro. Dos puntos, representados por triples de esta manera, son adyacentes cuando su producto interno es cero. El grafo de polaridad para un cuerpo finito de orden impar tiene vértices, de los cuales son autoadyacentes y no pertenecen a ningún triángulo. Cuando se eliminan, el resultado es un grafo localmente lineal con vértices, aristas y circunferencia hipergráfica cinco, lo que da el número máximo posible de aristas para un grafo localmente lineal de esta circunferencia hasta términos de orden inferior. ^[10] ${\displaystyle (x,y,z)}$ ${\displaystyle q}$ ${\displaystyle q^{2}+q+1}$ ${\displaystyle q+1}$ ${\displaystyle q^{2}}$ ${\displaystyle {\bigl (}{\tfrac {1}{2}}+o(1){\bigr )}q^{3}}$

Regularidad

Grafos regulares con pocos vértices

Un grafo es regular cuando todos sus vértices tienen el mismo grado , el número de aristas incidentes. Todo grafo localmente lineal debe tener un grado par en cada vértice, porque las aristas en cada vértice pueden emparejarse para formar triángulos. El producto cartesiano de dos grafos locales lineales regulares es nuevamente 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 producir grafos localmente lineales regulares de cada grado par. ^[1]

Los grafos localmente lineales -regulares deben tener al menos vértices, porque hay esta cantidad de vértices entre cualquier triángulo y sus vecinos solamente. (No hay dos vértices del triángulo que puedan compartir un vecino sin violar la linealidad local.) Los grafos regulares con exactamente esta cantidad de vértices son posibles solo cuando 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 , el grafo de Paley de 9 vértices 4-regular de , el grafo de Kneser de 15 vértices 6-regular de , y el grafo de complemento 10-regular de 27 vértices del grafo de Schläfli . El grafo final 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] ${\displaystyle 2r}$ ${\displaystyle 6r-3}$ ${\displaystyle r}$ ${\displaystyle K_{3}}$ ${\displaystyle KG_{6,2}}$

Gráficos fuertemente regulares

Un grafo fuertemente regular se puede caracterizar por un cuádruple de parámetros donde es el número de vértices, es el número de aristas incidentes por vértice, es el número de vecinos compartidos para cada par de vértices adyacentes, y es el número de vecinos compartidos para cada par de vértices no adyacentes. Cuando el grafo es localmente lineal. Los grafos localmente lineales ya mencionados anteriormente que son grafos fuertemente regulares y sus parámetros son ^[11] ${\displaystyle (n,k,\lambda ,\mu )}$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle \lambda }$ ${\displaystyle \mu }$ ${\displaystyle \lambda =1}$

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

Otros gráficos localmente lineales y 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 grafo de Cossidente-Penttila (378,52,1,8), ^[14] y
• El gráfico de los Juegos (729,112,1,20). ^[15]

Otras combinaciones potencialmente válidas 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 de los 99 grafos de Conway , y John Horton Conway ha ofrecido un premio de $1000 por su solución. ^[16] ${\displaystyle \lambda =1}$

Gráficas de distancia-regulares

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

Densidad

Los gráficos planos localmente lineales más densos posibles se forman pegando un antiprisma (vértices rojos y bordes negros) en cada cara cuadrilátera de un gráfico plano (vértices azules y bordes amarillos discontinuos).

Una formulación del problema de Ruzsa–Szemerédi pide el número máximo de aristas en un grafo localmente lineal con vértice. Como demostraron Imre Z. Ruzsa y Endre Szemerédi , este número máximo es pero es para cada . La construcción de grafos localmente lineales a partir de conjuntos sin progresión conduce a los grafos localmente lineales más densos conocidos, con aristas. (En estas fórmulas, , y son ejemplos de notación o minúscula , notación Omega grande y notación O grande , respectivamente.) ^[9] ${\displaystyle n}$ ${\displaystyle o(n^{2})}$ ${\displaystyle \Omega (n^{2-\varepsilon })}$ ${\displaystyle \varepsilon >0}$ ${\displaystyle n^{2}/\exp O({\sqrt {\log n}})}$ ${\displaystyle o}$ ${\displaystyle \Omega }$ ${\displaystyle O}$

Entre los grafos planos , el número máximo de aristas en un grafo localmente lineal con vértices es . El grafo del cuboctaedro es el primero de una secuencia infinita de grafos poliédricos con vértices y aristas, para , construidos expandiendo las caras cuadriláteras de en antiprismas. Estos ejemplos muestran que se puede alcanzar el límite superior. ^[5] ${\displaystyle n}$ ${\displaystyle {\tfrac {12}{5}}(n-2)}$ ${\displaystyle n=5k+2}$ ${\displaystyle {\tfrac {12}{5}}(n-2)=12k}$ ${\displaystyle k=2,3,\dots }$ ${\displaystyle K_{2,k}}$ ${\displaystyle {\tfrac {12}{5}}(n-2)}$

Todo grafo localmente lineal tiene la propiedad de permanecer conectado después de que se le quite cualquier coincidencia, porque en cualquier camino a través del grafo, cada arista coincidente puede ser reemplazada por las otras dos aristas de su triángulo. Entre los grafos con esta propiedad, los menos densos son los grafos triangulares de cactus, que también son los grafos localmente lineales menos densos. ^[4]

Aplicaciones

Una aplicación de los grafos localmente lineales se da en la formulación de los diagramas de Greechie, que se utilizan en lógica cuántica para ayudar a determinar si ciertas ecuaciones del espacio de Hilbert pueden inferirse unas de otras. En esta aplicación, los triángulos de los grafos localmente lineales forman los bloques de los diagramas de Greechie con un tamaño de bloque de tres. Los diagramas de Greechie correspondientes a las redes provienen de los grafos localmente lineales de circunferencia hipergráfica cinco o más, ^[18] tal como se construyen, por ejemplo, a partir de grafos de polaridad. ^[10]

Se puede utilizar una combinación de muestreo aleatorio y un lema de eliminación de grafos para encontrar hipergrafos 3-uniformes de gran tamaño y circunferencia dentro de hipergrafos lineales 3-uniformes arbitrarios o sistemas triples de Steiner parciales. Este método se puede utilizar luego para demostrar límites inferiores asintóticamente ajustados en el número de independencia de hipergrafos lineales 3-uniformes y sistemas triples de Steiner parciales. ^[19]

Referencias

1. Fronček, Dalibor (1989), "Gráficos localmente lineales", Mathematica Slovaca , 39 (1): 3–6, hdl : 10338.dmlcz/136481 , MR  1016323
2. Larrión, F.; Pizaña, MA; Villarroel-Flores, R. (2011), "Pequeños gráficos nK2 localmente" (PDF) , Ars Combinatoria , 102 : 385–391, SEÑOR  2867738
3. Erdős, Paul ; Rényi, Alfred ; Sós, Vera T. (1966), "Sobre un problema de teoría de grafos" (PDF) , Studia Sci. Matemáticas. Hungría. , 1 : 215–235
4. Farley, Arthur M.; Proskurowski, Andrzej (1982), "Redes inmunes a fallos de línea aislados", Networks , 12 (4): 393–403, doi :10.1002/net.3230120404, MR  0686540; ver en particular la pág. 397: "Llamamos a la red resultante un cactus triangular; es una red de cactus en la que cada línea pertenece exactamente a un triángulo".
5. Zelinka, Bohdan (1988), "Gráficos lineales locales politópicos", Mathematica Slovaca , 38 (2): 99–103, hdl : 10338.dmlcz/133017 , MR  0945363
6. Devillers, Alice; Jin, Wei; Li, Cai Heng; Praeger, Cheryl E. (2013), "Transitividad local 2-geodésica y gráficos de camarilla", Journal of Combinatorial Theory , Serie A, 120 (2): 500–508, doi : 10.1016/j.jcta.2012.10.004 , MR  2995054En la notación de esta referencia, la familia de gráficos -regulares se denota como . ${\displaystyle 2r}$ ${\displaystyle F(r,2)}$
7. Munaro, Andrea (2017), "Gráficos en línea de grafos libres de triángulos subcúbicos", Discrete Mathematics , 340 (6): 1210–1226, doi : 10.1016/j.disc.2017.01.006 , MR  3624607
8. Fan, Cong (1996), "Sobre jaulas generalizadas", Journal of Graph Theory , 23 (1): 21–31, doi :10.1002/(SICI)1097-0118(199609)23:1<21::AID-JGT2>3.0.CO;2-M, MR  1402135
9. Ruzsa, IZ ; Szemerédi, E. (1978), "Sistemas triples sin seis puntos que lleven tres triángulos", Combinatoria (Proc. Quinto coloquio húngaro, Keszthely, 1976), vol. II , coloq. Matemáticas. Soc. János Bolyai, vol. 18, Amsterdam y Nueva York: Holanda Septentrional, págs. 939–945, MR  0519318
10. Lazebnik, Felix; Verstraëte, Jacques (2003), "Sobre hipergrafos de circunferencia cinco", Electronic Journal of Combinatorics , 10 : R25:1–R25:15, doi : 10.37236/1718 , MR  2014512
11. Makhnëv, AA (1988), "Gráficos fuertemente regulares con ", Akademiya Nauk SSSR , 44 (5): 667–672, 702, doi :10.1007/BF01158426, MR  0980587, S2CID  120911900 ${\displaystyle \lambda =1}$
12. Brouwer, AE ; Haemers, WH (1992), "Estructura y unicidad del gráfico fuertemente regular (81,20,1,6)", Una colección de contribuciones en honor a Jack van Lint, Discrete Mathematics , 106/107: 77–82, doi :10.1016/0012-365X(92)90532-K, MR  1181899
13. Berlekamp, ​​ER ; van Lint, JH ; Seidel, JJ (1973), "Un gráfico fuertemente regular derivado del código ternario perfecto de Golay", A Survey of Combinatorial Theory (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colo., 1971) , Ámsterdam: North-Holland: 25–30, doi :10.1016/B978-0-7204-2262-7.50008-9, ISBN 9780720422627, Sr.  0364015
14. Cossidente, Antonio; Penttila, Tim (2005), "Hemisistemas en la superficie hermítica", Journal of the London Mathematical Society , Segunda serie, 72 (3): 731–741, doi :10.1112/S0024610705006964, MR  2190334
15. Bondarenko, Andriy V.; Radchenko, Danylo V. (2013), "Sobre una familia de grafos fuertemente regulares con ", Journal of Combinatorial Theory , Serie B, 103 (4): 521–531, arXiv : 1201.0383 , doi :10.1016/j.jctb.2013.05.005, MR  3071380 ${\displaystyle \lambda =1}$
16. Zehavi, Sa'ar; Oliveira, Ivo Fagundes David (2017), No es el problema de 99 gráficos de Conway , arXiv : 1707.08047
17. Hiraki, Akira; Nomura, Kazumasa; Suzuki, Hiroshi (2000), "Gráficos regulares a distancia de valencia 6 y ", Journal of Algebraic Combinatorics , 11 (2): 101–134, doi : 10.1023/A:1008776031839 , MR  1761910 ${\displaystyle a_{1}=1}$
18. McKay, Brendan D .; Megill, Norman D.; Pavičić, Mladen (2000), "Algoritmos para diagramas de Greechie", Revista internacional de física teórica , 39 (10): 2381–2406, arXiv : quant-ph/0009039 , doi :10.1023/A:1026476701774, MR  1803695
19. Henning, Michael A.; Yeo, Anders (2020), "Capítulo 12: Sistemas triples parciales de Steiner", Transversales en hipergrafos lineales uniformes , Developments in Mathematics, vol. 63, Cham: Springer, págs. 171–177, doi :10.1007/978-3-030-46559-9_12, ISBN 978-3-030-46559-9, Sr.  4180641