Matching and covering the vertices of a random graph by copies of a given graph
type: Item
instance of: scholarly article
title: Matching and covering the vertices of a random graph by copies of a given graph
zbMATH Open document ID: 0774.05091
DOI: 10.1016/0012-365X(92)90141-2
author: Andrzej Ruciński
published in: Discrete Mathematics
publication date: 1993-01-16T00:00:00Z
review text: We partially answer the question: how slowly must \(p(n)\) converge to 0 so that a random graph \(K(n,p)\) has property \(\text{PM}_ G\) almost surely, where \(\text{PM}_ G\) means that all \(n\) vertices can be covered by vertex-disjoint copies of a fixed graph \(G\). For \(G=K_ 2\) this is the problem of finding the edge-probability threshold for the existence of a perfect matching solved by P. Erdős and A. Rényi in 1966. For graphs \(G\) with minimum degree smaller than \(m(G)=\max_{H\subseteq G}{e(H)\over v(H)-1}\), we find that the threshold for \(\text{PM}_ G\) is \(p=n^{-1/m(G)}\). A necessary condition for \(\text{PM}_ G\) is the property \(\text{COV}_ G\) that each vertex lies in a copy of \(G\). Although for every tree \(T\) the thresholds for \(\text{PM}_ T\) and \(\text{COV}_ T\) coincide (see \textit{T. Łuczak} and the author [SIAM J. Discrete Math. 4, 107-120 (1991; Zbl 0766.05078)]), it is not the case for general \(G\) and a class of counterexamples will be presented. We also establish a threshold theorem for matching all but \(o(n)\) vertices into vertex-disjoint copies of \(G\). Most proofs make use of a recent correlation inequality from \textit{S. Janson}, \textit{T. Łuczak} and the author [Random graphs '87, Proc. 3rd Int. Semin., Poznan/Poland 1987, 73- 87 (1990; Zbl 0733.05073)].
reviewed by: Andrzej Ruciński
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 94356
zbMATH Keywords: covering
zbMATH Keywords: random graph
zbMATH Keywords: perfect matching
MaRDI profile type: Publication
cites work: Threshold functions for small subgraphs
cites work: Threshold functions
cites work: Q5343356
cites work: On the existence of a factor of degree one of a connected random graph
cites work: Q3749092
cites work: Q3360223
cites work: Tree-Matchings in Graph Processes
cites work: Strongly balanced graphs and random graphs
cites work: Threshold functions for extension statements
description: scientific article; zbMATH DE number 94356