Maximum matchings in a class of random graphs
type: Item
instance of: scholarly article
title: Maximum matchings in a class of random graphs
zbMATH Open document ID: 0629.05057
DOI: 10.1016/0095-8956(86)90077-8
published in: Journal of Combinatorial Theory. Series B
publication date: 1986-01-01T00:00:00Z
review text: A random graph D(n,m) is obtained by first picking uniformly at random a digraph with vertex set \(\{\) 1,...,n\(\}\) and each outdegree m, and then ignoring orientations of edges. It is not hard to show that D(n,1) almost surely has no perfect matching. Shamir and Upfal proved that D(n,6) almost surely has a perfect matching for n even. The present paper shows that this conclusion holds for D(n,2). The proof is based on a refinement of Tutte's theorem on the existence of perfect matchings, and involves many careful estimations.
Mathematics Subject Classification ID: 05C80
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 4023338
zbMATH Keywords: random graph
zbMATH Keywords: perfect matching
author: Alan Frieze
reviewed by: Colin McDiarmid
MaRDI profile type: Publication
full work available at URL: 0095-8956(86)90077-8
OpenAlex ID: W2054534432
Wikidata QID: Q57401629
cites work: Paths, Trees, and Flowers
cites work: On the connectivity of random m-orientable graphs and digraphs
cites work: On the existence of Hamiltonian cycles in a class of random graphs
cites work: Q3270978
cites work: An exact threshold theorem for random graphs and the node-packing problem
cites work: Random near-regular graphs and the node packing problem
cites work: One-factor in random graphs based on vertex choice
cites work: The Factorization of Linear Graphs
cites work: Matchings in random regular bipartite digraphs
Recommended article: Maximum matchings in general graphs through randomization
Recommended article: Combinatorial Geometry and Graph Theory
Recommended article: The number of matchings in random graphs
Recommended article: A concentration inequality for maximum matching size in random graphs1
Recommended article: Q4508359
Recommended article: Q4325283
Recommended article: On maximal matchings of connected graphs
Recommended article: Small maximal matchings in random graphs.
Recommended article: Maximum matching in regular and almost regular graphs
Recommended article: Random matchings in regular graphs
description: scientific article; zbMATH DE number 4023338