Matchings and independent sets of a fixed size in regular graphs

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:116

Article

Carroll, Teena¹  Galvin, David²  Tetali, Prasad^3,4 

[1] St Norbert Coll, Dept Math, De Pere, WI 54115 USA

[2] Univ Notre Dame, Dept Math, South Bend, IN USA

[3] Georgia Inst Technol, Sch Math, Atlanta, GA 30332 USA

[4] Georgia Inst Technol, Sch Comp Sci, Atlanta, GA 30332 USA

关键词: Entropy;    Stable sets;    Matching polynomial;    Monomer-dimer model;    Hard-core model;    Graph homomorphisms;   

DOI  :  10.1016/j.jcta.2008.12.008

来源: Elsevier

【 摘 要 】

We use an entropy based method to study two graph maximization problems. We upper bound the number of matchings of fixed size l in a d-regular graph on N vertices. For 2l/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 l in the graph consisting of N/2d 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. (C) 2009 Elsevier Inc. All rights reserved.

【 授权许可】

Free