Covers and Factors beyond Cliques

The random graph process G(n,m) is a classical model of generating random graphs. Starting on n vertices, edges are included one at a time chosen uniformly at random among all pairs of non-adjacent vertices. Investigating the times at which the graph process first exhibits a certain behaviour as n tends to infinity is a classical question that has received a lot of attention in the past decades.

In their recent work, Heckel, Kaufmann, Müller, and Pasch showed that with high probability, the first moment in the random graph process when every vertex is contained in some clique on r vertices is also the first moment when the graph can be partitioned into disjoint copies of such cliques. This relies on previous results by Kahn, Riordan, and Heckel, the latter two of which provided couplings between the random graph process and a similarly defined hypergraph process.

The aim of this project is to extend – when possible – the equality between the two hitting times to subgraphs that are not cliques. This requires both the careful adaptation and far-reaching generalization of previously established techniques and will likely lead to interesting probabilistic and combinatorial phenomena.