Large induced matchings in random graphs

Abstract

Given a large graph $H$, does the binomial random graph $G(n,p)$ contain a copy of $H$ as an induced subgraph with high probability? This classical question has been studied extensively for various graphs $H$, going back to the study of the independence number of $G(n,p)$ by Erdős and Bollobás, and Matula in 1976. In this paper we prove an asymptotically best possible result for induced matchings by showing that if $C/n\le p\le 0.99$ for some large constant $C$, then $G(n,p)$ contains an induced matching of order approximately $2{\log }_q(np)$, where $q=\frac{1}{1-p}$.