Problemas extremales en teoría de grafos

Abstract

Uno de los problemas más representativos dentro de la Teoría Extremal de Grafos consiste en el estudio de los valores de la función ex (n; F), es decir, el tamaño máximo de un grafo de orden n sin contener a F como subgrafo. Es en este sentido donde podemos encuadrar los objetivos de esta tesis. Concretamente, abordaremos dos extensiones del modelo. Una de ellas consiste en el estudio de la función ex (n; TKp), que denota el número máximo de aristas de un grafo con n vértices sin contener como subgrafo una subdivisión del grafo completo de orden p. En la otra, mediante la función ex (n; Ks,t) buscaremos maximizar el tamaño de u grafo de orden n sin contener como subgrafo al grafo bipartito Ks,t. Como veremos a lo largo de esta memoria, estamos ante dos problemas extremales para los que que se conocen sólo respuestas paralelas y que han sido tratados principalmente desde un punto de vista asintótico, esto es, para valores suficientemente grandes de n. De hecho, los resultados han ido encaminados a la búsqueda de cotas para distintas funciones. Nuestro propósito es profundizar en la búsqueda de valores exactos para las funciones ex (n; TKp) y ex (n; Ks,t). Probaremos resultados de estructura que nos llevarán a encontrar acotaciones que conducen a tales valores exactos. Finalmente, y para los casos en que tales valores sean encontrados, caracterizaremos los que se conoce como familia de grafos extremales y que denotaremos por EX (n; TKp) y EX (n; Ks,t) respectivamente.