Random triangles in random graphs. Issue 4 (26th May 2021)

• Record Type: Journal Article
• Authors: Heckel, Annika
• Is Part Of: Random structures & algorithms. Volume 59:Issue 4(2021)
• Page Start: 616
• Page End: 621
• Publication Date: 2021-05-26
• Subjects: coupling -- random graphs -- random hypergraphs; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.21013
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: In a recent paper, Oliver Riordan shows that for r ≥ 4 and p up to and slightly larger than the threshold for a K r ‐factor, the hypergraph formed by the copies of K r in G ( n, p ) contains a copy of the binomial random hypergraph H = H r ( n, π ) with π ∼ p r 2 . For r = 3, he gives a slightly weaker result where the density in the random hypergraph is reduced by a constant factor. Recently, Jeff Kahn announced an asymptotically sharp bound for the threshold in Shamir's hypergraph matching problem for all r ≥ 3 . With Riordan's result, this immediately implies an asymptotically sharp bound for the threshold of a K r ‐factor in G ( n, p ) for r ≥ 4 . In this note, we resolve the missing case r = 3 by modifying Riordan's argument. This means that Kahn's result also implies a sharp bound for triangle factors in G ( n, p ).