Sharp thresholds for 1-balanced factors in random graphs
Let $F$ be a graph on $r$ vertices and let $G$ be a graph on $n$ vertices. An $F$-factor in $G$ is a subgraph of $G$ composed of $n/r$ vertex-disjoint copies of $F$, if $r$ divides $n$. For instance, a $K_2$-factor is simply a perfect matching. The study of threshold functions for $F$-factors in $G(n,p)$ goes back to Erdős and Rényi themselves; but for general $F$ it was not until the 2008 breakthrough paper by Johansson, Kahn and Vu that the weak threshold for strictly 1-balanced $F$ was established. More recently, Riordan and Heckel obtained sharp thresholds for $F=K_r$ and so-called nice graphs, using sophisticated coupling arguments that utilize Kahn's recent celebrated solution of Shamir's problem on hypergraph matchings. This talk reviews these results and extends them to sharp thresholds for any strictly 1-balanced $F$. In particular, this confirms the thirty year old conjecture by Ruciński that the sharp threshold for the emergence of an $F$-factor coincides with the sharp threshold for the disappearance of the last vertex that is not contained in a copy of $F$.
This is joint work with A. Heckel, M. Kaufmann, N. Müller and M. Pasch.