Matching and covering the vertices of a random graph by copies of a given graph (Q1199484): Difference between revisions

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)].