ISSN:
1439-6912
Keywords:
AMS Subject Classification (1991) Classes: 05C75
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
G on vertex set , , with density d〉2ε and all vertex degrees not too far from d, has about as many perfect matchings as a corresponding random bipartite graph, i.e. about . 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 and , the number of edges of the matching spanned between S and T is close to |S||T|/n (c.f. Lemma 1). As an application we give an alternative proof of the Blow-up Lemma of Komlós, Sárközy and Szemerédi [10].
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/s004930050063
Permalink
