Noticias en español
Exact positive codegree thresholds for perfect matching.
Abstract: Rödl, Ruciński and Szemerédi found best-possible codegree conditions that force the existence of perfect matchings in $k$-graphs. Given that the codegree is too strong for many applications, we study this question for a weaker, but more versatile degree condition, which maintains the codegree’s constructive power: the positive codegree. For a $k$-graph, this corresponds to the minimum degree over all sets of size $k-1$ with degree at least one. For $k\geq 3$ , we show exact minimum positive codegree conditions for the existence of perfect matchings in $k$-graphs with no...
Read MoreRainbow 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 More