Random cliques in random graphs and sharp thresholds for F-factors - Riordan, O (Wiley, 2022)
We show that for each r ≥ 4, in a density range extending up to, and slightly beyond, the threshold for a Kr-factor, the copies of Kr in the random graph G(n, p) are randomly distributed, in the (one-sided) sense that the hypergraph that they form contains a copy of a binomial random hypergraph with almost exactly the right density. Thus Jeff Kahn’s recent asymptotically sharp bound for the threshold in Shamir’s hypergraph matching problem implies a corresponding bound for the threshold for G(n, p) to contain a Kr-factor. The case r = 3 is more difficult, and has been settled by Annika Heckel. We also prove a corresponding result for K (t) r -factors in random t-uniform hypergraphs, as well as (in some cases weaker) generalizations replacing Kr by certain other (hyper)graphs.