Georgia Institute of Technology College of Sciences

The notion of weak saturation was introduced by Bollobás in 1968. A graph $G$ on $n$ vertices is weakly $F$-saturated if the edges of $E(K_n) \setminus  E(G)$ can be added to $G$, one edge at a time, in such a way that every added edge creates a new copy of $F$. The minimum size of a weakly $F$-saturated graph $G$ of order $n$ is denoted by $\mathrm{wsat}(n, F)$. In this talk, we discuss the weak saturation number of complete bipartite graphs and determine $\mathrm{wsat}(n, K_{t,t})$ whenever $n > 3t-4$. For fixed $1

The following are two classical questions in the area of universal graphs.

1. What is the minimum number of vertices in a graph that contains all $n$-vertex planar graphs as induced subgraphs?

2. What is the minimum number of edges in a graph that contains all $n$-vertex planar graphs as subgraphs?

We give nearly optimal constructions for each problem, i.e. with $n^{1+o(1)}$ vertices for Question 1 and $n^{1+o(1)}$ edges for Question 2. The proofs combine a recent structure theorem for planar graphs (of independent interest) with techniques from data structures.

Joint work with V. Dujmovic, C. Gavoille, G. Joret, P. Micek, and P. Morin.

Erdős, Pach, Pollack and Tuza conjectured that for fixed integers $r$, $\delta \ge 2$, for any connected graph $G$ with minimum degree $\delta$ and order $n$:

(i) If $G$ is $K_{2r}$-free and $\delta$ is a multiple of $(r-1)(3r+2)$, then, as $n$ tends to infinity, the diameter of $G$ is at most $\frac{2(r-1)(3r+2)}{(2r^2-1)} \cdot \frac{n}{\delta} + O(1)$.

(ii) If $G$ is $K_{2r+1}$-free and $\delta$ is a multiple of $3r-1$, then, as $n$ tends to infinity, the diameter of $G$ is at most $\frac{3r-1}{r} \cdot \frac{n}{\delta} + O(1)$.

They created examples that show that the above conjecture, if true, is tight.

No more progress has been reported on this conjecture, except that for $r=2$ in (ii), under a stronger hypothesis ($4$-colorable instead of $K_5$-free), Czabarka, Dankelman and Székely showed that for every connected $4$-colorable graph $G$ of order $n$ and minimum degree $\delta \ge 1$, the diameter of $G$ is at most $\frac{5n}{2\delta} - 1$.

For every $r>1$ and $\delta \ge 2(r-1)$, we create $K_{2r}$-free graphs with minimum degree $\delta$ and diameter $\frac{(6r-5)n}{(2r-1)\delta+2r-3}+O(1)$, which are counterexamples to the conjecture for every $r>1$ and $\delta > 2(r-1)(3r+2)(2r-3)$. We also prove positive results under a stronger hypothesis, $k$-colorability, instead of being $K_{k+1}$-free. We show that the diameter of connected $k$-colorable graphs with minimum degree at least $\delta$ and order $n$ is at most $\left(3-\frac{1}{k-1}\right)\frac{n}{\delta}+O(1)$, while for $k=3$, it is at most $\frac{57n}{23\delta}+O(1)$.

This is joint work with Inne Singgih and László A. Székely.

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.