A normal law for matchings

Dedicated to the memory of Paul Erdos, both for his pioneering discovery of normality in unexpected places, and for his questions, some of which led ( eventually) to the present work. For a simple graph G, let xi(G) be the size of a matching drawn uniformly a t random front the set of all matchings of G. Motivated by work of C. Godsi l [11], we give, for a sequence {G(n)} and xi(n) = xi(Gn), several necessar y and sufficient conditions for asymptotic normality of the distribution of xi(n), for instance {Pr(xi(n) = k)}(k greater than or equal to 0) is asymptotically normal iff nu(n) - mu(n) --> infinity (where mu(n) = E xi(n) and nu(n) is the size of a, largest matching in G(n) ). In particular this gives asymptotic normality for any sequence of regula r graphs (of positive degree) or graphs with perfect matchings. When nu(n) - mu(n) tends to a finite limit, a sufficient (and probably necessary) cond ition is given for nu(n) - xi(n) to be asymptotically Poisson. The material presented here suggests numerous related questions, some of which are disc ussed in the last section of the paper.