Matchings in regular graphs: minimizing the partition function

DOI10.22108/TOC.2020.123763.1742MaRDI QIDQ4997230zbMATH OpenOpenAlexFDO

Authors Márton Borbényi, Péter Csikvári

Publication date 28 June 2021

Full work available at URL https://arxiv.org/abs/2006.16815

zbMATH Keywords

matching polynomialmatchingsregular graphs

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Graph polynomials (05C31) Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

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(lambda)=su{m}_{k=0}^n{m}_k(G)lambd{a}^k$. In this paper we show that if $G$ is a $d$--regular graph and $0<lambda<(4d{)}^{-2}$, then ${\displaystyle }$frac{1}{v(G)}ln M_G(lambda)>frac{1}{v(K_{d+1})}ln M_{K_{d+1}}(lambda).${\displaystyle }$ The same inequality holds true if $d=3$ and $lambda<0.3575$. More precise conjectures are also given.

Recommendations

• Matchings and independent sets of a fixed size in regular graphs
• On the number of matchings in regular graphs
• Random matchings in regular graphs
• Results and open problems in matchings in regular graphs
• A proof of the upper matching conjecture for large graphs

Cites work

• Counting matchings and tree-like walks in regular graphs
• scientific article; zbMATH DE number 428989 (Why is no real title available?)
• Independent sets, matchings, and occupancy fractions
• Lower matching conjecture, and a new proof of Schrijver's and Gurvits's theorems
• Maximising the permanent of (0,1)-matrices and the number of extensions of Latin rectangles
• Maximum matching and a polyhedron with 0,1-vertices
• Maximum matchings in regular graphs of high girth
• On the density of triangles and squares in regular finite and unimodular random graphs
• On the number of matchings in regular graphs
• Short proofs on the matching polyhedron
• Theory of monomer-dimer systems

Cited in

(4)

• On the number of matchings in regular graphs
• An identity involving 3-regular graphs
• Results and open problems in matchings in regular graphs
• Minimum codegree condition for perfect matchings in k‐partite k‐graphs

This page was built for publication: Matchings in regular graphs: minimizing the partition function

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4997230)