Seminario de Grafos

Aumentando óptimamente la nodo-conectividad de un ciclo en uno.

Event Date: Jan 07, 2021 in Seminario de Grafos, Seminars

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 More

Casi todos los árboles dirigidos son n-inevitables.

Event Date: Dec 17, 2020 in Seminario de Grafos, Seminars

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

Bipartite Ramsey numbers of paths for random graphs.

Event Date: Dec 10, 2020 in Seminario de Grafos, Seminars

    Resumen: Dado dos grafos G y H, decimos que G —> H si para todo 2-coloreo (rojo/azul) de las aristas de G contiene una copia de H monocromática. Sea G(K_k(n),p) un espacio de grafos aleatorios con probabilidad de aristas p, donde K_k(n) es el grafo completo k-partito con n vértices en cada parte. Demostramos que si np va a infinito entonces la probabilidad de que G(K_k(n),p) —>P_(k-1-o(1))n tiende a 1 para k=2,3.

Read More

Ciclos hamiltonianos y simetría en los niveles medios del hipercubo.

Event Date: Dec 03, 2020 in Seminario de Grafos, Seminars

Abstract: Consideremos el grafo de los niveles medios que tiene como vértices todos los bitstrings de largo 2n+1 con exactamente n o n+1 unos, y aristas entre todo par de bitstrings que difieren en exactamente una coordenada. El recientemente demostrado teorema de los niveles medios dicta que este grafo tiene un ciclo hamiltoniano. Siendo los niveles medios un grafo altamente simétrico, este teorema es uno de los ejemplos más notables de la conjetura de Lovász: Todo grafo conexo y altamente simétrico (salvo 5 excepciones) tiene un ciclo hamiltoniano. Dicha interacción entre simetría y...

Read More

Conjetura de Ryser en hipergrafos t-intersectantes.

Event Date: Nov 19, 2020 in Seminario de Grafos, Seminars

Resumen: La conjetura de Ryser establece que el número de cover de un hipergrafo r-partito r-uniforme es a lo más (r-1)  veces el tamaño de su número de matching. En esta charla, revisaremos avances recientes en cotas para la conjetura en hipergrafos t intersectantes dadas ciertas restricciones asociadas a r y t.

Read More

Número de Ramsey orientado para árboles.

Event Date: Nov 05, 2020 in Seminario de Grafos, Seminars

Resumen: En grafos con orientación puede hablarse del número de Ramsey orientado, el análogo al aplicado en grafos simples pero en un torneo en vez de un Kn. En esta charla se mostrarán dos de los tres resultados importantes del paper “Directed Ramsey number for trees” de Bucić, Letzter y Sudakov, publicado el año 2018, uno que entrega una cota superior para el número de Ramsey orientado k-coloreado para un árbol orientado cualquiera, y el otro que entrega cota inferior y superior del mismo número para un camino de largo n.  

Read More