Enumeration of Perfect Matching of Graphs with Applications

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

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.