Title of article
Matchings in regular graphs: minimizing the partition function
Author/Authors
Borbényi, Márton Eötvös Loránd University - Budapest, Hungary , Csikvari, Peter Eötvös Loránd University - Budapest, Hungary
Pages
23
From page
73
To page
95
Abstract
For a graph G on v(G) vertices let mk(G) denote the number of matchings of size k, and consider the partition function MG(λ)=∑nk=0mk(G)λk. In this paper we show that if G is a d--regular graph and 0<λ<(4d)−2, then
1v(G)lnMG(λ)>1v(Kd+1)lnMKd+1(λ).
The same inequality holds true if d=3 and λ<0.3575. More precise conjectures are also given.
Keywords
matchings , matching polynomial , regular graphs
Journal title
Transactions on Combinatorics
Serial Year
2021
Record number
2698125
Link To Document