Random triangles in random graphs

2018/02/23 by Heckel, Annika
#05C65 #05C70 #05C80 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1802.08472

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 \choose 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).

Related

• Random cliques in random graphs and sharp thresholds for F-factors
• Random cliques in random graphs revisited
• The hitting time of clique factors
• Factors in random graphs
• Sharp Thresholds for Factors in Random Graphs