Matchings and Independent Sets of a Fixed Size in Regular Graphs

Teena Carroll, David Galvin, Prasad Tetali

We use an entropy based method to study two graph maximization problems. We upper bound the number of matchings of fixed size $\ell$ in a $d$-regular graph on $N$ vertices. For $\f…