Árboles generadores en grafos densos I.

ract: Dados dos grafos H y G un problema central en teoría de grafos extremales es determinar condiciones globales en G que garantizan la existencia de una copia de H en G. Un ejemplo de resultado en esa dirección es el Teorema de Dirac, que afirma que si G es un grafo en nvértices con grado mínimo al menos n/2, entonces existe una copia del ciclo en n vértices en G. En este seminario vamos a estudiar la relación entre el grado mínimo de G y la existencia de copias de diferentes árboles generadores de G. Más específicamente, vamos a ver el artículo Proof of a Packing Conjecture of Bollobás de Komlós, Sárközy  y Szemerédi de 1995. En ese artículo fue mostrado que si G es un grafo en nvértices con grado mínimo n/2 + o(n) y T es un árbol en n vértices con grado máximo acotado, entonces existe una copia de T en G. Cabe resaltar que esa demostración es una de las primeras aplicaciones del Blow-up lemma.