Perfect Matchings in ε-Regular Graphs and the Blow-Up Lemma
Perfect Matchings in ε-Regular Graphs and the Blow-Up Lemma
复制标题
ε-正则图中的完美匹配和爆炸引理
DOI：
10.1007/s004930050063
复制
发表时间：
1999
期刊：
影响因子：
1.1
通讯作者：
A. Rucinski
中科院分区：
文献类型：
--
作者：
V. Rödl;A. Rucinski
图G在顶点集d>2ε且所有顶点的度都不太远离d的顶点集上，其完美匹配数约等于相应的随机二部图的完美匹配数，即约.本文利用这一结果证明，当概率迅速接近1时，从图G中随机抽取的完美匹配是均匀分布的，即对任意大的顶点子集和，在S和T之间跨越的匹配的边的数量接近于|S||不|/n（c.f.引理1）.作为应用，我们给出了Komlós，Sárközy和Szemerédi [10]的Blow-up引理的另一种证明.
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].