Hiperbolicidad de grafos en sentido de Gromov

Si X es un espacio métrico geodésico y x₁; x₂; x₃ ∈ X, un triángulo geodésico T = {x₁; x₂; x₃} es la unión de tres geodésicas [x₁x₂], [x₂x₃] y [x₃x₁] en X. El espacio X es ∂-hiperbólico (en sentido de Gromov) si cualquier lado del triángulo T está contenido en un ∂-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 ∈ [xixj] se verifica d(u, [xjxk] ∪ [xixk]). Denotamos por ∂(X) la constante de hiperbolicidad optimal de X, es decir, ∂(X) := inf{∂ 0 : X es ∂-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 ∂ (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 ∂(G) ≤ nk/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 ∂(G) = nk/4. También caracterizamos los grafos con aristas de longitud k con ∂(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: G₁ x G₂ 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 G₁ x G₂, (G₁), (G₂) y los diámetros de G₁ y G₂ (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