Events Archive

Let F be a graph on r vertices and let G be a graph on n vertices. Then an F -factor in G is a subgraph of G composed of n/r vertex-disjoint copies of F , if r divides n. In other words, an F -factor yields a partition of the n vertices of G. The study of such F -factors in the Erdős–Rényi random graph dates back to Erdős himself. Decades later, in 2008, Johansson, Kahn and Vu established the thresholds for the existence of an F -factor for strictly 1-balanced F – up to the leading constant. The sharp thresholds, meaning the leading constants, were obtained only recently by Riordan and Heckel, but only for complete graphs and for so-called ‘nice’ graphs. Their results rely on sophisticated couplings that utilize the recent, celebrated solution of Shamir’s problem by Kahn. The talk will explain the basic ideas underlying the couplings by Riordan and Heckel, as well as extensions to strictly 1-balanced graphs F and hitting time results. The talk is based on joint work with Fabian Burghart, Annika Heckel, Marc Kaufmann and Matija Pasch.