Georgia Institute of Technology College of Sciences

For positive integers $d < k$ and $n$ divisible by $k$, let $m_d(k,n)$ be the minimum $d$-degree ensuring the existence of a perfect matching in a $k$-uniform hypergraph. In the graph case (where $k=2$), a classical theorem of Dirac says that $m_1(2,n) = \lceil n/2\rceil$. However, in general, our understanding of the values of $m_d(k,n)$ is still very limited, and it is an active topic of research to determine or approximate these values. In the first part of this talk, we discuss a new "transference" theorem for Dirac-type results relative to random hypergraphs. Specifically, we prove that a random $k$-uniform hypergraph $G$ with $n$ vertices and "not too small" edge probability $p$ typically has the property that every spanning subgraph with minimum $d$-degree at least $(1+\varepsilon)m_d(k,n)p$ has a perfect matching. One interesting aspect of our proof is a "non-constructive" application of the absorbing method, which allows us to prove a bound in terms of $m_d(k,n)$ without actually knowing its value.

The ideas in our work are quite powerful and can be applied to other problems: in the second part of this talk we highlight a recent application of these ideas to random designs, proving that a random Steiner triple system typically admits a decomposition of almost all its triples into perfect matchings (that is to say, it is almost resolvable).

Joint work with Asaf Ferber.

Hadwiger's conjecture from 1943 states that every graph with no $K_t$ minor is $(t-1)$-colorable for every $t\ge 1$. In the early 1980s, Kostochka and Thomason independently proved that every graph with no $K_t$ minor has average degree $O(t\sqrt{\log t})$ and hence is $O(t\sqrt{\log t})$-colorable.  In this talk, we show that every graph with no $K_t$ minor is $O(t(\log t)^{\beta})$-colorable for every $\beta > 1/4$, making the first improvement on the order of magnitude of the Kostochka-Thomason bound. 

This is joint work with  Sergey Norin and Luke Postle.

A graph G is F-saturated if G is F-free and G+e is not F-free for any edge not in G. The saturation number of F, is the minimum number of edges in an n-vertex F-saturated graph. We consider analogues of this problem in other settings.  In particular we prove saturation versions of some Ramsey-type theorems on graphs and Dilworth-type theorems on posets. We also consider semisaturation problems, wherein we only require that any extension of the combinatorial structure creates new copies of the forbidden configuration.  In this setting, we prove a semisaturation version of the Erdös-Szekeres theorem on convex k-gons, as well as multiple semisaturation theorems for sequences and posets. Joint work with Gábor Damásdi, Balázs Keszegh, David Malec, Casey Tompkins, and Oscar Zamora.

An edge-colored graph $G$ is called \textit{rainbow} if every edge of $G$ receives a different color. The \textit{anti-Ramsey} number of $t$ edge-disjoint rainbow spanning trees, denoted by $r(n,t)$, is defined as the maximum number of colors in an edge-coloring of $K_n$ containing no $t$ edge-disjoint rainbow spanning trees. Jahanbekam and West [{\em J. Graph Theory, 2016}] conjectured that for any fixed $t$, $r(n,t)=\binom{n-2}{2}+t$ whenever $n\geq 2t+2 \geq 6$. We show their conjecture is true and also determine $r(n,t)$ when $n = 2t+1$. Together with previous results, this gives the anti-Ramsey number of $t$ edge-disjoint rainbow spanning trees for all values of $n$ and $t$. Joint work with Linyuan Lu.