Árboles generadores en grafos densos I.

Abstract: 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.

 

 

Date: Aug 18, 2022 at 10:30:00 h
Date of closure: Aug 18, 2022
Venue: Sala de seminarios Jacques L Lions, CMM, Séptimo Piso Torre Norte.
Speaker: Giovanne Santos
Affiliation: DIM, F.C:F.M. Universidad de Chile
Coordinator: Maya Stein
More info at:
Event website
Abstract:
PDF

Posted on Aug 17, 2022 in Seminario de Grafos, Seminars