Large induced matchings in random graphs

DOI10.1137/20M1330609MaRDI QIDQ5854458zbMATH OpenOpenAlexFDO

Authors Oliver Cooley, Nemanja Draganić, Mihyun Kang, Benny Sudakov

Publication date 17 March 2021

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

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

zbMATH Keywords

induced matchingsPaley-Zygmund inequalityrandom graphsTalagrand's inequality

Mathematics Subject Classification ID

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

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$.

Recommendations

• scientific article; zbMATH DE number 4087713
• The strong matching number of a random graph
• scientific article; zbMATH DE number 1696620
• Combinatorial Geometry and Graph Theory
• Maximum induced matchings of random cubic graphs

Cites work

• Cliques in random graphs
• scientific article; zbMATH DE number 4087713 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 3999982 (Why is no real title available?)
• scientific article; zbMATH DE number 932179 (Why is no real title available?)
• Induced trees in sparse random graphs
• Large holes in sparse random graphs
• Large induced trees in sparse random graphs
• Maximal induces trees in sparse random graphs
• On induced paths, holes and trees in random graphs
• On large induced trees and long induced paths in sparse random graphs
• On the independence number of random graphs
• On the order of the largest induced tree in a random graph
• The probabilistic method
• The size of the largest hole in a random graph
• The strong matching number of a random graph
• Trees in random graphs

Cited in

(16)

• On large matchings and cycles in sparse random graphs
• Maximum induced matchings of random cubic graphs
• Strong and weighted matchings in inhomogenous random graphs
• Structure of the largest subgraphs of \(G_{n , p}\) with a given matching number
• Isomorphisms between random graphs
• The strong matching number of a random graph
• The inducibility of complete bipartite graphs
• The largest hole in sparse random graphs
• Induced forests in some distance-regular graphs
• Induced forests and trees in Erdős-Rényi random graph
• The largest hole in sparse random graphs
• Parameterized results on acyclic matchings with implications for related problems
• Long induced paths in expanders
• \(\mathcal{P}\)-matchings parameterized by treewidth
• Large induced distance matchings in certain sparse random graphs
• Maximum induced trees and forests of bounded degree in random graphs

This page was built for publication: Large induced matchings in random graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5854458)