Structure of the largest subgraphs of G_n,p with a given matching number

2019/04/25 by Raz, Abigail
#05C35 #05C80 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1904.11571

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≥ (8 ln n)/(n) or p ≪ (1)/(n), but that it does not extend (again with high probability) when (4ln(2e))/(n) < p< (ln n)/(3n).

Related

• Factorially many maximum matchings close to the Erdős-Gallai bound
• Unusually large components in near-critical Erdős-Rényi graphs via ballot theorems
• On the Matching Problem in Random Hypergraphs
• Large induced matchings in random graphs
• An analogue of the Erdős-Gallai theorem for random graphs