Noticias en español
The Hamilton Compression of Highly Symmetric Graphs.
Abstract: The relationship between symmetry and Hamiltonicity in graphs has gained much attention in recent years but is still not so well understood, this can be seen, for example, in the colliding conjectures of Lovász and Babai. To try to shed some light on this relationship, we introduce a measure of how symmetric the Hamilton cycles in a graph can be. We say that a Hamilton cycle C=x_1,…,x_n in a graph is k-symmetric, if the mapping x_i to x_(i+n/k) for all i=1,…,n, where indices are considered modulo n, is an automorphism of G. In other words, if we lay out the vertices...
Read MoreÁrboles generadores en grafos aleatorios III
Abstract: En los dos últimos seminarios vimos algunas técnicas utilizadas para encajar árboles con muchas hojas apartadas o con muchos caminos de largo medio en el grafo aleatorio. Finalizamos esta serie de seminarios sobre el artículo Spanning trees in random graphs de Montgomery, estudiando cómo se utiliza el método de absorción para encajar árboles con muchos caminos largos en el grafo aleatorio.
Read MoreÁ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