En teoría de grafos , un grafo localmente lineal es un grafo no dirigido en el que cada borde pertenece a un triángulo único. De manera equivalente, para cada vértice del gráfico, los bordes entre los vecinos del vértice emparejan a todos los vecinos en una coincidencia inducida , de modo que cada vecino es adyacente exactamente a otro vecino. [1] Los gráficos localmente lineales también se han llamado gráficos localmente emparejados. [2]
Ejemplos de gráficas localmente lineales incluyen las gráficas triangulares de cactus , las gráficas lineales de tres gráficas regulares sin triángulos y los productos cartesianos de gráficas localmente lineales más pequeñas. Ciertos gráficos de Kneser y ciertos gráficos fuertemente regulares también son localmente lineales.
La cuestión de cuán densas pueden ser las gráficas localmente lineales (cuántas aristas pueden tener, en relación con el número total de pares de vértices) es una de las formulaciones del problema de Ruzsa-Szemerédi . Algunas gráficas localmente lineales tienen un número de aristas que está dentro de un factor pequeño, pero no constante, del número de pares de vértices. También se conocen los gráficos planos más densos que pueden ser localmente lineales.
Construcciones
Se conocen varias construcciones para gráficos localmente lineales.
Pegado y productos
Los gráficos de amistad , gráficos formados al pegar una colección de triángulos en un solo 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, todo gráfico de cactus triangular , un gráfico formado por pegar 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 la operación de suma de clique en los gráficos. Dejar y sean dos gráficos localmente lineales, 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, el gráfico resultante permanece localmente lineal. [5]
El producto cartesiano de cualesquiera dos gráficas localmente lineales permanece localmente lineal, porque cualquier triángulo en el producto proviene de triángulos en uno u otro factor. Por ejemplo, el gráfico de Paley de nueve vértices (el gráfico 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 de nuevo es localmente lineal. [6]
De gráficos más pequeños
Algunos gráficos que no son localmente lineales en sí mismos se pueden utilizar como marco para construir gráficos localmente lineales más grandes. Una de esas construcciones involucra gráficas lineales . Para cualquier gráfico, el gráfico de líneas es una gráfica que tiene un vértice para cada arista de . Dos vértices en son adyacentes cuando los dos bordes que representan en tienen un punto final común. Sies un gráfico libre de triángulos regulares de 3 , luego su gráfico lineales 4-regular y localmente lineal. Cada grafo local 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 arriba como un producto cartesiano, también se puede construir de una manera diferente como el gráfico lineal del gráfico de utilidad. . El gráfico de líneas del gráfico 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á en exactamente dos camarillas de bordes disjuntos y el ciclo más corto con bordes de camarillas distintas tiene una longitud de cinco. [8]
Se aplica un proceso de expansión más complicado a los gráficos planos . Dejarser 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. De la fórmula poliédrica de Euler se deduce que si posee vértices, tiene exactamente caras. Pegando un antiprisma cuadrado en cada cara de, y luego eliminar los bordes originales de , produce un nuevo gráfico plano localmente lineal con vértices y bordes. [5] Por ejemplo, el cuboctaedro se puede volver a producir de esta manera, a partir de las dos caras (interior y exterior) de un 4 ciclos.
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 posee vértices (en la notación estándar para coeficientes binomiales ), que representan el-subconjuntos de elementos de un -conjunto de elementos. En este gráfico, dos vértices son adyacentes cuando los subconjuntos correspondientes están separados. Para parámetros que obedecen a la ecuación, el gráfico resultante es localmente lineal, porque para cada dos -subconjuntos de elementos hay exactamente otro -subconjunto de elementos (el complemento de su unión) que es disjunto de ambos. El gráfico local lineal resultante tiene vértices y bordes. Por ejemplo, para el gráfico de Kneser es localmente lineal con 15 vértices y 45 aristas. [2]
Los gráficos localmente lineales también se pueden construir a partir de conjuntos de números sin progresión. Dejar ser un número primo y dejar ser un subconjunto de los números módulo de modo que no hay tres miembros de formar 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 bordes que es localmente lineal. Para construir esta gráfica, haga tres conjuntos de vértices, cada uno numerado de a y construir triángulos usando un vértice de cada uno de los tres conjuntos que conectan vértices numerados modulo , dónde es cualquier número en el rango de a y es cualquier elemento de . Por construcción, cada borde del gráfico resultante pertenece a un triángulo, pero no puede haber otros triángulos que los que se forman de esta manera. Cualquier otro triángulo tendría vértices numerados dónde , , 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.
Regularidad
Gráficos regulares con pocos vértices
Cada gráfico localmente lineal debe tener un grado par en cada vértice, porque las aristas de cada vértice se pueden emparejar en triángulos. El producto cartesiano de dos gráficos regulares localmente lineales es de nuevo 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áficos localmente lineales de grado dos (triángulos) para producir gráficos localmente lineales regulares de cada grado par. [1]
La -Los gráficos lineales locales 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). Las gráficas regulares con exactamente esta cantidad de vértices son posibles solo cuandoes 1, 2, 3 o 5, y se definen de forma única para cada uno de estos cuatro casos. Las cuatro gráficas regulares que cumplen con este límite en el número de vértices son el triángulo regular de 3 vértices 2, 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 complemento regular a 10 de 27 vértices del gráfico de Schläfli . El gráfico final de 27 vértices 10 regular también representa el gráfico de intersección de las 27 líneas en una superficie cúbica . [2]
Gráficos muy regulares
Un gráfico muy regular se puede caracterizar por un cuádruple de parámetros dónde 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. Cuándoel gráfico es localmente lineal. Los gráficos lineales locales ya mencionados anteriormente que son gráficos muy regulares y sus parámetros son [10]
- 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
- 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), [11]
- el gráfico Berlekamp-van Lint-Seidel (243,22,1,2), [12]
- el gráfico Cossidente-Penttila (378,52,1,8), [13] y
- el gráfico de Juegos (729,112,1,20). [14]
Otras combinaciones potencialmente válidas con incluyen (99,14,1,2) y (115,18,1,3) pero se desconoce si existen gráficos muy regulares con esos parámetros. [10] La cuestión de la existencia de un gráfico fuertemente regular con parámetros (99,14,1,2) se conoce como el problema de 99 gráficos de Conway , y John Horton Conway ha ofrecido un premio de $ 1000 por su solución. [15]
Gráficos de distancia regular
Hay un número finito de gráficos de distancia regular 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 Hammingy el gráfico de Foster reducido a la mitad . [dieciséis]
Densidad
Una formulación del problema Ruzsa-Szemerédi pide el número máximo de aristas en un-Gráfico lineal localmente 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 gráficos localmente lineales a partir de conjuntos sin progresión conduce a los gráficos localmente lineales más densos conocidos, conbordes. (En estas fórmulas,, , y son ejemplos de notación O pequeña , notación Omega grande y notación O grande , respectivamente). [9]
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 bordes, para , construido expandiendo las caras cuadriláteras de en antiprismas. Estos ejemplos muestran quese puede alcanzar el límite superior. [5]
Cada gráfico localmente lineal tiene la propiedad de permanecer conectado después de que se le quita cualquier coincidencia, porque en cualquier camino a través del gráfico, cada borde emparejado puede ser reemplazado por los otros dos bordes de su triángulo. Entre los gráficos con esta propiedad, los menos densos son los gráficos triangulares de cactus, que también son los gráficos localmente lineales menos densos. [4]
Referencias
- ^ a b c Fronček, Dalibor (1989), "Gráficos localmente lineales", Mathematica Slovaca , 39 (1): 3-6, hdl : 10338.dmlcz / 136481 , MR 1016323
- ^ a b c Larrión, F .; Pizaña, MA; Villarroel-Flores, R. (2011), "Pequeños gráficos localmente nK 2 " (PDF) , Ars Combinatoria , 102 : 385–391, MR 2867738
- ^ Erdős, Paul ; Rényi, Alfréd ; Sós, Vera T. (1966), "Sobre un problema de teoría de grafos" (PDF) , Studia Sci. Matemáticas. Hungar. , 1 : 215–235
- ^ a b Farley, Arthur M .; Proskurowski, Andrzej (1982), "Redes inmunes a fallas de líneas aisladas", Redes , 12 (4): 393–403, doi : 10.1002 / net.3230120404 , MR 0686540; ver en particular p. 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".
- ^ a b c Zelinka, Bohdan (1988), "Polytopic local linear graphs", Mathematica Slovaca , 38 (2): 99–103, hdl : 10338.dmlcz / 133017 , MR 0945363
- ^ Devillers, Alice; Jin, Wei; Li, Cai Heng; Praeger, Cheryl E. (2013), "Gráficos de clique y transitividad geodésica local 2", Journal of Combinatorial Theory , Serie A, 120 (2): 500–508, doi : 10.1016 / j.jcta.2012.10.004 , MR 2995054. En la notación de esta referencia, la familia de-Los gráficos regulares se denotan como .
- ^ Munaro, Andrea (2017), "Gráficas en línea de gráficas sin triángulos subcúbicos" , Matemáticas discretas , 340 (6): 1210–1226, doi : 10.1016 / j.disc.2017.01.006 , MR 3624607
- ^ Fan, Cong (1996), "On generalized cages", 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
- ^ a b Ruzsa, IZ ; Szemerédi, E. (1978), "Sistemas triples sin seis puntos que llevan tres triángulos", Combinatoria (Proc. Quinto Coloquio Húngaro, Keszthely, 1976), vol. II , Coloq. Matemáticas. Soc. János Bolyai, 18 , Amsterdam y Nueva York: North-Holland, págs. 939–945, MR 0519318
- ^ a b Makhnëv, AA (1988), "Gráficos muy regulares con ", Akademiya Nauk SSSR , 44 (5): 667–672, 702, doi : 10.1007 / BF01158426 , MR 0980587 , S2CID 120911900
- ^ 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, Discrete Mathematics , 106/107: 77-82, doi : 10.1016 / 0012-365X (92) 90532-K , Señor 1181899
- ^ 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) , Amsterdam: Holanda Septentrional: 25–30, doi : 10.1016 / B978-0-7204-2262-7.50008-9 , ISBN 9780720422627, MR 0364015
- ^ Cossidente, Antonio; Penttila, Tim (2005), "Hemisystems on the Hermitian surface", Journal of the London Mathematical Society , Segunda serie, 72 (3): 731–741, doi : 10.1112 / S0024610705006964 , MR 2190334
- ^ Bondarenko, Andriy V .; Radchenko, Danylo V. (2013), "En 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 , MR 3071380
- ^ Zehavi, Sa'ar; Oliveira, Ivo Fagundes David (2017), No el problema de 99 gráficos de Conway , arXiv : 1707.08047
- ^ 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