Perfect Matchings In ε-Regular Graphs And The Blow-Up Lemma

As proved in [2], every ffl-regular graph G on vertex set V1 [V2 , jV 1 j = jV 2 j = n, with density d ? 2ffl and all vertex degrees not too far from d, has about as many perfect matchings as a corresponding random bipartite graph, i.e. about d n n!. In this paper we utilize that result to prove that with probability quickly approaching one, a perfect matching drawn randomly from G is spread evenly, in the sense that for any large subsets of vertices S ae V1 and T ae V2 , the number of edges of the matching spanned between S and T is close to jSjjT j=n (c.f. Lemma 1). As an application we give an alternative proof of the Blow-up Lemma of Koml'os, S'arkozy and Szemer'edi [10]