On the Validations of the Asymptotic Matching Conjectures
On the Validations of the Asymptotic Matching Conjectures
复制标题
关于渐近匹配猜想的验证
DOI：
--
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
K. Markstrom
中科院分区：
文献类型：
--
作者：
S. Friedland;E. Krop;P. Lundow;K. Markstrom
本文回顾了r-正则二部图的渐近匹配猜想，以及它们在估计d维整数格和Bethe格中的单体-二聚体熵方面的联系。我们证明了支持这些猜想的单体-二聚体熵的新的严格上下界。我们刻画了r-正则环面图无限族的一般结构，并给出了对任意p个∈[0，1]计算密度p的单体-二聚体熵的算法。最后，我们利用环图来检验某些无限r-正则二部图的渐近匹配猜想。
In this paper we review the asymptotic matching conjectures for r-regular bipartite graphs, and their connections in estimating the monomer-dimer entropies in d-dimensional integer lattice and Bethe lattices. We prove new rigorous upper and lower bounds for the monomer-dimer entropies, which support these conjectures. We describe a general construction of infinite families of r-regular tori graphs and give algorithms for computing the monomer-dimer entropy of density p, for any p∈[0,1], for these graphs. Finally we use tori graphs to test the asymptotic matching conjectures for certain infinite r-regular bipartite graphs.