Noticias en español
Bipartite Ramsey numbers of paths for random graphs.
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 MoreCiclos hamiltonianos y simetría en los niveles medios del hipercubo.
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 MoreConjetura de Ryser en hipergrafos t-intersectantes.
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 MoreNúmero de Ramsey orientado para árboles.
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 MoreBounds on the unavoidability of some classes of directed trees, and algorithms for showing such embeddings.
Resumen: Decimos que un grafo dirigido H es m-inevitable si aparece como subgrafo de todo torneo en m vertices. En esta charla se presentará brevemente la historia del problema de acotar la inevitabilidad de distintas clases de arboles dirigidos. Se mostrarán resultados recientes, junto con algoritmos para realizar dichos embeddings.
Read MoreEmbedding de árboles en grafos expansores.
Resumen: Vamos hablar sobre el paper “Tree Embeddings”, de Penny E. Haxell. En este paper, Penny muestra un teorema general para embedding de árboles en grafos expansores, y como aplicación se probará un caso particular de la conjetura de Erdős-Sós, que pregunta si un grafo G con grado promedio a lo menos t-1 contiene todo árbol T con t aristas como subgrafo. Ella muestra que la conjetura es verdad si el grafo G no contiene K_{2,r}.
Read More