On the number of nearly perfect matchings in almost regular uniform hypergraphs (Q1817560)
From MaRDI portal
| This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: On the number of nearly perfect matchings in almost regular uniform hypergraphs |
scientific article; zbMATH DE number 1382629
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | On the number of nearly perfect matchings in almost regular uniform hypergraphs |
scientific article; zbMATH DE number 1382629 |
Statements
On the number of nearly perfect matchings in almost regular uniform hypergraphs (English)
0 references
15 August 2000
0 references
\textit{N. Pippenger} and \textit{J. Spencer} [J. Comb. Theory, Ser. A 51, No. 1, 24-42 (1989; Zbl 0729.05038)] showed the existence of a nearly perfect matching in almost regular uniform hypergraphs satisfying certain conditions. \textit{D. A. Grable} and \textit{K. T. Phelps} [J. Comb. Des. 4, No. 4, 255-273 (1996; Zbl 0911.05028)] showed that such hypergraphs have exponentially many nearly perfect matchings. In this paper the authors present a simple proof of Grable's extension of Pippenger's theorem based on a comparison of upper and lower bounds of the probability for a random subgraph to have a nearly perfect matching.
0 references
perfect matching
0 references
hypergraph
0 references
Lovász local lemma
0 references