Skip navigation

Sharp thresholds and hitting times for factors in the Binomial random graph

Oberseminar Mainz

Date: 04.11.2025

Time: 14:15–16:15 h

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.

Speaker

Noela Müller, Universität Eindhoven

Place

Uni Mainz, Institut für Mathematik, Raum 05-136
Johannes-Gutenberg-Universität Mainz, Institut für Mathematik, Staudingerweg 9, 55128 Mainz, Deutschland


Organizing partners

Technische Universität Darmstadt, Goethe-Universität Frankfurt am Main

For this event, no registration is necessary. PDF- Link