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

DOI10.1016/J.DISC.2020.112227MaRDI QIDQ2222927zbMATH OpenOpenAlexFDO

Authors Abigail Raz

Publication date 27 January 2021

Published in Discrete Mathematics (Search for Journal in Brave)

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

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)

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$.

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

Cites work

• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• Improved bounds for Erdős' matching conjecture
• On Erdős' extremal problem on matchings in hypergraphs
• On maximal paths and circuits of graphs
• On the maximum number of edges in a hypergraph with given matching number
• The size of a hypergraph and its 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)