Enumeration of Perfect Matching of Graphs with Applications

图与应用完美匹配的枚举

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

Ciucu 9802390 This project is concerned with the enumeration of perfect matchings of certain special graphs that turn out to be closely related to several important problems in combinatorics (enumeration of spanning trees, plane partitions, alternating sign matrices), and also have strong connections with interesting questions in probability (rapidly mixing Markov chains) and statistical physics (dimer models and vertex models). Specifically, based on the solution the PI found for an open spanning tree enumeration problem posed by Stanley, the PI intends to extend the ideas in his previous work on the factorization theorem for perfect matchings of symmetric graphs to obtain similar factorizations for characteristic polynomials of graphs and, as a consequence, for spanning trees. Furthemore, the PI intends to use ideas from his work on the complementation theorem for perfect matchings to classify periodic weightings of the Aztec diamond that lead to nice enumeration formulas. This would give a unified perspective on several results of Elkies, Kuperberg, Larsen and Propp, B. Y. Yang, Stanley and the PI. In addition to the core research program outlined above, the PI intends to pursue three additional problems. First, the PI will pursue extending comparison results of Diaconis and Saloff-Coste to non-reversible Markov chains. This would allow one to deduce the rapid mixing of the elementary move Markov chain on certain three dimensional ``lozenge'' tilings, considered by the PI as an analog of the two dimensional situation studied by Luby, Randall and Sinclair. Second, the PI will continue his investigations of the three dimensional dimer problem by considering, besides the simple cubic lattice, other lattices of comparable interest (e.g., the body-centered cubic lattice or the face-centered cubic lattice), as well as some other problems likely to be suitable for such an analysis (e.g., three-colorings of the cubic lattice). And third, the PI intends to extend his joint work w ith C. Krattenthaler on enumeration of lozenge tilings of certain regions of the triangular lattice to more general (possibly weighted) regions relevant to plane partition enumeration. 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.

Ciucu 9802390 该项目涉及某些特殊图的完美匹配的枚举，这些特殊图与组合学中的几个重要问题（生成树的枚举、平面分区、交替符号矩阵）密切相关，并且与概率（快速混合马尔可夫链）和统计物理（二聚体模型和顶点模型）中的有趣问题有很强的联系。具体来说，基于 PI 为 Stanley 提出的开放生成树枚举问题找到的解决方案，PI 打算扩展他之前关于对称图完美匹配因式分解定理的工作中的思想，以获得图的特征多项式的类似因式分解，从而获得生成树的类似因式分解。此外，PI 打算利用他在完美匹配互补定理方面的研究成果来对阿兹特克钻石的周期权重进行分类，从而得出良好的枚举公式。这将为 Elkies、Kuperberg、Larsen 和 Propp、B. Y. Yang、Stanley 和 PI 的多项结果提供统一的视角。除了上述核心研究计划外，PI 还打算解决另外三个问题。首先，PI 将追求将 Diaconis 和 Saloff-Coste 的比较结果扩展到不可逆马尔可夫链。这将允许人们推断出基本移动马尔可夫链在某些三维“菱形”平铺上的快速混合，PI 将其视为 Luby、Randall 和 Sinclair 研究的二维情况的模拟。其次，PI将继续对三维二聚体问题的研究，除了简单立方晶格之外，还考虑其他类似感兴趣的晶格（例如体心立方晶格或面心立方晶格），以及可能适合此类分析的其他一些问题（例如立方晶格的三色）。第三，PI 打算将他与 C. Krattenthaler 的合作工作扩展到三角格子某些区域的菱形平铺枚举到与平面分区枚举相关的更一般（可能是加权）区域。 这项研究属于组合学的一般领域。组合学的目标之一是找到研究如何排列离散对象集合的有效方法。离散系统的行为对于现代通信极其重要。例如，大型网络的设计（例如电话系统中的网络）以及计算机科学中处理离散对象集的算法设计，都利用了组合研究。