پیوندهای مفید
اخبار و اعلانات
آمار
| تعداد نشریات | 42 |
| تعداد شماره‌ها | 1,510 |
| تعداد مقالات | 12,450 |
| تعداد مشاهده مقاله | 24,648,257 |
| تعداد دریافت فایل اصل مقاله | 10,412,902 |
Matchings in regular graphs: minimizing the partition function | ||
| Transactions on Combinatorics | ||
| مقاله 1، دوره 10، شماره 2، شهریور 2021، صفحه 73-95 اصل مقاله (334.19 K) | ||
| نوع مقاله: Research Paper | ||
| شناسه دیجیتال (DOI): 10.22108/toc.2020.123763.1742 | ||
| نویسندگان | ||
| Márton Borbényi؛ Peter Csikvari* | ||
| Eötvös Loránd University, Budapest, Hungary | ||
| چکیده | ||
| 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. | ||
| کلیدواژه‌ها | ||
| matchings؛ matching polynomial؛ regular graphs | ||
| مراجع | ||
|
[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. | ||
|
آمار تعداد مشاهده مقاله: 167 تعداد دریافت فایل اصل مقاله: 197 |
||