Record number :
1531442
Title of article :
Matchings and independent sets of a fixed size in regular graphs
Author/Authors :
Carroll، نويسنده , , Teena and Galvin، نويسنده , , David and Tetali، نويسنده , , Prasad، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2009
Pages :
9
From page :
1219
To page :
1227
Abstract :
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.
Keywords :
entropy , Stable sets , Matching polynomial , Monomer–dimer model , Hard-core model , Graph homomorphisms
Journal title :
Journal of Combinatorial Theory Series A
Serial Year :
2009
Link To Document :
بازگشت