Structure of the largest subgraphs of $G_{n,p}$ with a given matching number

Abstract

This paper examines the structure of the largest subgraphs of the Erdős-Rényi random graph, $G_{n,p}$, with a given matching number. This extends a result of Erdős and Gallai who, in 1959, gave a classification of the structures of the largest subgraphs of $K_n$ with a given matching number. We show that their result extends to $G_{n,p}$ with high probability when $p\ge \frac{8\ln n}{n}$ or $p\ll \frac{1}{n}$, but that it does not extend (again with high probability) when $\frac{4\ln (2e)}{n}<p<\frac{\ln n}{3n}$.