Resumen de Problemas extremales en teoría de grafos
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 artistas 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 un grafo de orden n sin contener como subgrafo al grafo bipartito Ks,t.
Como veremos a lo largo de este trabajo, estamos ante dos problemas extremales para los que se conocen sólo respuestas parciales 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 dichas 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 lo que se conoce como familia de grafos extremales y que denotaremos por EX(n;TKp) y EX(n;Ks,t) respectivamente.
