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

• Strengthening 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.

Ämnesord

NATURVETENSKAP  -- Matematik -- Matematisk analys (hsv//swe)

NATURAL SCIENCES  -- Mathematics -- Mathematical Analysis (hsv//eng)

Nyckelord

Matematik

Mathematics

Publikations- och innehållstyp

ref (ämneskategori)

art (ämneskategori)