On large matchings and cycles in sparse random graphs (Q1092926): Difference between revisions

The subject of investigation is the existence of large matchings and cycles in a random graph on n vertices having edge-probability \(p=c/n\). For large c, such a graph contains (with probability approaching one as \(n\to \infty)\) matching with size \((1-(1+\epsilon (c))e^{-c})n\) and a cycle of length \((1-(1+\epsilon (c))e^{-c})n\), where \(\epsilon\) (c)\(\to 0\) as \(c\to \infty\). The author shows a stronger property, that, for any positive integer k, there exists a large subgraph (with given size) containing \(\lfloor k\rfloor\) edge-disjoint Hamilton cycles, plus an edge-disjoint matching leaving exactly one vertex isolated if k is odd.