Perfect Matchings in Random r -regular, s -uniform Hypergraphs
Colin Cooper, Alan Frieze, Michael Molloy, Bruce Reed
Source record
Source: Crossref
Published: Mar 1, 1996
DOI: 10.1017/s0963548300001796
Open original source ↗Source abstract
We show that r -regular, s -uniform hypergraphs contain a perfect matching with high probability (whp), provided The Proof is based on the application of a technique of Robinson and Wormald [7, 8]. The space of hypergraphs is partitioned into subsets according to the number of small cycles in the hypergraph. The difference in the expected number of perfect matchings between these subsets explains most of the variance of the number of perfect matchings in the space of hypergraphs, and is sufficient to prove existence (whp), using the Chebychev Inequality.
Evidence graph
No public relationships recorded yet.
Integrity note: This page is a factual metadata record created by deterministic ingestion. It is not a claim that the work moves a mathematical frontier or has been independently verified.