Maximum matchings in a class of random graphs (Q1093654)

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.