Seminario de Grafos

Hamiltonicity in pseudorandom graphs: absorbing paths.

Event Date: Jun 11, 2024 in Seminario de Grafos, Seminars

Abstract:  In this second talk, we will introduce the “extendability method” for embedding sparse structures in expander graphs and we will use it to construct efficient absorbers to solve the Hamiltonicity problem in pseudorandom graphs.

Hamiltonicity in pseudorandom graphs: Pósa rotation.

Event Date: Jun 04, 2024 in Seminario de Grafos, Seminars

Abstract: In this series of talks, we will study different approaches to the Hamiltonicity problem in sparse pseudorandom graphs. In this first talk, we will review the celebrated “extension-rotation” technique pioneered by Pósa in the 70s and how to use it in pseudorandom graphs to find Hamilton cycles.

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?”.

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...

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.

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...