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

DOI10.1016/J.DISC.2020.112227zbMATH Open1456.05151arXiv1904.11571OpenAlexW3110610699MaRDI QIDQ2222927FDOQ2222927

Authors: Abigail Raz 

Publication date: 27 January 2021

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: This paper examines the structure of the largest subgraphs of the ErdH{o}s-R'enyi random graph, $G_{n,p}$, with a given matching number. This extends a result of ErdH{o}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 $pgefrac8lnnn$ or $pllfrac1n$, but that it does not extend (again with high probability) when $frac4ln(2e)n<p<fraclnn3n$.

Full work available at URL: https://arxiv.org/abs/1904.11571

Recommendations

• On large matchings and cycles in sparse random graphs
• scientific article; zbMATH DE number 4039956
• Large induced matchings in random graphs
• Matching and covering the vertices of a random graph by copies of a given graph
• scientific article; zbMATH DE number 731847

zbMATH Keywords

random graphmatching numbersubgraph structure

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cites Work

• Title not available (Why is that?)
• On maximal paths and circuits of graphs
• On Erdős' extremal problem on matchings in hypergraphs
• The size of a hypergraph and its matching number
• Improved bounds for Erdős' matching conjecture
• On the maximum number of edges in a hypergraph with given matching number

Cited In (1)

• An analogue of the Erdős-Gallai theorem for random graphs

This page was built for publication: Structure of the largest subgraphs of \(G_{n , p}\) with a given matching number

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2222927)