Gráfico localmente lineal

Grafica 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 gráfico localmente lineal es un gráfico no dirigido en el que cada arista pertenece exactamente a un triángulo. De manera equivalente, para cada vértice del gráfico, sus vecinos son adyacentes exactamente a otro vecino, por lo que los vecinos se pueden emparejar en una coincidencia inducida . ^[1] Los gráficos localmente lineales también se denominan gráficos coincidentes localmente. ^[2] Sus triángulos forman los hiperbordes de hipergrafos lineales de 3 uniformes sin triángulos y los bloques de ciertos sistemas triples parciales de Steiner , y los gráficos localmente lineales son exactamente los gráficos de Gaifman de estos hipergrafos o sistemas parciales de Steiner.

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

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

Construcciones

Pegado y productos

Gráficos de amistad

Las gráficas de amistad , gráficas formadas pegando una colección de triángulos en un único vértice compartido, son localmente lineales. Son los únicos gráficos 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, cada gráfico de cactus triangular , un gráfico formado pegando triángulos en vértices compartidos sin formar ciclos adicionales, es localmente lineal. ^[4]

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

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

De gráficos más pequeños

Algunos gráficos que no son localmente lineales se pueden utilizar como marco para construir gráficos localmente lineales más grandes. Una de esas construcciones implica gráficos lineales . Para cualquier gráfico , el gráfico lineal es un gráfico que tiene un vértice para cada arista de . Dos vértices son adyacentes cuando las dos aristas que representan tienen un punto final común. Si es un gráfico sin triángulos de 3 regulares , entonces su gráfico 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 los tres bordes incidentes a . Cada gráfico localmente lineal de 4 regulares se puede construir de esta manera. ^[7] Por ejemplo, la gráfica del cuboctaedro es la gráfica lineal de un cubo, por lo que es localmente lineal. El gráfico de Paley localmente lineal de nueve vértices, construido anteriormente como un producto cartesiano, también se puede construir de una manera diferente a la gráfica lineal del gráfico de utilidad . La gráfica lineal de la gráfica de Petersen también es localmente lineal según esta construcción. Tiene una propiedad análoga a las jaulas : es el gráfico 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 bordes disjuntos 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 plano localmente lineal que se puede formar como el gráfico lineal de un cubo o pegando antiprismas en las caras interior y exterior de un cubo de 4 ciclos.

Se aplica un proceso de expansión más complicado a los gráficos planos . Sea una gráfica plana incrustada en el plano de tal manera que cada cara sea un cuadrilátero, como la gráfica de un cubo. Pegar un antiprisma cuadrado en cada cara de y luego eliminar los bordes originales de produce un nuevo gráfico plano 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 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 ciclos. 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 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 gráficos de Kneser , gráficos construidos a partir de patrones de intersección de conjuntos de igual tamaño, son localmente lineales. Los gráficos 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 gráfico 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 gráfico, dos vértices son adyacentes cuando los subconjuntos correspondientes son conjuntos disjuntos y no tienen elementos en común. En el caso especial cuando , el gráfico resultante es localmente lineal, porque para cada dos subconjuntos de elementos disjuntos hay exactamente otro subconjunto de elementos disjuntos de ambos, que consta de todos los elementos que no están ni en ni en . El gráfico localmente lineal resultante tiene vértices y aristas. Por ejemplo, el gráfico 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}}$

También se pueden construir gráficos localmente lineales 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 no haya tres miembros que formen un módulo de progresión aritmética . (Es decir, es un módulo de conjunto de Salem-Spencer ). Este conjunto se puede utilizar para construir un gráfico tripartito con vértices y aristas que sea localmente lineal. Para construir este gráfico, haz tres conjuntos de vértices, cada uno numerado del hasta . Para cada número en el rango de a y cada elemento de , construya 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 una gráfica como la unión de todos estos triángulos. Debido a que es una unión de triángulos, cada arista del gráfico resultante pertenece a un triángulo. Sin embargo, no pueden existir otros triángulos que los formados de esta manera. Cualquier otro triángulo tendría los vértices numerados a los que pertenecen , y todos , violando la suposición 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\}}$

Se puede pensar de manera equivalente que los triángulos en un gráfico localmente lineal forman un hipergráfico de 3 uniformes . Un hipergrafo de este tipo debe ser lineal, lo que significa que dos de sus hipergrafos (los triángulos) no pueden compartir más de un vértice. El gráfico localmente lineal en sí es el gráfico de Gaifman del hipergrafo, el gráfico de pares de vértices que pertenecen a un hipergrafo común. Desde este punto de vista, tiene sentido hablar de la circunferencia del hipergrafo. En términos gráficos, esta es la duración del ciclo más corto que no es uno de los triángulos del gráfico. En este contexto, se ha utilizado una construcción algebraica basada en gráficos de polaridad (también llamados gráficos de Brown) para encontrar gráficos localmente lineales densos que no tienen 4 ciclos; su circunferencia hipergráfica es cinco. Un gráfico 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 rectas. Los vértices del gráfico de polaridad son puntos y una arista conecta dos puntos siempre que uno sea polar con una línea que contiene al otro. De manera más algebraica, los vértices de un mismo gráfico se pueden representar mediante coordenadas homogéneas : se trata de ternas de valores de un campo finito , no todos cero, donde dos ternas definen el mismo punto en el plano siempre que sean múltiplos escalares entre sí. Dos puntos, representados de esta manera por ternas, son adyacentes cuando su producto interno es cero. El gráfico de polaridad para un campo 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 gráfico localmente lineal con vértices, aristas y una circunferencia del hipergráfico cinco, lo que proporciona el número máximo posible de aristas para un gráfico 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

Gráficos 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 gráfico localmente lineal debe tener grados pares en cada vértice, porque los bordes de cada vértice se pueden emparejar formando triángulos. El producto cartesiano de dos gráficos regulares localmente lineales 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 gráficas localmente lineales de grado dos (triángulos) para producir gráficas localmente lineales regulares de cada grado par. ^[1]

Los gráficos locales lineales regulares deben tener al menos vértices, porque hay tantos vértices entre cualquier triángulo y solo sus vecinos. (No hay dos vértices del triángulo que puedan compartir un vecino sin violar la linealidad local). Los gráficos regulares con exactamente esta cantidad de vértices sólo son posibles cuando es 1, 2, 3 o 5, y están definidos de forma única para cada uno de estos cuatro casos. Los cuatro gráficos regulares que cumplen con este límite en el número de vértices son el triángulo de 3 vértices y 2 regulares , el gráfico de Paley de 9 vértices y 4 regulares, el gráfico de Kneser de 15 vértices y 6 regulares y el gráfico de Kneser de 27 vértices y 10 regulares. Gráfico complementario del gráfico de Schläfli . El gráfico final de 27 vértices y 10 regulares también representa el gráfico 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 gráfico 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 la gráfica es localmente lineal. Los gráficos localmente lineales ya mencionados anteriormente que son gráficos 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 triángulo (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 gráfico de Schläfli (27,10,1,5).

Otros gráficos 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 de Cossidente-Penttila (378,52,1,8), ^[14] y
• el gráfico de 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 gráficos fuertemente regulares con esos parámetros. ^[11] La cuestión de la existencia de un gráfico fuertemente regular con parámetros (99,14,1,2) se conoce como problema de los 99 gráficos de Conway , y John Horton Conway ha ofrecido un premio de 1000 dólares por su solución. ^[dieciséis] ${\displaystyle \lambda =1}$

Gráficos de distancia regular

Hay un número finito de gráficas regulares de distancia de grado 4 o 6 que son localmente lineales. Más allá de los gráficos fuertemente regulares de los mismos grados, también incluyen el gráfico lineal del gráfico de Petersen, el gráfico de Hamming y el gráfico de Foster reducido a 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 discontinuos amarillos).

Una formulación del problema de Ruzsa-Szemerédi solicita el número máximo de aristas en un gráfico localmente lineal de vértices. Como demostraron Imre Z. Ruzsa y Endre Szemerédi , este número máximo es pero es para cada . La construcción de gráficos localmente lineales a partir de conjuntos libres de progresión conduce a los gráficos localmente lineales más densos conocidos, con aristas. (En estas fórmulas, , y son ejemplos de notación o pequeña , 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 gráficos planos , el número máximo de aristas en un gráfico localmente lineal con vértices es . La gráfica del cuboctaedro es la primera de una secuencia infinita de gráficas poliédricas con vértices y aristas, para , construida 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 gráfico localmente lineal tiene la propiedad de permanecer conectado después de eliminar cualquier coincidencia, porque en cualquier camino a través del gráfico, cada arista coincidente puede ser reemplazada por las otras dos aristas de su triángulo. Entre los gráficos con esta propiedad, los menos densos son los gráficos de cactus triangulares, que también son los gráficos localmente lineales menos densos. ^[4]

Aplicaciones

Una aplicación de los gráficos localmente lineales ocurre en la formulación de diagramas de Greechie, que se utilizan en lógica cuántica para ayudar a determinar si ciertas ecuaciones espaciales de Hilbert pueden inferirse entre sí. En esta aplicación, los triángulos de gráficos localmente lineales forman los bloques de diagramas de Greechie con un tamaño de bloque tres. Los diagramas de Greechie correspondientes a redes provienen de gráficos localmente lineales de circunferencia de hipergrafo cinco o más, ^[18] construidos, por ejemplo, a partir de gráficos de polaridad. ^[10]

Se puede utilizar una combinación de muestreo aleatorio y un lema de eliminación de gráficos para encontrar hipergráficos de 3 uniformes de gran circunferencia dentro de hipergráficos lineales de 3 uniformes arbitrarios o sistemas triples de Steiner parciales. Luego, este método se puede utilizar para demostrar límites inferiores asintóticamente ajustados en el número de independencia de hipergrafos lineales de 3 uniformes y sistemas triples parciales de Steiner. ^[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", Redes , 12 (4): 393–403, doi :10.1002/net.3230120404, MR  0686540; ver en particular p. 397: "A la red resultante la llamamos 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 politópicos localmente lineales", Mathematica Slovaca , 38 (2): 99–103, hdl : 10338.dmlcz/133017 , MR  0945363
6. Diabólicos, 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 , SEÑOR  2995054. En 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 gráficos subcúbicos sin triángulos", Matemáticas discretas , 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, SEÑOR  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, Félix; Verstraëte, Jacques (2003), "Sobre hipergrafías 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 singularidad del gráfico fuertemente regular (81,20,1,6), Una colección de contribuciones en honor a Jack van Lint, Matemáticas discretas , 106/107: 77–82, doi :10.1016/0012-365X(92)90532-K, SEÑOR  1181899
13. Berlekamp, ​​ER ; van Lint, JH ; Seidel, JJ (1973), "Un gráfico fuertemente regular derivado del código Golay ternario perfecto", A Survey of Combinatorial Theory (Proc. Internat. Sympos., Colorado State Univ., Fort Collins, Colorado, 1971) , Ámsterdam: Holanda Septentrional: 25–30, doi :10.1016/B978-0-7204-2262-7.50008-9, ISBN 9780720422627, SEÑOR  0364015
14. Cossidente, Antonio; Penttila, Tim (2005), "Hemisistemas en la superficie hermitiana", Revista de la Sociedad Matemática de Londres , Segunda Serie, 72 (3): 731–741, doi :10.1112/S0024610705006964, SEÑOR  2190334
15. Bondarenko, Andriy V.; Radchenko, Danylo V. (2013), "Sobre una familia de gráficos fuertemente regulares con ", Journal of Combinatorial Theory , Serie B, 103 (4): 521–531, arXiv : 1201.0383 , doi :10.1016/j.jctb.2013.05 .005, SEÑOR  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 de distancia regular 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 hipergrafías lineales uniformes , Desarrollos en matemáticas, vol. 63, Cham: Springer, págs. 171-177, doi :10.1007/978-3-030-46559-9_12, ISBN 978-3-030-46559-9, señor  4180641