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 $$ r\ge 4 $$, 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\left(n, p\right) $$ 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\left(n, p\right) $$ 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.