Seminario de Grafos

Expansión sublineal en grafos.

Event Date: Apr 12, 2021 in Seminario de Grafos, Seminars

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 More

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