Seminario de Grafos

Event Date: May 28, 2024 in Seminario de Grafos, Seminars

Abstract: On 14/5 I gave a talk revolving around the fat minor conjecture. On 15/5 a paper appeared on Arxiv claiming to disprove it. I will report on this new development and I will attempt to offer a comprehensive view of the new questions that it raises, such as “Is this for real?” and “What now?”.

Read More

Coarse Graph Theory I – The Questions

Event Date: May 14, 2024 in Seminario de Grafos, Seminars

Resumen: Coarse graph theory is concerned with the large-scale geometric properties of infinite graphs, especially the properties preserved by quasi-isometries. Although such inquiries have been raised since the 80’s, it was usually in the context of Cayley graphs and geometric group theory. Recently the topic migrated to graph theory with intriguing outcomes. Eventually, the field of coarse graph theory was officially inaugurated and systematically treated in a paper by Georgakopoulos and Papasoglu.   In this talk, I will explain the basics of coarse graph theory, exploreits...

Read More

A spectral proof of Szemerédi’s regularity lemma.

Event Date: May 07, 2024 in Seminario de Grafos, Seminars

Resumen: In this talk I will present the spectral proof of the regularity lemma due to Frieze and Kannan in the version popularized by Tao.

Read More

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