Noticias en español
Bounds 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 MoreNúmeros de Ramsey para árboles: Caso Doble estrella S(2m,m).
Abstract: Dados dos enteros n y m, denotamos por S(n,m) al grafo que consiste en dos estrellas de tamaño n y m, respectivamente, que están unidas por sus centros mediante una arista. En esta charla se pretende entregar el contexto histórico que tiene la teoría de Ramsey para árboles y además se mostrará una nueva cota superior para S(2m,m), lo que responde parcialmente una pregunta de Norin et.al del 2016. Se explicará a grandes rasgos la demostración de esta cota y además la estructura que tiene el coloreo extremal.
Read MoreOn extremal problems concerning the traces of sets.
Abstract: Given two non-negative integers n and s, define m(n,s) to be the maximal number such that in every hypergraph H on n vertices and with at most m(n,s) edges there is a vertex x such that |Hx|>|E(H)|-s, where Hx is the link graph of x. This problem has been posed by Füredi and Pach and by Frankl and Tokushige. While the first results were only for specific small values of s, Frankl determined m(n,2^{d-1}-1) for all d with d|n. Subsequently, the goal became to determine m(n,2^{d-1}-c) for larger c. Frankl and Watanabe determined m(n,2^{d-1}-c) for c=0,1,2. Other general results...
Read MoreRamsey Goodness of trees in random graphs.
Abstract: In 1977, Chvátal proved that every blue-red coloring of the edges of the complete graph on rn+1 vertices yields either a blue copy of the complete graph on r vertices or a red copy of each tree with r edges. This result was further extended by Burr and Erdős in 1983, starting a topic now known with the name of Ramsey goodness. In this talk, we will discuss a random analog of Chvátal’s theorem in sparse random graphs, which is one of the first results for Ramsey numbers of large graphs in sparse random graphs. If time permits, we will discuss some details of the proof and open...
Read MoreCondiciones tipo-Pósa para potencias de ciclos hamiltonianos.
Abstract: Un resultado clásico de Pósa dice que un grafo en n vértices es hamiltoniano si su secuencia de grados d_1 \leq \dotsb \leq d_n cumple d_i >= i+1, para todo i \leq n/2. Acá, generalizamos este resultado a potencias de ciclos. Una k-potencia de un ciclo hamiltoniano es el grafo que se obtiene de un ciclo al unir los vértices a distancia a lo más k. Demostramos que si G tiene n vértices v_1, …, v_n y se cumple d(v_i) >= (k-2)n/k + i + o(n) para todo i <= n/k, entonces el grafo tiene la (k-1)-potencia de un ciclo hamiltoniano. Esta condición es esencialmente la mejor...
Read More