Abstract: En el último seminario vimos un resultado de Komlós, Sárközy y Szemerédi de 1995 sobre la existencia de árboles generadores de grado máximo acotado en grafos densos. Este resultado fue mejorado en 2001 por los mismos autores, quienes demostraron que se puede encontrar árboles generadores de grado máximo O(n/log n) en grafos densos.

 

Recientemente, Kathapurkar y Montgomery presentaron una generalización de este resultado para grafos dirigidos. A diferencia de los resultados anteriores, la demostración de esta generalización no utiliza el Lema de Regularidad. En este seminario vamos a estudiar esta generalización y algunas técnicas utilizadas en la demostración.

Date: Aug 25, 2022 at 10:30:00 h
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