Random triangles in random graphs
Abstract
In a recent paper, Oliver Riordan shows that for $r \ge 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,\pi)$ with $\pi \sim 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 \ge 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 \ge 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)$.
 Publication:

arXiv eprints
 Pub Date:
 February 2018
 arXiv:
 arXiv:1802.08472
 Bibcode:
 2018arXiv180208472H
 Keywords:

 Mathematics  Combinatorics;
 05C80;
 05C70;
 05C65
 EPrint:
 4 pages