Matchings in regular graphs‎: ‎minimizing the partition function

Document Type : Research Paper

Authors

Eötvös Loránd University, Budapest, Hungary

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

Keywords

Main Subjects

References

[1] P. Csikvári, Lower matching conjecture, and a new proof of Schrijver’s and Gurvits’s theorems, J. Eur. Math. Soc.
(JEMS), 19 (2017) 1811–1844.
[2] E. Davies, M. Jenssen and W. Perkins, A proof of the upper matching conjecture for large graphs, arXiv preprint
arXiv:2004.06695, (2020).
[3] E. Davies, M. Jenssen, W. Perkins and B. Roberts, Independent sets, matchings, and occupancy fractions, J. Lond.
Math. Soc. (2), 96 (2017) 47–66.
[4] J. Edmonds, Maximum matching and a polyhedron with 0, 1-vertices, J. Res. Nat. Bur. Standards Sect. B, 69
(1965) 125–130.
[5] A. D. Flaxman and S. Hoory, Maximum matchings in regular graphs of high girth, Electron. J. Combin., 14 (2007)
4 pp.
[6] S. Friedland, E. Krop and K. Markström, On the number of matchings in regular graphs, Electron. J. Combin.,
15 (2008) 28 pp.
[7] C. Godsil, Algebraic combinatorics, 6, Chapman and Hall Mathematics Series. Chapman Hall, New York, 1993.
[8] L. Gurvits, Unleashing the power of Schrijver’s permanental inequality with the help of the Bethe approximation,
arXiv preprint arXiv:1106.2844, (2011).
[9] V. Harangi, On the density of triangles and squares in regular finite and unimodular random graphs, Combinatorica,
33 (2013) 531–548.
[10] O. J. Heilmann and E. H. Lieb, Theory of monomer-dimer systems, Comm. Math. Phys., 25 (1972) 190–232.
[11] B. D. McKay and I. M. Wanless, Maximising the permanent of (0, 1)-matrices and the number of extensions of
latin rectangles, Electron. J. Combin., 5 (1998) 20 pp.
[12] A. Schrijver, Short proofs on the matching polyhedron, J. Combin. Theory Ser. B, 34 (1983) 104–108.
[13] I. M. Wanles, Counting matchings and tree-like walks in regular graphs, Combinatorics, Probability and Computing,
19 (2010) 463–480.

Files

History

  • Receive Date: 01 July 2020
  • Revise Date: 01 November 2020
  • Accept Date: 01 November 2020
  • Published Online: 01 June 2021

Share

How to cite

Statistics