Asymptotic Enumeration of Perfect Matchings of Lattice Graphs

格图完美匹配的渐近枚举

• 批准号: 0100950
• 负责人: Mihai Ciucu
• 金额: $ 8.07万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2001
• 资助国家: 美国
• 起止时间: 2001-07-15 至 2004-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0100950&HistoricalAwards=false
• 关键词: Asymptotic; Enumeration; Perfect; Matchings; Lattice

This project is concerned with the asymptotic and exact enumeration of perfect matchings of certain lattice graphs (or, in an equivalent language, enumeration of tilings of the regions dual to these graphs) that turn out to be closely related to several important problems in combinatorics (enumeration of spanning trees, plane partitions, alternating sign matrices), and that appear in statistical physics in the guise of the dimer model. Specifically, motivated by the monomer-monomer correlation introduced by Fisher and Stephenson, and based on the exact enumeration found by the proposer of the tilings of certain hexagonal regions with triangular holes along their symmetry axes (which generalizes MacMahon's theorem on counting plane partitions), the proposer pursues extending his work on the asymptotic enumeration of tilings in the situation when the holes are not necessarily on the symmetry axis of the region. This should bring useful insight into an important conjecture of Fisher and Stephenson concerning the rotational invariance of the monomer-monomer correlation. Furthermore, the proposer studies three additional problems. First, the proposer pursues extending the arguments that allowed him to prove directly one identity from a set of four similar identities he found relating eight of the ten symmetry classes of plane partitions to the remaining three identities. This would help explaining the still mysterious fact that all ten cases are enumerated by simple product formulas and would bring close to completion the task of finding combinatorial proofs for all ten cases. Second, the proposer continues his work on the three dimensional dimer problem by considering the question of improving the lower bound, employing extensions to three dimensions of the Gessel-Viennot and Kasteleyn theorems that yield signed enumerations. And third, the proposer uses a generalization of his complementation theorem for perfect matchings to classify the periodic weightings of the Aztec diamond that lead to simple product enumeration formulas, thus giving a unified perspective on several results of Elkies, Kuperberg, Larsen and Propp, B. Y. Yang, Stanley and the proposer.This research is in the general area of Combinatorics. One of the goals of Combinatorics is to find efficient methods of studying how discrete collections of objects can be arranged. The behavior of discrete systems is extremely important to modern communications. For example, the design of large networks, such as those occurring in telephone systems, and the design of algorithms in computer science deal with discrete sets of objects, and this makes use of combinatorial research. The specific problems in this project are instances of the dimer model of statistical physics. A basic illustration of this is the real-world process (relevant to the study of of lubricants) of adsorption of a liquid, consisting of two-atom molecules --- the dimers in the model --- along the surface of a crystal, whose fixed atoms form a lattice pattern, with any two neighboring positions capable of holding one molecule, and any given crystal atom being involved in the adsorption of at most one molecule. The main issue in this setting is the asymptotic behavior of the quantities that are studied (specifically, the number of different ways the surface of the crystal can be covered by molecules), but it turns out in the present context that the usually more difficult problem of determining quantities exactly allows progress in the asymptotic study.

这个项目是关于某些格图的完美匹配的渐近和精确枚举（或者，用等效的语言，对这些图的对偶区域的平铺枚举），结果与组合学中的几个重要问题（生成树的枚举，平面划分，交替符号矩阵）密切相关，并且以二聚体模型的名义出现在统计物理中。具体地说，在Fisher和Stephenson引入的单体-单体相关理论的推动下，基于作者对某些六边形区域沿对称轴有三角形孔的平铺的精确枚举（这推广了MacMahon计算平面分区的定理），作者扩展了他的工作，研究了洞不一定在区域对称轴上的情况下平铺的渐近枚举。这将有助于理解Fisher和Stephenson关于单体-单体相关的旋转不变性的重要猜想。此外，本文还研究了三个附加问题。首先，提出者继续扩展他的论证，这些论证使他能够从一组四个相似的恒等式中直接证明一个恒等式，他发现这四个相似的恒等式将平面划分的十个对称类中的八个与剩下的三个恒等式联系起来。这将有助于解释所有十种情况都是由简单的乘积公式列举出来的这个仍然神秘的事实，并将使为所有十种情况找到组合证明的任务接近完成。其次，作者继续他在三维二聚体问题上的工作，通过考虑改进下界的问题，将Gessel-Viennot定理和Kasteleyn定理扩展到三维，产生有符号枚举。第三，通过对他的完美匹配互补定理的推广，对阿兹特克钻石的周期权重进行分类，从而得出简单的乘积枚举公式，从而对Elkies、Kuperberg、Larsen和Propp、b.y. Yang、Stanley和作者的几个结果给出了统一的视角。这项研究属于组合学的一般领域。组合学的目标之一是找到研究离散对象集合如何排列的有效方法。离散系统的行为对现代通信极为重要。例如，大型网络的设计，比如那些出现在电话系统中的网络，以及计算机科学中处理离散对象集的算法设计，这就利用了组合研究。这个项目中的具体问题是统计物理的二聚体模型的实例。一个基本的例子是现实世界中液体的吸附过程（与润滑油的研究有关），由两原子分子组成的液体——模型中的二聚体——沿着晶体表面，其固定的原子形成晶格模式，任意两个相邻的位置都能容纳一个分子，任何给定的晶体原子都参与了最多一个分子的吸附。这种情况下的主要问题是所研究的量的渐近行为（具体来说，晶体表面可以被分子覆盖的不同方式的数量），但在目前的情况下，通常更困难的确定量的问题恰恰允许渐近研究取得进展。