Can I read Matchings and Independent Sets of a Fixed Size in Regular Graphs on EtoBox?

Matchings and Independent Sets of a Fixed Size in Regular Graphs by Carroll, Teena; Galvin, David; Tetali, Prasad is a scholarly article available to read on EtoBox.

What is Matchings and Independent Sets of a Fixed Size in Regular Graphs about?

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 $\frac{2\ell}{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 $\ell$ in the graph consisting of $\frac{N}{2d}$ disjoint copies of the complete bipartite graph $K_{d,d}$. This provides asymptotic evidence for a conjecture of S. Friedland {\it 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.

Author

Carroll, Teena; Galvin, David; Tetali, Prasad

Published

2012

Language

EN