Noticias en español
Conjetura de Merino—Welsch.
Resumen: En 1999 Criel Merino y Dominic Welsh conjeturan que para cada grafo conexo sin loops ni puentes, se cumple que el número de spanning trees es menor que el máximo entre el número de orientaciones cíclicas y el número de orientaciones totalmente acíclicas. Como estas tres cantidades son evaluaciones del polinomio de Tutte, esta pregunta puede ser formulada en el contexto más amplio de matroides no necesariamente gráficas Luego de varios resultados parciales, la versión matroide fue des-probada la semana pasada, pero el contraejemplo no es simple ni viene de un grafo. Vamos a repasar...
Read MoreOn the ascending subgraph decomposition problem.
Abstract: A decomposition of a graph G is a collection of graphs H_1,…,H_m such that G is an edge-disjoint union of H_1,…,H_m. We say that G has an ascending subgraph decomposition if there exists a decomposition of G such that e(H_i) = i, and each H_i is isomorphic to a subgraph of H_{i+1}. A necessary conditi
Read MoreAlmost spanning universality in random graphs.
Resumen: We will study embeddings of large graphs of bounded degree in G(n,p). Johansson, Kahn, Vu determined the threshold for G(n,p) to contain a K_(r+1)-factor, i.e., a collection of n/(r+1) vertex disjoint copies of K_(r+1). The threshold turns out to be the same as for the property ‘every vertex is contained in a (r+1)-clique’, which is a necessary condition for containing a K_(r+1)-factor. Now for integers t,D, let H(t,D) be the class of t-vertex graphs and maximum degree at most D. It is conjectured that whp G(n,p) should contain every graph in H(n,D) as soon as it...
Read MoreCondiciones de grado mínimo para subdivisiones generadoras.
Resumen: En esta charla mostraremos que en todo grafo con n vértices y grado mínimo ligeramente por sobre n/2 es posible encontrar la subdivisión de un grafo completo, la que además usa todos los vértices del grafo huésped y donde cada arista está subdividida casi la misma cantidad de veces. La demostración es completamente probabilista y no usa ningún tipo de argumento tipo absorción o regularidad.
Read MoreCondiciones de grado mínimo para caminos y ciclos monocromáticos en grafos 2-arista-coloreados (segunda parte).
Abstract: Diremos que un grafo $G$ apunta a un grafo $H$ si es que en cada $2$-arista-coloreo de $G$ existe una copia monocromática de $H$. Schelp tenía la idea de que si el grafo completo $K_n$ apunta un grafo pequeño $H$, entonces cada subgrafo denso de $K_n$ también apunta a H.En este seminario, veremos un resultado demostrado por Balogh, Kostochka, Lavrov y Liu en 2021 ( https://arxiv.org/pdf/1906.02854.pdf ) que indica que “para todo $n$ suficientemente grande, si $n = 3t + r$ donde $r\in\{0,1,2\} y $G$ es un grafo en $n$ vértices con $\delta(G) \geq (3n-1)/4$,entonces para todo...
Read MoreCondiciones de grado mínimo para caminos y ciclos monocromáticos en grafos 2-arista-coloreados.
Abstract: Diremos que un grafo $G$ apunta a un grafo $H$ si es que en cada $2$-arista-coloreo de $G$ existe una copia monocromática de $H$. Schelp tenía la idea de que si el grafo completo $K_n$ apunta un grafo pequeño $H$, entonces cada subgrafo denso de $K_n$ también apunta a H.
Read More