Seminario de Grafos

Conjetura de Merino—Welsch.

Event Date: Nov 21, 2023 in Seminario de Grafos, Seminars

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 More

On the ascending subgraph decomposition problem.

Event Date: Nov 07, 2023 in Seminario de Grafos, Seminars

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 More

Almost spanning universality in random graphs.

Event Date: Oct 24, 2023 in Seminario de Grafos, Seminars

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 More

Condiciones de grado mínimo para subdivisiones generadoras.

Event Date: Oct 17, 2023 in Seminario de Grafos, Seminars

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 More

Condiciones de grado mínimo para caminos y ciclos monocromáticos en grafos 2-arista-coloreados (segunda parte).

Event Date: Jun 15, 2023 in Seminario de Grafos, Seminars

 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 More

Condiciones de grado mínimo para caminos y ciclos monocromáticos en grafos 2-arista-coloreados.

Event Date: Jun 08, 2023 in Seminario de Grafos, Seminars

 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