Noticias en español
Ciclos de largo dado en grafos orientados.
Resumen: En esta charla se mostrará que para todo l > 3, todo grafo orientado contiene un ciclo de tamaño exactamente l, bajo ciertas condiciones de tamaño y semigrado mínimo. Además se mostrarán conjeturas relacionadas y aplicaciones sobre panciclicidad.
Read MoreOriented trees via chromatic number.
Resumen: It is folklore that every graph G contains every tree T whose order is at most \chi(G), the chromatic number of G. This is no longer necessarily true if G and T are oriented. In 1980, Burr conjectured that an arbitrary orientation of a graph G contains every oriented tree of order 1 + \chi(G)/2. We will present related questions and recent advances relating to this conjecture.
Read MoreCaminos monocromáticos en digrafos pseudoaleatorios.
Resumen: En esta charla se presentará una noción pseudoaleatoriedad para digrafos, y se mostrarán resultados sobre cómo encontrar caminos dirigidos monocromáticos largos. Usando esta estrategia se encuentra una cota superior para el “Size Ramsey Number” de caminos en grafos dirigidos.
Read MoreExpansión sublineal en grafos.
Resumen: En esta charla introduciremos los aspectos básicos de los grafos con expansión sublineal y su uso en problemas extremales. En particular, mostraremos una aplicación sencilla para encontrar subdivisiones del grafo completo en grafos con grado promedio relativamente bajo. Acá el link al zoom: https://uchile.zoom.us/j/83539034403?pwd=NlZ6UGwzNndpZHNZNThGSzViMldLdz09 password 624=05
Read MoreAumentando óptimamente la nodo-conectividad de un ciclo en uno.
Abstract: “Definimos el problema de “aumentación de conectividad de grafos” de la forma siguiente: La entrada es un grafo G y un conjunto de aristas E, tal que G es k-conexo y G+E es (k+1)-conexo. Y la salida debe ser un subconjunto F de E de tamaño mínimo tal que G+F sea (k+1)-conexo. Este tipo de problemas se enmarcan en el diseño de redes, muy importante en áreas tales como telecomunicaciones y electricidad. Muchos de estos problemas son NP-dificiles, por lo que es necesario diseñar algoritmos de aproximación para atacar el problema. En este seminario mostraré un resumen...
Read MoreCasi todos los árboles dirigidos son n-inevitables.
Resumen: Se mostrará una condición suficiente para ver que un árbol dirigido es n-inevitable, esto se probará a través de un resultado de descomposición de torneos de Kühn, Mycroft y Osthus, y el uso lema de embedding semi-determinista, que nos permite embeber árboles en n-o(1) vértices, finalmente se verá que las condiciones suficientes se cumplen asintótica-casi-seguramente.
Read More