Random Lifts Of Graphs: Perfect Matchings

被引：0

作者：

Nathan Linial*

Eyal Rozenman

机构：

[1] Hebrew University,Institute of Computer Science

[2] Hebrew University,Institute of Computer Science

来源：

Combinatorica | 2005年 / 25卷

关键词：

05C80; 05C70;

D O I：

暂无

中图分类号：

学科分类号：

摘要：

We study random lifts of a graph G as defined in [1]. We prove a 0-1 law which states that for every graph G either almost every lift of G has a perfect matching, or almost none of its lifts has a perfect matching. We provide a precise description of this dichotomy. Roughly speaking, the a.s. existence of a perfect matching in the lift depends on the existence of a fractional perfect matching in G. The precise statement appears in Theorem 1.

引用

页码：407 / 424

页数：17