Árboles generadores en grafos densos II.

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.