Large Induced Matchings in Random Graphs

DOI10.1137/20M1330609zbMATH Open1459.05297arXiv2004.03359OpenAlexW3132429747MaRDI QIDQ5854458

Nemanja Draganić, Oliver Cooley, Mihyun Kang, Benjamin Sudakov

Publication date: 17 March 2021

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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 ErdH{o}s and Bollob'as, and Matula in 1976. In this paper we prove an asymptotically best possible result for induced matchings by showing that if $C/nleple0.99$ for some large constant $C$, then $G(n,p)$ contains an induced matching of order approximately $2lo{g}_q(np)$, where $q=frac11-p$.

Full work available at URL: https://arxiv.org/abs/2004.03359

zbMATH Keywords

random graphsPaley-Zygmund inequalityTalagrand's inequalityinduced matchings

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Trees in random graphs
• On the independence number of random graphs
• Induced trees in sparse random graphs
• On the order of the largest induced tree in a random graph
• Large holes in sparse random graphs
• Maximal induces trees in sparse random graphs
• On large induced trees and long induced paths in sparse random graphs
• The size of the largest hole in a random graph
• Large induced trees in sparse random graphs
• Cliques in random graphs
• On Induced Paths, Holes and Trees in Random Graphs

Related Items (7)

The inducibility of complete bipartite graphs ⋮ The largest hole in sparse random graphs ⋮ Induced forests in some distance-regular graphs ⋮ The largest hole in sparse random graphs ⋮ Induced forests and trees in Erdős-Rényi random graph ⋮ Parameterized results on acyclic matchings with implications for related problems ⋮ Strong and weighted matchings in inhomogenous random graphs

This page was built for publication: Large Induced Matchings in Random Graphs