Dimer models have a long and fruitful history in fields ranging from organic chemistry to statistical mechanics and condensed matter physics, where in each case one can abstract the states or degrees of freedom of a physical system as instances of perfect matchings in a graph. Here, the enumeration of perfect matchings has often proven germane to characterizing the general behavior of physical systems, and in predicting critical phenomena such as phase transitions. In the other direction, the search for exact solutions to the dimer model has been a boon to graph theorists and computer scientists, having resulted in the development of the classic Fisher-Kasteleyn-Temperley (FKT) \(\mathcal {O} \! \left( n^3\right) \) time algorithm for counting perfect matchings in order n planar graphs. In this work we introduce the valency model, which represents soft-core constraints for dimer models (i.e., constraints allowing multiple dimers to share an endpoint) at a maximum occupancy limit where we require each vertex in a graph to host some specified number of dimers. We first distinguish the valency model from the original dimer model (i.e., where the FKT algorithm applies) by establishing that it is #P-complete to count legal edge weight assignments satisfying instances of the valency model on planar graphs of maximum vertex degree 3. On the other hand, assuming a fixed upper bound for vertex degrees and edge weights, we give an algorithm for finding individual legal edge weight assignments for valency models that has the same asymptotic time complexity as state-of-the-art algorithms for finding perfect matchings. Finally, we provide a method of efficiently reducing the problem of counting legal edge weight assignments for arbitrary valency models to computing the permanent or hafnian of a matrix whose non-zero elements are a root of unity.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Packing Dimers to Maximum Occupancy Under Soft-Core Constraints

  • Robert D. Barish,
  • Tetsuo Shibuya

摘要

Dimer models have a long and fruitful history in fields ranging from organic chemistry to statistical mechanics and condensed matter physics, where in each case one can abstract the states or degrees of freedom of a physical system as instances of perfect matchings in a graph. Here, the enumeration of perfect matchings has often proven germane to characterizing the general behavior of physical systems, and in predicting critical phenomena such as phase transitions. In the other direction, the search for exact solutions to the dimer model has been a boon to graph theorists and computer scientists, having resulted in the development of the classic Fisher-Kasteleyn-Temperley (FKT) \(\mathcal {O} \! \left( n^3\right) \) time algorithm for counting perfect matchings in order n planar graphs. In this work we introduce the valency model, which represents soft-core constraints for dimer models (i.e., constraints allowing multiple dimers to share an endpoint) at a maximum occupancy limit where we require each vertex in a graph to host some specified number of dimers. We first distinguish the valency model from the original dimer model (i.e., where the FKT algorithm applies) by establishing that it is #P-complete to count legal edge weight assignments satisfying instances of the valency model on planar graphs of maximum vertex degree 3. On the other hand, assuming a fixed upper bound for vertex degrees and edge weights, we give an algorithm for finding individual legal edge weight assignments for valency models that has the same asymptotic time complexity as state-of-the-art algorithms for finding perfect matchings. Finally, we provide a method of efficiently reducing the problem of counting legal edge weight assignments for arbitrary valency models to computing the permanent or hafnian of a matrix whose non-zero elements are a root of unity.