Noticias en español
Árboles generadores en grafos aleatorios II.
Abstract: En el último seminario vimos que el grafo aleatorio binomial Gn,p es universal para la familia de árboles con muchas hojas apartadas. Siguiendo con el estudio del artículo “Spanning trees in random graphs” de Montgomery, en este seminario, veremos las técnicas utilizadas para demostrar que Gn,p es universal para árboles con muchos caminos de determinado largo. En especial, se presentará el método de rotación-extensión de Pósa para encontrar caminos largos en grafos.
Read MoreÁrboles generadores en grafos aleatorios I
Abstract: En 2015, Kahn conjeturó que para todo ∆ ∊ ℕ, existe un C > 0 tal que para toda secuencia de árboles (Tn)_{n in ℕ}, donde Tn es un árbol en n vértices con ∆(Tn) ≤ ∆, la probabilidad de que el grafo aleatorio G(n,Clogn/n) contenga Tn tiende a 1 cuando n tiende al infinito. Montgomery en el artículo “Spanning trees in random graphs” de 2019, demostró que esta conjetura es cierta. Además, demostró que G(n,Clogn/n) es universal para árboles con grado máximo acotado. En este seminario, veremos un caso específico de este resultado para árboles con grado máximo acotado y...
Read MoreNúmero cromático de grafos de distancia exacta.
Abstract: Se presentarán los principales resultados del paper “Chromatic numbers of exact distance graphs” (https://doi.org/10.1016/j.jctb.2018.05.007) El grafo de distancia exacta p de un grafo G=(V,E) es el grafo con el mismo conjunto de vértices que G y entre dos vértices hay una arista si y sólo si estos vértices están a distancia exactamente p en G. Usando la noción de números de coloreos generalizados se encontrarán cotas para el número cromático de grafos de distancia exacta p, separando los casos en que p sea impar y el caso en que es...
Read MoreÁrboles generadores en grafos densos III.
Abstract: En este seminario seguimos estudiando el artículo Spanning trees in dense directed graphs de Kathapurkar y Montgomery. Más específicamente, veremos cómo encontrar copias de algunos árboles casi-generadores en grafos densos. Además, vamos a ver como el Lema de Regularidad, utilizado en la demostración de otros resultados en el área, es reemplazado por un proceso aleatorio para encontrar la copia del árbol.
Read MoreÁ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...
Read MoreÁ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...
Read More