Noticias en español
On 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 MoreReconocimiento y caracterización de cuadrados exactos de grafos.
Abstract: Para un grafo G=(V,E) se define su cuadrado exacto, G^{[#2]}, como el grafocon el mismo conjunto de vértices V en donde una arista uv está en el cuadrado exacto si y solo si u y v están a distancia 2 en el grafo original G. Se dice que G es una raíz (cuadrada) exacta de G^{[#2]}. Se mostrará una caracterización de los grafos que tienen raíz exacta, donde dicha caracterización permite fácilmente crear un algoritmo de reconocimiento en tiempo polinomial. Se mostrará que reconocer grafos que tienen una raíz exacta que es bipartita es un problema NP-completo. Se presentará una...
Read More