Hiperbolicidad de grafos en sentido de gromov

Abstract

Si X es un espacio métrico geodésico y x1, x2, x3 pertenece en X, un triángulo geodésico T= {x1, x2, x3} es la unión de tres geodésicas [x1x2], [x2x3] y [x3x1] en X. El espacio X es delta-hiperbólico (en sentido de Gromov) si cualquier lado del triángulo T está contenido en un delta-entorno de la unión de otros dos lados, para cada triángulo geodésico T en X, es decir, si para toda permutación {i, j, k} de {1, 2, 3} y para todo u en [xixj] se verifica d(u,[xjxk]U[xixk]<=delta. Denotamos por delta(X) la constante de hiperbolicidad optimal de X, es decir, delta(X):=inf{delta>= 0: X es delta -hiperbólico}. Esta tesis se enmarca dentro del estudio de las propiedades de los grafos hiperbólicos de Gromov, y forma parte de un amplio proyecto que involucra a numerosos investigadores de diversas universidades que trabajan en este mismo tema. Los resultados de esta tesis se presentan en dos secciones, en el tercer capítulo. En la primera de ellas relacionamos la constante de hiperbolicidad de un grafo con algunos parámetros del mismo grafo, como el cuello, el número de vértices y el diámetro: en particular, si g denota el cuello (el ínfimo de las longitudes de los ciclos del grafo), probamos que delta(G) >=g(G)/4 para todo grafo (finito o infinito, posiblemente con aristas múltiples y/o bucles); si G es un grafo con n vértices y aristas de longitud k (posiblemente con aristas múltiples y/o bucles), entonces delta(G) <=k/4. Además, demostramos que ambas desigualdades son óptimas: encontramos una gran familia de grafos para la cual la primera desigualdad es de hecho una igualdad; además, caracterizamos el conjunto de grafos con delta (G) = nk/4. También caracterizamos los grafos con aristas de longitud k con delta (G) < k. En la segunda sección estudiamos la hiperbolicidad de una clase especial de grafos, los grafos producto, obteniendo información valiosa sobre un grafo producto a partir de información sobre ambos factores. En particular, llegamos a caracterizar la hiperbolicidad del producto cartesiano de grafos: G1XG2 es hiperbólico si y sólo si uno de los factores es hiperbólico y el otro factor está acotado. También probamos algunas desigualdades optimales entre la constante de hiperbolicidad de G1XG2, delta(G1), delta (G2) y los diámetros de G1y G2 (y encontramos familias de grafos para los que se alcanzan las igualdades). Además, obtenemos el valor exacto de la constante de hiperbolicidad para muchos grafos producto.