Projects per year
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\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 .
Original language  English 

Pages (fromto)  267280 
Number of pages  14 
Journal  SIAM Journal on Discrete Mathematics 
Volume  35 
Issue number  1 
DOIs  
Publication status  Published  2021 
Keywords
 Induced matchings
 Paleyzygmund inequality
 Random graphs
 Talagrand's inequality
ASJC Scopus subject areas
 Mathematics(all)
Fields of Expertise
 Information, Communication & Computing
Projects
 1 Finished

FWF  Cores  Random Graphs: Cores, Colourings and Contagion
1/09/18 → 30/06/22
Project: Research project