Large Induced Matchings in Random Graphs

Oliver Cooley, Nemanja Dragani, Mihyun Kang, Benny Sudakov

Publikation: Beitrag in einer FachzeitschriftArtikelBegutachtung


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\H os and Bollob\'as and by Matula in 1976. In this paper we prove an asymptotically best possible result for induced matchings by showing that if C/n \leq p \leq 0.99 for some large constant C, then G(n, p) contains an induced matching of order approximately 2 logq(np), where q = 1 1 p .

Seiten (von - bis)267-280
FachzeitschriftSIAM Journal on Discrete Mathematics
PublikationsstatusVeröffentlicht - 2021

ASJC Scopus subject areas

  • Mathematik (insg.)

Fields of Expertise

  • Information, Communication & Computing

Dieses zitieren