Random cliques in random graphs and sharp thresholds for F$$ F $$‐factors. Issue 4 (22nd July 2022)

• Record Type: Journal Article
• Authors: Riordan, Oliver
• Is Part Of: Random structures & algorithms. Volume 61:Issue 4(2022)
• Page Start: 619
• Page End: 637
• Publication Date: 2022-07-22
• Subjects: factors -- hypergraphs -- random graphs; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.21111
• Languages: English
• ISSNs: 1042-9832

Abstract

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.