Matchings and independent sets of a fixed size in regular graphs

We use an entropy based method to study two graph maximization problems. We upper bound the number of matchings of fixed size ℓ in a d-regular graph on N vertices. For 2 ℓ N bounded away from 0 and 1, the logarithm of the bound we obtain agrees in its leading term with the logarithm of the number of matchings of size ℓ in the graph consisting of N 2 d disjoint copies of K d , d . This provides asymptotic evidence for a conjecture of S. Friedland et al. We also obtain an analogous result for independent sets of a fixed size in regular graphs, giving asymptotic evidence for a conjecture of J. Kahn. Our bounds on the number of matchings and independent sets of a fixed size are derived from bounds on the partition function (or generating polynomial) for matchings and independent sets.