Random cliques in random graphs and sharp thresholds for F F ‐factors. Issue 4 (22nd July 2022) - Riordan, Oliver
Abstract: We show that for each r ≥ 4 r4 , in a density range extending up to, and slightly beyond, the threshold for a K r K_r ‐factor, the copies of K r K_r in the random graph G ( n, p ) 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 ) G(n, p) to contain a K r K_r ‐factor. The case r = 3 r=3 is more difficult, and has been settled by Annika Heckel. We also prove a corresponding result for K r ( t ) K_r^(t) ‐factors in random t t ‐uniform hypergraphs, as well as (in some cases weaker) generalizations replacing K r K_r by certain other (hyper)graphs.