Matchings in regular graphs: minimizing the partition function

2020/06/30 by Márton Borbényi, Borbényi, Márton, Péter Csíkvári +1
Mathematics · Computer Science · #Graph theory and applications #Limits and Structures in Graph Theory #Advanced Graph Theory Research

paper · doi:10.48550/arxiv.2006.16815

Abstract

For a graph G on v(G) vertices let m_k(G) denote the number of matchings of size k, and consider the partition function M_G(λ)=∑_k=0ⁿm_k(G)λ^k. In this paper we show that if G is a d--regular graph and 0\frac1v(K_d+1)ln M_K_d+1(λ). The same inequality holds true if d=3 and λ<0.3575. More precise conjectures are also given.

Related

• Matchings and Independent Sets of a Fixed Size in Regular Graphs
• Maximum matchings in regular graphs
• Results and open problems in matchings in regular graphs
• On the Number of Matchings in Regular Graphs
• Perfect partition of some regular bipartite graphs