Noticias en español
Rainbow trees and graceful labellings.
Abstract: A tree T on n vertices is said to be graceful if there exists a bijective labelling f of its vertices to the set {1,2,…,n} such that the values of |f(x)-f(y)| are pairwise distinct over all edges xy in E(T), or equivalently, such that the set {|f(x)-f(y)| : xy in E(T)} has size exactly n-1. The longstanding graceful tree conjecture, posed by Rósa in the 1960s, asserts that every tree is graceful. We prove an approximate version of this conjecture by showing that every tree T on n vertices has a bijective labelling f of its vertices to the set {1,2,…,n} such that the set...
Read MoreEvolutionary graph theory.
Abstract: What does the coronavirus epidemic have in common with fake news on social media? They are both examples of real-world phenomena in which something (a virus, or the news) is spreading over a graph (a contact network, or a social network). In this talk, we will introduce some extremely simplified random processes that model how things could propagate through graphs, and we will investigate how the outcomes (e.g. “who wins” and “how long it takes”) depend on the graph structure, and on the little details of the underlying random process. Along the way, we will...
Read MoreChen-Chvátal Conjecture in Graphs and Hypergraphs.
Abstract: It is well known that a set of n non-collinear points in the Euclidean plane determines at least n distinct lines. In 2008, Chen and Chvátal conjectured that this result extends to arbitrary finite metric spaces with an appropriate definition of line. In this talk, we present a survey of this conjecture, outlining known results in the contexts of metric spaces, hypergraphs, and graphs
Read MoreThe Brown-Erdős-Sós conjecture in dense triple systems.
Abstract: In 1973, Brown, Erdős, and Sós conjectured, in an equivalent form, that for any $\delta > 0$ and integer $e \geq 3$, every sufficiently large linear 3-uniform hypergraph with at least $\delta n^2$ edges contains a collection of $e$ edges whose union spans at least $e+3$ vertices. In this talk, we show a proof of the conjecture for the case $\delta > 4/5$.
Read MoreThe Ramsey Number of Multiple Copies of a Graph
Abstract: Let H be a graph without isolated vertices. The Ramsey Number r(nH) is the minimum N such that every coloring of the edges of the complete graph on N vertices with red and blue contains n pairwise vertex-disjoint monochromatic copies of H of the same color. In 1975, Burr, Erdős and Spencer established that r(nH) is a linear function of n for large enough n. In 1987, Burr proved a superexponential upper bound for when the long-term linear behavior starts. In 2023, Bucic and Sudakov showed that the long-term linear behavior starts already when n is an exponential function of |H|...
Read MoreThe Ramsey Number of Hypergraph Cycles.
Abstract: In 1999, Łuczak proved that the three-coloured Ramsey number of the cycle of length $n$ is less than $(4+o(1))n$, presenting a technique that, conceptually, through the use of Szemerédi’s regularity lemma, reduces the problem to that of finding the Ramsey number of a connected matching. Ever since then, Łuczak’s method has been applied successfully in many results. There are many natural ways to generalize cycles for $k$-uniform hypergraphs. In this talk, we first present a brief survey of the Ramsey numbers of Berge, loose, and tight cycles. Then we examine the use...
Read More