On the number of nearly perfect matchings in almost regular uniform hypergraphs

AbstractStrengthening the result of Rődl and Frankl (Europ. J. Combin 6 (1985) 317–326), Pippenger proved the theorem stating the existence of a nearly perfect matching in almost regular uniform hypergraph satisfying some conditions (see J. Combin. Theory A 51 (1989) 24–42). Grable announced in J. Combin. Designs 4 (4) (1996) 255–273 that such hypergraphs have exponentially many nearly perfect matchings. This generalizes the result and the proof in Combinatorica 11 (3) (1991) 207–218 which is based on the Rődl Nibble algorithm (European J. Combin. 5 (1985) 69–78). In this paper, we present a simple proof of Grable's extension of Pippenger's theorem. Our proof is based on a comparison of upper and lower bounds of the probability for a random subgraph to have a nearly perfect matching. We use the Lovasz Local Lemma to obtain the desired lower bound of this probability